Mixing mixed-integer inequalities

Citation
O. Gunluk et Y. Pochet, Mixing mixed-integer inequalities, MATH PROGR, 90(3), 2001, pp. 429-457
Citations number
26
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
3
Year of publication
2001
Pages
429 - 457
Database
ISI
SICI code
0025-5610(200105)90:3<429:MMI>2.0.ZU;2-Z
Abstract
Mixed-integer rounding (MIR) inequalities play a central role in the develo pment of strong cutting planes for mixed-integer programs. In this paper, w e investigate how known MIR inequalities can be combined in order to genera te new strong valid inequalities. Given a mixed-integer region S and a collection of valid "base" mixed-integ er inequalities, we develop a procedure for generating new valid inequaliti es for S. The starting point of our procedure is to consider the MIR inequa lities related with the base inequalities. For any subset of these MIR ineq ualities, we generate two new inequalities by combining or "mixing" them. W e show that the new inequalities are strong in the sense that they fully de scribe the convex hull of a special mixed-integer region associated with th e base inequalities. We discuss how the mixing procedure can be used to obtain new classes of st rong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facili ty location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we s tudy some extensions of this mixing procedure.