Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in extended spaces, i.e., if additional variables are allowed. We show that every bounded (hole-free) integer set can be described by an extended integer formulation using at most three non-zero coefficients which are +1 or -1. In the original space, we provide lower bounds on the size of integer formulations with bounded coefficients. For 0/1-problems, we also introduce a technique to compute a tight lower bound on the number of non-zeros of integer formulations in the original space. Moreover, we present statistics on these bounds in small dimensions. Finally, we consider conditions on the representability of integer optimization problems with arbitrary objective function as mixed-integer programs. All results are illustrated by examples.
Citation
TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, June 2017
Article
View On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints