The Support of Integer Optimal Solutions

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{\boldsymbol{c}^T\boldsymbol{x} : A\boldsymbol{x} = \boldsymbol{b}, , \boldsymbol{x}\ge\boldsymbol{0}, ,\boldsymbol{x}\in$\mathbb{Z}$^n\right}$ has an optimal solution whose support is bounded by $2m\log (2\sqrt{m}\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\infty }})$, where $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{\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.