Gomory cuts revisited

Gomory cuts revisited

0.00 Avg rating0 Votes
Article ID: iaor19972106
Country: Netherlands
Volume: 19
Issue: 1
Start Page Number: 1
End Page Number: 9
Publication Date: Jul 1996
Journal: Operations Research Letters
Authors: , , ,
Keywords: cutting plane algorithms
Abstract:

The authors 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 three search is out of the question as far as the solution of large-scale combinatorial optimization problems is concerned’ because the cuts generated at one node of the search tree need not be valid at other nodes. They 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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.