Projected Chvátal–Gomory cuts for mixed integer linear programs |
| |
Authors: | Pierre Bonami Gérard Cornuéjols Sanjeeb Dash Matteo Fischetti Andrea Lodi |
| |
Institution: | (1) IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA;(2) Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;(3) LIF, Faculté des Sciences de Luminy, 13288 Marseille, France;(4) DEI, University of Padova, via Gradenigo 6A, 35131 Padova, Italy;(5) DEIS, University of Bologna, viale Risorgimento 2, 40136 Bologna, Italy |
| |
Abstract: | Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often
gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the
Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose
MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP,
since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this
paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea
is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then
to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts
have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically
be solved in a reasonable amount of computing time.
Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894.
Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n.
FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract
n. FP6-021235-2). |
| |
Keywords: | Mixed integer linear program Chvátal– Gomory cut Separation problem Projected polyhedron |
本文献已被 SpringerLink 等数据库收录! |
|