Mixed Integer Reformulations of Integer Programs and the Affine\n TU-dimension of a Matrix

We study the reformulation of integer linear programs by means of a mixed\ninteger linear program with fewer integer variables. Such reformulations can be\nsolved efficiently with mixed integer linear programming techniques. We exhibit\nexamples that demonstrate how integer programs can be reformulated using far\nfewer integer variables. To this end, we introduce a generalization of total\nunimodularity called the \\emph{affine TU-dimension} of a matrix and study\nrelated theory and algorithms for determining the affine TU-dimension of a\nmatrix. We also present bounds on the number of integer variables needed to\nrepresent certain integer hulls.\n