Combinatorial Benders' Cuts for Mixed-Integer Linear Programming

Gianni Codato () and Matteo Fischetti ()
Additional contact information
Gianni Codato: Department of Information Engineering, University of Padova, via Gradenigo 6/A, I-35100 Padova, Italy
Matteo Fischetti: Department of Information Engineering, University of Padova, via Gradenigo 6/A, I-35100 Padova, Italy

Operations Research, 2006, vol. 54, issue 4, 756-766

Abstract: Mixed-integer programs (MIPs) involving logical implications modeled through big-M coefficients are notoriously among the hardest to solve. In this paper, we propose and analyze computationally an automatic problem reformulation of quite general applicability, aimed at removing the model dependency on the big-M coefficients. Our solution scheme defines a master integer linear problem (ILP) with no continuous variables, which contains combinatorial information on the feasible integer variable combinations that can be “distilled” from the original MIP model. The master solutions are sent to a slave linear program (LP), which validates them and possibly returns combinatorial inequalities to be added to the current master ILP. The inequalities are associated to minimal (or irreducible) infeasible subsystems of a certain linear system, and can be separated efficiently in case the master solution is integer. The overall solution mechanism closely resembles the Benders' one, but the cuts we produce are purely combinatorial and do not depend on the big-M values used in the MIP formulation. This produces an LP relaxation of the master problem which can be considerably tighter than the one associated with original MIP formulation. Computational results on two specific classes of hard-to-solve MIPs indicate that the new method produces a reformulation which can be solved some orders of magnitude faster than the original MIP model.

Keywords: mixed-integer programs; Benders' decomposition; branch and cut; computational analysis (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (104)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0286 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:54:y:2006:i:4:p:756-766

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().