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} \| A \|_\infty)$, where $ \| A \|_\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.
Categories: math.OC