This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Cook, W. Articles by Goycoolea, M.

Numerically Safe Gomory Mixed-Integer Cuts

Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
School of Business, Universidad Adolfo Ibáñez, Peñalolen, 7941169 Santiago, Chile
bico{at}isye.gatech.edu
sanjeebd{at}us.ibm.com
rfukasaw{at}us.ibm.com
marcos.goycoolea{at}uai.cl

We describe a simple process for generating numerically safe cutting planes using floating-point arithmetic and the mixed-integer rounding procedure. Applying this method to the rows of the simplex tableau permits the generation of Gomory mixed-integer cuts that are guaranteed to be satisfied by all feasible solutions to a mixed-integer programming problem (MIP). We report on tests with the MIPLIB 3.0 and MIPLIB 2003 test collections as well as with MIP instances derived from the TSPLIB traveling salesman library.

Key words: integer programming; cutting plane; Gomory cuts
History: received March 2008; revised February 2009; accepted March 2009.