Cuttingplanes

Cutting planes are a technique used in mathematical optimization to improve the efficiency of algorithms that solve problems. They are particularly relevant in the context of integer programming and mixed-integer programming, where the feasible region is not a convex set. A cutting plane is an inequality that is added to the set of constraints of a linear program. This inequality is chosen such that it does not cut off any feasible integer solutions but eliminates a portion of the fractional (non-integer) feasible region of the linear programming relaxation.

The core idea is to iteratively add cutting planes that tighten the linear programming relaxation of an integer program. Each time a cutting plane is added, a new linear program is solved. If the solution to this new linear program is integer-feasible, then it is also a feasible solution to the original integer program, and the algorithm can terminate. If the solution is fractional, and it's not a feasible integer solution to the original problem, then the cutting plane successfully removed it from consideration without removing any valid integer solutions. This process is repeated until an integer-feasible solution is found.

Various types of cutting planes exist, each derived from different properties of integer constraints. Common examples include Gomory cuts, valid inequalities derived from the problem's structure, and cuts generated by solving subproblems. The effectiveness of cutting plane methods depends on the strength of the cuts generated and the efficiency with which they can be found and incorporated into the linear program. By progressively refining the feasible region, cutting planes help to accelerate the convergence of optimization algorithms towards an optimal integer solution.