Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix

Abstract

We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mixed integer linear programming techniques. We exhibit a variety of examples that demonstrate how integer programs can be reformulated using far fewer integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determining the affine TU-dimension of a matrix.We also present bounds on the number of integer variables needed to represent certain integer hulls. Moreover, we introduce a generalization of Total Dual Integrality of a linear inequality system and study related theory. This allows us to prove integrality of solutions to linear inequality systems under additional integrality constraints.