Gomory Cutting Plane Pivot Tool

Constraints =     Variables =     Seed =        


            Number format:

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 xj 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 xj 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 xj 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 xj 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 xj 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.