Numerically safe gomory mixed-integer cuts

William Cook; Sanjeeb Dash; Ricardo Fukasawa; Marcos Goycoolea

doi:10.1287/ijoc.1090.0324

Numerically safe gomory mixed-integer cuts

William Cook
, Sanjeeb Dash
, Ricardo Fukasawa
, Marcos Goycoolea

Business School

Research output: Contribution to journal › Article › peer-review

26 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 language	English
Pages (from-to)	641-649
Number of pages	9
Journal	INFORMS Journal on Computing
Volume	21
Issue number	4
DOIs	https://doi.org/10.1287/ijoc.1090.0324
State	Published - Sep 2009

Keywords

Cutting plane
Gomory cuts
Integer programming

Access to Document

10.1287/ijoc.1090.0324

Cite this

@article{2cc48001e7d646f684b9f5bca3128fc7,

title = "Numerically safe gomory mixed-integer cuts",

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.",

keywords = "Cutting plane, Gomory cuts, Integer programming",

author = "William Cook and Sanjeeb Dash and Ricardo Fukasawa and Marcos Goycoolea",

year = "2009",

month = sep,

doi = "10.1287/ijoc.1090.0324",

language = "English",

volume = "21",

pages = "641--649",

journal = "INFORMS Journal on Computing",

issn = "1091-9856",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

number = "4",

}

TY - JOUR

T1 - Numerically safe gomory mixed-integer cuts

AU - Cook, William

AU - Dash, Sanjeeb

AU - Fukasawa, Ricardo

AU - Goycoolea, Marcos

PY - 2009/9

Y1 - 2009/9

N2 - 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.

AB - 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.

KW - Cutting plane

KW - Gomory cuts

KW - Integer programming

UR - https://www.scopus.com/pages/publications/70449470353

U2 - 10.1287/ijoc.1090.0324

DO - 10.1287/ijoc.1090.0324

M3 - Article

AN - SCOPUS:70449470353

SN - 1091-9856

VL - 21

SP - 641

EP - 649

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

IS - 4

ER -

Numerically safe gomory mixed-integer cuts

Abstract

Keywords

Access to Document

Fingerprint

Cite this