The Support of Integer Optimal Solutions

Abstract

The support of a vector is the number of nonzero-components. We show that given an integral $m\times n$ matrix $A$, the integer linear optimization problem $\max \left\{{\mathbf{c}}^T\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{x}\ge 0,\mathbf{x}\in {\mathbb{Z}}^n\right\}$ has an optimal solution whose support is bounded by $2m\log (2\sqrt{m}\Vert A{\Vert }_{\infty })$, where $\Vert A{\Vert }_{\infty }$ is the largest absolute value of an entry of $A$. Compared to previous bounds, the one presented here is independent on the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.