Network formulations of mixed-integer programs

Michele Conforti, Marco Di Summa, Fritz Eisenbrand and Laurence A. Wolsey

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

Abstract: We consider mixed-integer sets of the type M IX T U = {x : Ax b; xi integer, i I}, where A is a totally unimodular matrix, b is an arbitrary vector and I is a nonempty subset of the column indices of A. We show that the problem of checking nonemptiness of a set M IX T U is NP-complete when A contains at most two nonzeros per column. This is in contrast to the case when A is TU and contains at most two nonzeros per row. Denoting the set by M IX 2T U , we provide an extended formulation for the convex hull of M IX 2T U whose constraint matrix is the dual of a network matrix, and with integer right hand side vector. The size of this formulation depends on the number |F | of distinct fractional parts taken by the continuous variables in the extreme points of conv(M IX 2T U ). When this number is polynomial in the dimension of the matrix A, the formulation is of polynomial size and the optimization problem over M IX 2T U lies in P. We show that there are instances for which |F | is of exponential size, and we also give conditions under which |F | is of polynomial size. Finally we show that these results for the set M IX 2T U 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.

Keywords: mixed-integer set; totally unimodular matrix; extended formulation; convex hull; dual of network matrix. (search for similar items in EconPapers)
Date: 2006-12
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2006.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:2006117

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 ().