Network formulations of mixed-integer programs

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.