Cutting plane techniques are powerful tools in integer programming, enhancing the efficiency of solving complex problems. These methods add mathematical inequalities to linear programming relaxations, tightening the feasible region and bringing solutions closer to integer values.

Various types of cutting planes exist, including Gomory fractional cuts, cover cuts, and lift-and-project cuts. The application of cutting planes involves solving LP relaxations, identifying violated cuts, and re-optimizing. These techniques are often integrated into branch-and-bound algorithms for improved performance.

Cutting Plane Techniques in Integer Programming

Concept of cutting planes

• Mathematical inequalities added to linear programming relaxations tighten feasible region
• Improve LP relaxation bringing solution closer to integer values reducing gap between LP relaxation and integer optimal solution
• Iterative process adds cuts to LP relaxation, resolves LP, repeats until no more cuts found or solution is integer (simplex method)

Types of cutting planes

• Gomory fractional cuts derived from simplex tableau based on fractional parts of basic variables generated using Gomory cutting plane algorithm
• Gomory mixed-integer cuts extend fractional cuts for mixed-integer problems involving continuous and integer variables
• Cover cuts exploit structure of subset sum inequalities identifying minimal cover sets (knapsack problems)
• Lift-and-project cuts derived from disjunctions in integer programming formulation use higher-dimensional space to generate stronger cuts
• Chvátal-Gomory cuts combine existing constraints rounded to obtain valid inequalities for integer program

Application of cutting planes

• Steps to apply cutting planes:

1. Solve LP relaxation
2. Identify violated cutting planes
3. Add cuts to LP formulation
4. Re-optimize LP

• Strengthening formulation reduces feasible region of LP relaxation eliminating fractional solutions bringing LP optimal solution closer to integrality
• Cut management selects most effective cuts removes redundant or weak cuts balances cut generation with solving time
• Termination criteria include no more violated cuts found improvement in objective value becomes negligible maximum number of cuts reached

Cutting planes in branch and bound

• Branch-and-cut algorithm integrates cutting planes within branch-and-bound framework generating cuts at each node of branch-and-bound tree
• Node processing solves LP relaxation applies cutting planes makes branching decisions
• Cut lifting strengthens cuts generated at parent nodes applies them to child nodes
• Global cuts valid for entire problem added to root node
• Local cuts valid only for specific branches of tree used to tighten bounds in subproblems
• Efficiency improvements reduce number of nodes explored improve lower bounds accelerate convergence to optimal integer solution ($z_{IP}$)