Paper Info
Title
A relax-and-cut framework for Gomory mixed-integer cuts
Abstract
Gomory mixed-integer cuts (GMICs) are widely used in modern branch-and-cut codes for the solution of mixed-integer programs. Typically, GMICs are iteratively generated from the optimal basis of the current linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank-1 GMICs read from a basis of the original LP—the one before the addition of any cut. We adopt a relax-and-cut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast—yet accurate—variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cut-and-branch enumerative framework.
Year
DOI
Venue
2011
10.1007/s12532-011-0024-x
Math. Program. Comput.
Keywords
Field
DocType
Mixed-integer programming,Gomory cuts,Lagrangian relaxation,Relax-and-cut,90C11,90C49,90C57
Integer,Discrete mathematics,Mathematical optimization,Cutting-plane method,Lagrangian,Branch and cut,Integer programming,Linear programming,Lagrangian relaxation,Mathematics
Journal
Volume
Issue
ISSN
3
2
0302-9743
ISBN
Citations 
PageRank 
3-642-13519-6
10
0.57
References 
Authors
23
2
Name
Order
Citations
PageRank
Matteo Fischetti12505260.53
Domenico Salvagnin228921.05