This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Conforti, M. Articles by Wolsey, L. A. Search for Related Content

Network Formulations of Mixed-Integer Programs

Dipartimento di Matematica Pura ed Applicata, Università degli Studi di Padova. 35121 Padova, Italy
Center for Operations Research and Econometrics, Université catholique de Louvain, 1348 Louvain-la-Neuve, Belgium
École Polytechnique Fédérale de Lausanne, Institute of Mathematics, CH-1015 Lausanne, Switzerland
Center for Operations Research and Econometrics, Université catholique de Louvain, 1348 Louvain-la-Neuve, Belgium
conforti{at}math.unipd.it
marco.disumma{at}uclouvain.be
friedrich.eisenbrand{at}epfl.ch
laurence.wolsey{at}uclouvain.be

We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of checking nonemptiness of a set of this type is NP-complete, even in the case in which the linear system describes mixed-integer network flows with half-integral requirement on the nodes.

This is in contrast to the case in which A is totally unimodular and contains at most two nonzeros per row. In this case, we provide an extended formulation for the convex hull of solutions whose constraint matrix is a dual-network matrix with an integral right-hand-side vector. The size of this formulation depends on the number of distinct fractional parts taken by the continuous variables in the extreme points of the convex hull of the given set. When this number is polynomial in the dimension of A, the extended formulation is of polynomial size. If, in addition, the corresponding list of fractional parts can be computed efficiently, then our result provides a polynomial algorithm for the optimization problem over these sets. We show that there are instances for which this list is of exponential size, and we also give conditions under which it is short and can be efficiently computed.

Finally, we show that these results provide a unified framework leading to polynomial-size extended formulations for several generalizations of mixing sets and lot-sizing sets studied in the last few years.

Key Words: mixed-integer programming; compact extended formulations
History: Received: December 4, 2006; revision received: March 18, 2008;