Gomory cuts revisited

We investigate the use of Gomory's mixed integer cuts within a branch-and-cut framework. It has been argued in the literature that ''a marriage of classical cutting planes and tree search is out of the question as far as the solution of large-scale combinatorial optimization problems is concerned'' [16] because the cuts generated at one node of the search tree need not be valid at other nodes. We show that it is possible, by using a simple lifting procedure, to make Gomory cuts generated at a node of the enumeration tree globally valid in the case of mixed 0-1 programs. The procedure essentially amounts to treating the variables fixed at 0 or 1 as if they were free. We also show why this lifting procedure is not valid for general (other than 0-1) mixed integer programs. Other issues addressed in the paper are of a computational nature, such as strategies for generating the cutting planes, deciding between branching and cutting, etc. The result is a robust mixed integer program solver.