Numerically safe gomory mixed-integer cuts

William Cook, Sanjeeb Dash, Ricardo Fukasawa, Marcos Goycoolea

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)641-649
Number of pages9
JournalINFORMS Journal on Computing
Volume21
Issue number4
DOIs
StatePublished - Sep 2009

Keywords

  • Cutting plane
  • Gomory cuts
  • Integer programming

Fingerprint

Dive into the research topics of 'Numerically safe gomory mixed-integer cuts'. Together they form a unique fingerprint.

Cite this