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 marri age of classical cutting planes and tree search is out of the question as far as the solution of large-scale combinatorial optimization prob lems 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 poss ible, by using a simple lifting procedure, to make Gomory cuts generat ed at a node of the enumeration tree globally valid in the case of mix ed 0-1 programs. The procedure essentially amounts to treating the var iables fixed at 0 or 1 as if they were free. We also show why this lif ting 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 inte ger program solver.