The Support of Integer Optimal Solutions
Iskander Aliev Jesus De Loera Fritz Eisenbrand Timm Oertel Robert Weismantel
math.OC

The genealogical tree of ethanol: gas-phase formation of
  glycolaldehyde, acetic acid and formic acid
    Bertrand Lefloch
    December 30, 2023
======================================================================================================


  

 The support of a vector is the number of nonzero-components. We show that
  given an integral m× n matrix A, the integer linear optimization problem  max{ c^T x : A x =  b,   x≥ 0,   x ∈^n}
  has an optimal solution whose support is bounded by 
  2m  log (2 √(m) A _∞), where A _∞ 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. 




§ INTRODUCTION


We consider the  integer optimization  problem in standard form

    max{ c^T x : A x =  b,   x≥ 0,   x ∈^n},

where A ∈^mn, b ∈^m and c ∈^n.

For convenience, we will assume throughout this paper that Problem (<ref>) is feasible.
We will also assume without loss of generality that the matrix A has full row rank, i.e., (A)=m. 

For a vector x ∈^n, let ( x) := { i ∈{1,…,n}: x_i ≠ 0} denote the support of x.
The main purpose of this paper is to establish lower and and upper bounds on the minimal size of  support of an optimal 
solution to Problem (<ref>) which are polynomial in m and the largest binary encoding length of an entry of A. 
Polynomial support bounds for integer programming <cit.> have been successfully used in many areas such as in logic and  complexity, see <cit.> in the design of efficient polynomial-time approximation schemes <cit.>, in fixed parameter tractability <cit.> and they were an ingredient in the solution of cutting stock with a fixed number of item types <cit.>. These previous bounds however were tailored for the integer feasibility problem only and thus depend on the largest encoding length of a component of the objective function vector if applied to the optimization problem (<ref>).  
We believe that the observation that we lay out in this paper, namely that these bounds are independent of the objective function, will find  further applications in algorithms and complexity. 


Note that the support of an optimal solution of the linear relaxation of (<ref>) is well-understood: if we denote by x^* 
a vertex of the polyhedron P(A,  b):= { x ∈: A x =  b,   x ≥ 0 } that corresponds to the linear optimum, then
from the theory of linear programming we know that x^* is determined by a basis B with x^*_B = A_B^-1 b and
x^*_i = 0 for all i ∈ N:={1,…,n}∖ B. In particular, ( x^*) is bounded by m alone. As we will see in this paper (cf. <cit.>), the story is much
more complicated for integer linear programs.



Throughout this paper log(·) will denote the logarithm with base two and A_∞  will denote the maximum absolute entry of the matrix A.
The first result of this paper shows that Problem <ref> has an optimal solution with support of size not exceeding a bound that only 
depends on m and A_∞ and independent of n. 



There exists  an optimal solution z^* for Problem (<ref>) such that

    |( z^*)|  ≤ m + log(g^-1√((AA^T))) ≤  2mlog(2√(m)A_∞),

where g denotes the greatest common divisor of all m × m minors of A.


This theorem  cannot be directly derived from the statements in <cit.> and <cit.> for the following reason.
To guarantee optimality of y^*, the objective function vector c would have to become part of the constraint matrix (see <cit.>).  
This, however, does not allow us to bound the support solely in terms of A. The resulting bound would have to depend also on c.


Our strategy to prove Theorem <ref> is based on a refinement of the proofs for results established in  <cit.> and <cit.>.
Specifically, in  <cit.> it was shown that there exists an integer point y^*∈ P(A,  b) 
with support bounded by 2m log(4m A_∞). This bound was recently improved in <cit.> to

    |( y^*)| ≤ m + log(g^-1√((AA^T))) .



Notice that an upper bound on the support of an optimal solution in the form of a function in m cannot be expected. 
This would imply that, for fixed  m, one can optimize in polynomial  time by first guessing the support of an optimal 
solution and then finding a solution using Lenstra's algorithm for integer programming in fixed dimension <cit.>. However, also for fixed m, the optimization problem (<ref>) is NP-hard <cit.>. 

The next result of this paper implies that the upper bound established in Theorem <ref> is nearly optimal.
In fact, we consider a more general setting, where we drop the nonnegativity constraints and estimate from below the size of support 
of all integer solutions to a suitable underdetermined system A x= b.
The obtained bound depends only on m and A_∞ and is independent of n and b. 
Under the nonnegativity constraints and provided that m≥ 2, a lower bound can be derived from an example given in <cit.>. 




For any ϵ>0 there exists a natural number N_ϵ such that the following holds.
Let m,n∈, where n/m>N_ϵ.
Then, there exists a matrix A∈^m × n, and a vector b∈^m, such that Problem (<ref>) is feasible and

    |( z)| ≥ mlog(A_∞)^1/1+ϵ,

for all z∈^n with A z= b.



Our main results have three implications that we outline next:

First we consider  the integer hull P_I of the polyhedron P=P(A,  b), i.e., P_I=(P∩^n).
It was proved by Cook et al. <cit.> that for a generic rational polyhedron P the number of vertices of P_I
is bounded by 2m^n(n^2log(A_∞))^n-1.
For polyhedra in standard form Theorem <ref> leads to an upper bound on the number
of vertices of the integer hull of P that is polynomial in n, provided that m is a constant.

To see this, let z^* be a vertex of P_I.
There exists  c∈^n, such that z^* is the unique optimum with respect to Problem (<ref>).
Taking a vertex x^* of P that gives an optimal solution of the corresponding continuous relaxation,
we can associate every vertex of P_I to at least one vertex of P.
Note, that P itself has no more than n^m vertices.
By <cit.>, we can assume that x^*- z^*_1≤ m(2mA_∞+1)^m, where
·_1 denotes the ℓ_1-norm.


From Theorem <ref> it follows that every vertex z^* of P_I has support of size at most 2mlog(2√(m)A_∞).
Thus, P_I has no more  than

    n^m · n^2mlog(2√(m)A_∞)· (m(2mA_∞+1)^m)^2mlog(2√(m)A_∞)

vertices.
Summarizing, we obtain


The number of vertices of the integer hull P_I is bounded by

    (mnA_∞)^O(m^2log(√(m)A_∞)).



A second consequence of Theorem <ref> is the following extension to mixed integer optimization problems.


There exists  an optimal solution z^* for the mixed-integer optimization problem



    max{ c^T x : A x =  b,   x≥ 0,   x ∈^n ×^d},


		such that
	
    |( z^*)| ≤ 2 m + log(g^-1√((AA^T))) ≤  m+2mlog(2√(m)A_∞).



Given a positive integer k, an integer matrix A is called k-modular if all its absolute subdeterminants are bounded by k. Theorem <ref> immediately implies the following result.


Fix a positive integer k. For a k-modular matrix A, Problem (<ref>) has an optimal solution with the size of support bounded by a polynomial in m.




§ PROOFS OF THEOREM <REF> AND THEOREM <REF>


We will describe the refinement of the proofs established in  <cit.> and <cit.>.
In the proofs of both of these results the key idea is to show that if the support of a feasible solution is large, specifically if
the bound (<ref>) is violated, then there exists a certain nonzero integer vector y∈{-1,0,1}^n
in  (A):={ x∈^n: A x=  0}. This vector can then be used to perturb the feasible solution and decrease its support.
We show that if  (<ref>) is violated, then there exists such a vector y that
satisfies additionally c^T  y=0. This allows us to perturb an optimal solution and decrease its support
while remaining optimal. As in <cit.>, we will utilize the following result by Bombieri and Vaaler.


There exist n - m linearly independent integral vectors y_1, …, y_n-m∈(A)∩^n satisfying

    ∏_i=1^n-m y_i_∞≤ g^-1√( det(AA^T)) ,

where g is the greatest common divisor of all m × m subdeterminants of A.




In <cit.> it was verified that the second inequality in (<ref>) always holds.
Therefore we only need to prove that the first inequality in (<ref>) holds.
For that, let z^* be an optimal solution for Problem (<ref>) with minimal support.

First, we argue that it suffices to consider the case |( z^*)|=n.
Suppose that |( z^*)|<n. For S=( z^*) define
A̅=A_S,  the submatrix of A whose columns are labeled by the indices of S.
Let b̅= b, c̅= c_S, and z̅^*= z^*_S.
By removing linearly dependent rows from A̅x̅=b̅, we may assume that A̅ has full row rank. Let m̅ = (A̅) ≤ m.


Observe that  z̅^* is an optimal solution for the corresponding Problem (<ref>) with minimal support.
Furthermore, note that z̅^* has full support.
Now, if (<ref>) holds true for z̅^*, then by <cit.> we have

    |( z^*)|=|(z̅^*)|≤m̅ + g̅^-1√((A̅A̅^T))≤ m + g^-1√((AA^T)),

where g̅ denotes the greatest common divisor of all m̅×m̅ minors of A̅.

From now on, suppose that |( z^*)|=n > m + log(g^-1√((AA^T))). This inequality implies that g^-1√((AA^T))<2^n-m.
By Theorem <ref>, there exists a vector y∈^n∖{ 0} such that

    A y= 0    and    y_∞≤(g^-1√((AA^T)))^1/(n-m)<2.

In particular, this implies that y_i∈{-1,0,1} for all i∈{1,…,n}.
Since z^*_i > 0 for all i ∈{1,…,n}, it follows that z^* +  y and z^* -  y are feasible.
As z^* is optimal, it also follows that c^T y = 0. Otherwise c^T( z^* +  y) or c^T( z^* -  y) would be larger.

We may assume that y_i<0 for at least one i. Otherwise, replace y by - y.
Let λ=min{z^*_i : y_i<0}.
Now, by construction z^* + λ y is an optimal solution to (<ref>) with support strictly smaller than n.
The obtained contradiction completes the proof.



Now we discuss the proof of Theorem <ref>.
Assuming that the columns of A form a Hilbert basis, Cook et al. <cit.> showed that the support of an optimal solution can be bounded solely in terms of m.
In the same article the authors constructed an example showing that such a result cannot hold for more general A. We extend their construction as follows.


Let p_i∈ denote the i-th prime number. The i-th primorial p_i# is defined as the product of the first i prime numbers, that is

    p_i#:=∏_j=1^i p_j.

Based on the Prime Number Theorem (see e.g., <cit.>) the asymptotical growth of primorials is well known to be

    p_i#=e^(1+o(1))iln(i),

where ln(·) denotes the natural logarithm (see <cit.>).



Let k=⌊ n/m ⌋ and let p_1,…,p_k∈ be the first k prime numbers.
We define

    q_i:=p_k#/p_i.

By construction, (q_1,…,q_k)=1.
Thus, there exists a λ∈^k such that ∑_j=1^k λ_j q_j=1.
Since, (q_1,…,q_j-1,q_j+1,…,q_k)=p_j for any j∈{1,…,k}, it
must hold that λ_j≠0 for all j∈{1,…,k}.
We set q̅_j:=-q_j if λ_j<0 and q̅_j:=q_j if λ_j>0.

Now, let A∈^m × n be a matrix with 



    A_ij=q̅_j+k-ik   if  k(i-1)< j ≤ ik,
    
    0   otherwise.


Further, let 1 denote the all-one m-dimensional vector. 
The vector z^*∈^n with entries z_i^*=|λ_i-k⌊ (i-1)/k ⌋| for i∈{1,…,km} and z_i^*=0 for i∈{km+1,…,n} is strictly positive in the first km entries and satisfies A z^* =  1.
So, Problem (<ref>) with b= 1 is feasible.
However, no integer vector z∈^n exists that satisfies A z =  1 and |( z)|<km.

It remains to note that by (<ref>) A_∞=q_1=p_k#/2=1/2e^(1+o(1))kln(k).
Thus, log(A_∞)=log(e)/2(1+o(1))kln(k).
Provided we have chosen N_ϵ sufficiently large, we have log(e)/2(1+o(1))kln(k)≤ k^1+ϵ,
and therefore |( z)| = m  k ≥ m log(A_∞)^1/(1+ϵ).



.3cm

Acknowledgements:  This work was partially supported by NSF grant DMS-1440140, 
while the second author was in residence at the Mathematical Sciences Research Institute in Berkeley, 
California, during the Fall 2017. The second author was also partially supported by NSF grant DMS-1522158.

The third author is supported by the Swiss National Science Foundation
(SNSF) within the project Convexity, geometry of numbers, and
  the complexity of integer programming (Nr. 163071). This work was done in part while the third author was visiting the 
  Simons Institute for the Theory of Computing, partially supported by the DIMACS/Simons Collaboration on 
  Bridging Continuous and Discrete Optimization through NSF grant #CCF-1740425.

The work of the fifth author was supported by an Alexander von Humboldt research award.

plain



