Module cutting_plane 

Gomory Cutting Plane Method for Integer Programming

The cutting plane method strengthens the LP relaxation by adding Gomory cuts: valid inequalities that eliminate fractional LP solutions while preserving all integer feasible solutions.

A Gomory mixed-integer cut is derived from a row of the optimal LP tableau for a fractional basic variable. For a pure integer program, the classic Gomory fractional cut is used.

Algorithm

1. Solve LP relaxation
2. If solution is integer, stop
3. Generate a Gomory cut from a fractional row
4. Add cut as a new inequality constraint
5. Return to step 1

References

• Gomory, R.E. (1958). “Outline of an algorithm for integer solutions to linear programs.” Bulletin of the AMS, 64(5), 275-278.
• Chvátal, V. (1983). “Linear Programming.” W.H. Freeman.

Structs

CuttingPlaneOptions

Options for the cutting plane method

CuttingPlaneSolver

Cutting plane solver