How do you handle multiple objectives or constraints in cutting plane method?

2 What is cutting plane method?

Cutting plane method is a way of solving linear programming problems that have integer variables, also known as integer programming problems. Integer variables are those that can only take whole numbers, such as the number of units produced, the number of workers hired, or the number of routes selected. Integer programming problems are often more difficult to solve than regular linear programming problems, because they have a discrete and finite solution space.

Cutting plane method works by relaxing the integer variables and solving the resulting linear programming problem, which is called the continuous relaxation. If the optimal solution of the continuous relaxation is integer, then it is also the optimal solution of the original problem. However, if the optimal solution of the continuous relaxation is fractional, then it is not feasible for the original problem. In that case, cutting plane method adds a linear inequality, called a cut, to the continuous relaxation, such that the fractional solution is excluded, but all feasible integer solutions are preserved. Then, the method solves the new continuous relaxation with the added cut, and repeats the process until an integer solution is obtained.

3 How to implement cutting plane method?

To implement cutting plane method, you must relax the integer variables and solve the continuous relaxation of the original problem with a linear programming solver, such as simplex method or interior point method. If the optimal solution of the continuous relaxation is integer, then this solution is the optimal solution of the original problem. If not, a cut must be derived from different sources to eliminate the fractional solution of the continuous relaxation. Examples include Gomory cuts, Chvatal-Gomory cuts, or branch-and-cut cuts. The cut is then added to the continuous relaxation and solved again with a linear programming solver. This process is repeated until an integer solution is found or until no more cuts can be generated.

4 How to handle multiple objectives or constraints?

Sometimes, you might have more than one objective or constraint in your linear programming problem. For example, you might want to maximize your profit and minimize your environmental impact, or you might have several budget or capacity constraints. In that case, you need to modify your problem formulation and your cutting plane method accordingly.

One way to handle multiple objectives is to use a weighted sum approach, where you assign a weight to each objective and combine them into a single objective function. For example, if you have two objectives, f1 and f2, you can write your objective function as w1*f1 + w2*f2, where w1 and w2 are the weights that reflect your preferences or trade-offs. Then, you can apply the cutting plane method to this single objective function as usual.

Another way to handle multiple objectives is to use a lexicographic approach, where you rank your objectives by their importance and solve them sequentially. For example, if you have two objectives, f1 and f2, and f1 is more important than f2, you can first solve the problem with f1 as the objective function and obtain an optimal solution x*. Then, you can add a constraint that f1(x) = f1(x*), and solve the problem with f2 as the objective function and obtain another optimal solution y*. Then, you can compare x* and y* and choose the one that satisfies your criteria. You can apply the cutting plane method to each subproblem as usual.

One way to handle multiple constraints is to use a slack variable approach, where you introduce a variable that measures the amount of violation or deviation from a constraint. For example, if you have a constraint of the form ax <= b, you can write it as ax + s = b, where s is the slack variable that represents the difference between b and ax. Then, you can add a penalty term to your objective function that depends on s, such as p*s or p*s^2, where p is a positive constant that reflects the cost of violating the constraint. Then, you can apply the cutting plane method to this modified problem as usual.

Another way to handle multiple constraints is to use a feasibility cut approach, where you add a cut that ensures that all the constraints are satisfied. For example, if you have a set of constraints of the form Ax <= b, you can add a cut of the form x'(Ax - b) >= 0, where x' is a vector of positive constants that reflects the importance or priority of each constraint. Then, you can apply the cutting plane method to this augmented problem as usual.