Leikkaustasomenetelmät

Leikkaustasomenetelmät, known in English as cutting plane methods, are a class of algorithms used to solve linear and integer programming problems. These methods work by iteratively adding linear inequalities, called cutting planes or cuts, to the feasible region of a relaxation of the original problem. The goal is to shrink the feasible region of the relaxation until it either becomes empty or contains only integer-feasible points.

The fundamental idea is to start with a relaxation of the integer programming problem, typically its linear programming (LP) relaxation, which ignores the integer constraints. If the optimal solution to the LP relaxation is integer-feasible, then it is also an optimal solution to the integer program. However, if the LP solution is not integer-feasible, a cutting plane is generated. This cut is an inequality that is satisfied by all integer-feasible solutions but is violated by the current non-integer LP solution. By adding this cut to the LP relaxation, the feasible region is reduced without excluding any valid integer solutions. The process is then repeated: solve the new LP relaxation, check for integer feasibility, and add a new cut if necessary. This continues until an integer-feasible solution is found.

The effectiveness of cutting plane methods depends heavily on the choice of the cutting planes. Different types of cuts exist, each with its own properties and derivation. Some common examples include Gomory cuts and Chvátal cuts. The efficiency of the algorithm can be significantly influenced by the strength of the cuts (how much they reduce the feasible region) and the number of iterations required to find an integer solution. Cutting plane methods can be used as standalone algorithms or as a subroutine within other integer programming techniques like branch-and-bound.