Gomory Cutting Plane Pivot Tool

Gomory Cutting Plane Pivot Tool

Constraints = Variables = Seed =

Number format: Zero Visibility:

Current Dictionary

Instructions

This pivot tool can be used to solve integer programming problems using the Gomory cut method.

This tool is a variant of the Simple Pivot Tool.

Input by hand (or generate randomly) a problem to solve. Ignoring the integrality constraint on the variables, solve the so-called LP-relaxation.

After the relaxation is solved, if by luck all of the x_j variables are integer, then you are done. Click the "Optimal" button to confirm that you have found the optimal solution.

If in the optimal dictionary some of the x_j variables are not integers, then click "Add Cuts" to generate appropriate Gomory cuts as new constraints. The current solution will be infeasible with respect to these constraints. Use the dual simplex method to solve to optimality.

If the new optimal solution has all integer values for the x_j then again you are done. If not, then click "Add Cuts" again and repeat. Keep repeating until the optimal solution has all integer values for the x_j variables.

NOTE: The slack variables introduced as "cuts" have a pair of integers as subscripts. The first integer represents the number of times "Add Cuts" has been invoked and the second integer is the j-index of the variable x_j that is the basic variable in this row.

Acknowledgement: I'd like to thank Hande Benson for coding up the first version of this implemention of the Gomory Cut algorithm.