Network Formulations of Mixed-Integer Programs

We consider mixed-integer sets of the type MIX TU = {x : Ax amp;#8805; b; xi integer, i amp;#8712; 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 MIX TU 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 MIX 2TU, we provide an extended formulation for the convex hull of MIX 2TU 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(MIX 2TU). When this number is polynomial in the dimension of the matrix A, the formulation is of polynomial size and the optimization problem over MIX 2TU 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 MIX 2TU 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