Mixing mixed-integer inequalities

Oktay GüNLüCK and Yves Pochet ()
Additional contact information
Oktay GüNLüCK: School of ORIE, Cornell University, Ithaca, New York
Yves Pochet: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium

No 1998011, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities. Given a mixed-integer region S and a collection of valid 'base' mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or "mixing" them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a mixed integer region associated with the base inequalities. We also study some extensions of this mixing procedure, and discuss how it can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems.

Keywords: mixed integer programming; mixed integer rounding; Gomory mixed integer cuts. (search for similar items in EconPapers)
Date: 1998-01-01
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1998.html (text/html)

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:cor:louvco:1998011

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().