Distances of optimal solutions of mixed-integer programs
Joseph Paat Robert Weismantel Stefan Weltge
math.OC


Isotropic-nematic transition of self-propelled rods in three dimensions
    R. Wittmann
    December 30, 2023
=======================================================================




A classic result of Cook et al. (1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations.

Their bound is given in terms of the number of variables and a parameter Δ, which quantifies sub-determinants of the underlying linear inequalities.

We show that this distance can be bounded in terms of Δ and the number of integer variables rather than the total number of variables.

To this end, we make use of a result by Olson (1969) in additive combinatorics and demonstrate how it implies feasibility of certain mixed-integer linear programs.

We conjecture that our bound can be improved to a function that only depends on Δ, in general.










§ INTRODUCTION


In this paper, we consider the question of bounding distances between optimal solutions of mixed-integer linear programs that only differ in the sets of integer constraints.

Let A ∈^m× n, b ∈^m, and c ∈^n.

For I ⊆{1, …, n} =: [n], consider the mixed-integer linear program


    max { c^⊺ x : Ax ≤ b,   x_i ∈ for all  i ∈ I }.I-MIP


Notice that ([n]-MIP) describes a pure integer linear program and (∅-MIP) describes its standard relaxation, which is a linear program.

Assuming that (I-MIP) has an optimal solution for every I ⊆ [n], we are interested in the following classic question.

Given I,J ⊆ [n] and an optimal solution for (I-MIP), how close is the nearest optimal solution for (J-MIP)?

We measure distance with respect to the maximum norm ·_∞ and focus on bounds that only depend on A, I, and J.


One of the first explicit attempts to obtain such distance bounds can be found in the work of Blair and Jeroslow <cit.>, which was later improved by Cook et al. <cit.>.

To state their result, let Δ = Δ(A) denote the largest absolute value of any determinant of a square submatrix of A.

 
    Let I,J ⊆ [n] such that (J-MIP) has an optimal solution and either I = ∅ or J = ∅.
    
    For every optimal solution w of (I-MIP), there exists an optimal solution z of (J-MIP) such that w-z_∞≤ nΔ.


Observe that Theorem <ref> only refers to situations in which one of the programs considered is the linear program.

For general I, J ⊆ [n], a bound of 2nΔ is obtained using the triangle inequality.

However, for any choice of I and J, their resulting bound depends on Δ and the total number of variables n.

The main purpose of this paper is to strengthen this dependence by showing that n can be replaced by the number of integer variables that appear in the two programs.

 
    Let I,J⊆ [n] with I  J such that (J-MIP) has an optimal solution.
    
    For every optimal solution w of (I-MIP), there exists an optimal solution z of (J-MIP) such that w - z _∞ < |I ∪ J| Δ.


To obtain our result, we make use of a result in additive combinatorics by Olson <cit.> that determines the so-called Davenport constant of certain abelian groups.

We show how Olson's result implies that mixed-integer linear programs of a certain structure have non-zero solutions.

More precisely, we establish the following result, which may be of independent interest.

 
    Let d,k ∈_≥ 1, u^1, …, u^k ∈^d, and α_1,…,α_k ≥ 0.
    
    If ∑_i=1^k α_i ≥ d, then there exist β_i ∈ [0,α_i] for i=1,…,k such that not all β_1, …, β_k are zero and ∑_i=1^k β_i u^i ∈^d.


While the bound in Theorem <ref> depends on the number of integer variables, we are not aware of any pairs of MIPs for which distances between optimal solutions cannot be bounded just in terms of Δ.

For this reason, we state the following conjecture.

 
    There exists a function f : _≥ 1→ such that the following holds.
    
    Let I,J ⊆ [n] such that (J-MIP) has an optimal solution.
    
    For every optimal solution w of (I-MIP), there exists an optimal solution z of (J-MIP) such that w - z _∞≤ f(Δ).


In fact, we believe that f can be chosen to be a linear function.

We conclude this paper by discussing this conjecture and providing some conditions under which it holds.




  §.§.§ Related work


Theorem <ref> was extended to the case of separable quadratic objective functions in <cit.> and later to the more general case of separable convex objective functions in <cit.> and <cit.>.

In <cit.>, it was shown that a closer analysis of the parameter Δ can lead to strengthened results for certain choices of the matrix A.

The proofs of these generalized results are similar to the proof of Theorem <ref>, albeit with additional analysis. 

The proof of Theorem <ref> that is presented in this paper is also similar to the proof of Theorem <ref>, and, consequently, the result can be generalized to the settings of <cit.>, <cit.>, <cit.>, and <cit.> using the techniques presented therein.

However, in order to highlight the importance of the ideas developed in this paper, we prove Theorem <ref> for linear objective functions and omit the additional analysis required for these generalizations. 



We reemphasize that we study how the parameters Δ, I, and J affect distance of mixed-integer programs in inequality form.

For recent developments on how other parameters affect the distance of integer linear programs in standard form, see, e.g. <cit.>.


Interestingly, the Davenport constant was previously used in <cit.> in the context of the dijoins and Woodall's conjecture.



  §.§.§ Outline


We start by reviewing parts of the proof of Cook et al. <cit.> in Section <ref> and show how Lemma <ref> can be applied to obtain Theorem <ref>.

In Section <ref>, we discuss the Davenport constant and the mentioned result by Olson <cit.>, which allows us to prove Lemma <ref>.

Finally, Section <ref> contains a discussion of Conjecture <ref>.







§ THE PROOF OF THEOREM <REF>
 

Our proof of Theorem <ref> follows the strategy developed by Cook et al. <cit.>, but differs in some parts in order to (i) be able to compare solutions of (I-MIP) and (J-MIP) with I,J ∅ directly, and to (ii) improve the bound of Theorem <ref>.

For instance, we bypass the use of strong linear programming duality in <cit.>, which restricted one of the sets I, J to be the empty set.


    Without loss of generality, we assume that I ∪ J = [d], where d ∈ [n].
    
    Let w ∈^n be an optimal solution of (I-MIP).
    
    Choose any z̃∈^n that is an optimal solution of (J-MIP) and define y := z̃ - w.
    
    Partitioning the rows of A into submatrices A_1, A_2 such that A_1 y < 0 and A_2 y ≥ 0, we define the cone
    
    
    C := { x ∈^n : A_1 x ≤ 0,   A_2 x ≥ 0 }.

    
    Note that C is defined by an integral matrix arising from A by multiplying some of its rows by -1.
    
    By standard arguments involving Cramer's rule, there exist integer vectors v^1,…,v^k ∈^n such that
    
    
    C = {λ_1 v^1 + … + λ_k v^k : λ_1,…,λ_k ≥ 0 },

    
    and v^i_∞≤Δ for i = 1,…,k.
    
    Observe that y ∈ C, and hence, there exist λ_1,…,λ_k ≥ 0 such that
    
    
    y = λ_1 v^1 + … + λ_k v^k.

    
    Consider the set
    
    
    G := { (γ̅_1,…,γ̅_k) : γ̅_i ∈ [0,λ_i]  for all  i ∈ [k],  γ̅_1 v^1 + … + γ̅_k v^k ∈^d ×^n - d},

    
    which is non-empty (it contains the all-zero vector) and compact.
    
    Thus, there exists some (γ_1,…,γ_k) ∈ G maximizing γ̅_1 + … + γ̅_k over G.
    
    Recalling that y = z̃ - w = ∑_i = 1^k λ_i v^i, we define the vectors 
    
    
    z := z̃ - ∑_i=1^k γ_i v^i = w + ∑_i=1^k (λ_i - γ_i) v^i

    
    and
    
    
    w̃ := w + ∑_i=1^k γ_i v^i = z̃ - ∑_i=1^k (λ_i - γ_i) v^i.

    
    
    First, we claim that z is feasible for (J-MIP) and w̃ is feasible for (I-MIP).
    
    To see this, observe that the coordinates of z indexed by J are integer since this is the case for z̃, (γ_1, …, γ_k)∈ G, and J ⊆ [d].
    
    Similarly, the coordinates of w̃ indexed by I are integer.
    
    Furthermore, by the definition of C, we see that
    
    
    [                         A_1z                            =  A_1w+∑_i=1^k(λ_i-γ_i)A_1v^i                            ≤                         A_1w                            ≤                          b_1;                         A_2z                            =      A_2z̃-∑_i=1^kγ_i A_2v^i                            ≤                        A_2z̃                            ≤                          b_2;                        A_1w̃                            =        A_1w+∑_i=1^kγ_iA_1v^i                            ≤                         A_1w                            ≤                          b_1;                        A_2w̃                            = A_2z̃-∑_i=1^k(λ_i-γ_i)A_2v^i                            ≤                        A_2z̃                            ≤                         b_2, ]

    which shows that Az ≤ b and Aw̃≤ b.


    Second, we claim that z is optimal for (J-MIP).
    
    Indeed, since w is optimal for (I-MIP), we must have
    
    
    c^⊺ w ≥ c^⊺w̃ = c^⊺ w + c^⊺(∑_i=1^k γ_i v^i).

    
    Hence, c^⊺ (∑_i=1^k γ_i v^i )≤ 0.
    
    This yields
    
    
    c^⊺ z = c^⊺z̃ - c^⊺(∑_i=1^k γ_i v^i )≥ c^⊺z̃.

    
    Since z̃ is optimal for (J-MIP), the latter inequality implies that z is also an optimal solution for (J-MIP).
    
    The distance from z to w can be bounded as follows:
    
    
    w-z_∞
            = ∑_i=1^k (λ_i - γ_i) v^i _∞≤∑_i=1^k (λ_i - γ_i) v^i_∞≤∑_i=1^k (λ_i - γ_i) Δ .

    
    
    It remains to argue that ∑_i=1^k (λ_i - γ_i) < d.
    
    To this end, let us assume the contrary.
    
    Defining α_i := λ_i - γ_i ≥ 0 for each i ∈ [k], this means that ∑_i=1^k α_i ≥ d.
    
    Thus, defining u^i ∈^d to be the projection of v^i onto the first d coordinates, we can invoke Lemma <ref> to obtain β_1,…,β_k with β_i ∈ [0,α_i] for each i ∈ [k] such that not all β_1,…,β_k are zero and ∑_i=1^k β_i u^i ∈^d.
    
    Observe that ∑_i=1^k β_i v^i ∈^d ×^n - d.
    
    For each i ∈ [n], define γ_i' := γ_i + β_i ≥ 0 and note that γ_i' ≤γ_i + α_i = λ_i.
    
    Furthermore, we have
    
    
    ∑_i=1^k γ_i' v^i = ∑_i=1^k γ_i v^i_∈ ^d ×^n - d + ∑_i=1^k β_i v^i_∈ ^d ×^n - d∈^d ×^n - d,

    
    and so (γ_1',…,γ_k') ∈ G.
    
    However, since not all β_1,…,β_k are zero, γ'_1 + … + γ'_k > γ_1 + … + γ_k, which contradicts the maximality of (γ_1,…,γ_k).
    







§ THE DAVENPORT CONSTANT AND THE PROOF OF LEMMA <REF>
 

We reduce the proof of Lemma <ref> to a problem in additive combinatorics about the Davenport constant of certain abelian groups.


    Let G be a finite abelian (additive) group.
    
    The Davenport constant of G is the smallest k ∈_≥ 1 such that for every (not necessarily distinct) elements g^1, …, g^k∈ G, there exists a non-empty set I ⊆ [k] such that ∑_i ∈ I g^i = e, where e is the identity element of G.


While determining the Davenport constant of a general abelian group is an open problem, Olson <cit.> provided a tight answer for the case of so-called p-groups.

A special case of his result reads as follows.

 
    Let d,p ∈_≥ 1 with p prime.
    
    The Davenport constant of ^d / p^d is pd - d + 1.


 
    Let d,p ∈_≥ 1 with p prime.
    
    Let f^1, …, f^r ∈^d such that r ≥ pd - d + 1.
    
    Then there exists a non-empty set I ⊆ [r] such that ∑_i ∈ I f^i ∈ p^d.



    By removing any vectors u^i such that α_i =0, we assume that α_i > 0 for all i ∈ [k].
    
    We split the proof into two cases.
    
    
    First, assume that there exists a prime p such that for each i∈ [k], there is some q_i ∈_≥ 0 such that α_i = q_i / p.
    
    Consider the list
    
    
    u^1, …, u^1_q_1  copies, u^2, …, u^2_q_2  copies, …, u^k, …, u^k_q_k  copies

    
    consisting of r := q_1 + … q_k = p (α_1 + … + α_k ) many vectors in ^d.
    
    The inequality ∑_i=1^kα_i ≥ d holds by assumption, so r ≥ p d ≥ pd - p + 1.
    
    Hence, by Corollary <ref>, we obtain ℓ_1,…,ℓ_k with ℓ_i ∈{0,…,q_i} for i = 1,…,k such that not all ℓ_1,…,ℓ_k are zero and ∑_i=1^k ℓ_i u^i ∈ p ^d.
    
    Defining β_i := ℓ_i / p, we obtain ∑_i=1^k β_i u^i ∈^d, where β_i ∈ [0,α_i] for each i = 1,…,k, and not all β_1, …, β_k are zero.
    
    The values β_1, …, β_k prove the desired result in this first case.


    The case of general α_1,…,α_k is handled by a limit argument.
    
    The vector (α_1,…,α_k) can be approximated using fractions with prime denominators in the following way.
    
    For each j ∈_≥ 1 there exists a prime p_j and integers q_1,j,…,q_k,j∈_≥ 0 with q_i,j/p_j ∈ [α_i, α_i + 1/j] for all i ∈ [k].
    
    By construction,
    
    
    lim_j →∞ (q_1,j / p_j,…,q_k,j / p_j) = (α_1,…,α_k).

    
    By the previous case, for each j ∈_≥ 1 there exist β_1,j,…,β_k,j with β_i,j∈ [0,q_i,j/p_j] such that not all β_1,j,…,β_k,j are zero and ∑_i=1^k β_i,j u^i ∈^d.
    
    Since the sequence (β_1,j,…,β_k,j) (j ∈_≥ 1) is contained in the compact set [0,α_1 + 1] ×…× [0,α_k + 1], it contains a convergent subsequence.
    
    Thus, we assume that the limit
    
    
    lim_j →∞ (β_1,j,…,β_k,j) =: (β_1,…,β_k)

    
    exists.
    
    For each i ∈ [k], the fact that lim_j →∞ q_i,j/p_j = α_i together with β_i,j∈ [0,q_i,j/p_j] for all j ∈_≥ 1 implies that β_i ∈ [0,α_i].
    
    Also, as there are only finitely many points in ^d of the form ∑_i=1^k γ_i u^i with γ_i ∈ [0, α_i + 1] for each i ∈ [k], there exists some point z ∈^d such that
    
    
    β_1,j u^1 + … + β_k,j u^k = z

    
    holds for infinitely many j ∈_≥ 1.
    
    This implies that β_1 u^1 + … + β_k u^k = z ∈^d.
    
    If β_1, …, β_k are not all zero, then they prove the desired result. 

    Otherwise, β_1 = … = β_k = 0, so z = 0.
    
    Choose any j ∈_≥ 1 that satisfies (<ref>) and consider the vector (εβ_1,j,…,εβ_k,j), where ε > 0 is chosen such that εβ_i,j∈ [0,α_i] holds for all i ∈ [k].
    
    Note that ε exists since all α_i are assumed to be positive.
    
    Not all components of (εβ_1,j,…,εβ_k,j) are zero and 
    
    
    εβ_1,j u^1 + … + εβ_k,j u^k
            = ε (β_1,j u^1 + … + β_k,j u^k)
            = ε z
            = 0 ∈^d.

    
    Thus, the values εβ_1,j,…,εβ_k,j prove the desired result.
    







§ BOUNDING DISTANCE IN TERMS OF Δ
 

We remark that all bounds discussed in this paper actually hold for arbitrary (not necessarily integer) right-hand sides b.

A simple example given in <cit.> shows that the bound of n Δ is best-possible when comparing (∅-MIP) and ([n]-MIP) for arbitrary b.

However, that example relies on the purely fractional components of b, which may disappear after standard preprocessing of a linear integer program.

Assuming that b is integral, the following example shows that the distance depends at least linearly on Δ.



For δ∈_≥ 1, define


    A = [ -δ  0;  δ -1 ],
          
        b = [ -1;  0 ],
          
        c = [  0; -1 ].


Here, Δ = δ.

The point w = (1/δ, 1)^⊺ is the unique optimal solution to solution of (∅-MIP), and the point z = (1, δ) is the unique optimal solution of both ({1}-MIP) and ({1,2}-MIP).

For J∈{{1}, {1,2}} and any optimal solution w of (∅-MIP), the closest optimal solution z of (J-MIP) satisfies z-w_∞ =  δ -1 = Δ -1. ♢



We are not aware of any pairs of MIPs for which distances between optimal solutions cannot be bounded just in terms of Δ.

For this reason, we believe that the distance bounds provided in this paper can be improved to a function that only depends on Δ, see Conjecture <ref>.

A case in which this conjecture holds is given by the following statement.

 
    Assume that Δ≤ 2.
    
    Let I,J ∈{∅, [n]} such that (J-MIP) has an optimal solution.
    
    For every optimal solution w of (I-MIP), there exists an optimal solution z of (J-MIP) such that w-z_∞≤Δ.


For the proof of Proposition <ref>, we use the following properties of so-called bimodular systems.

Unfortunately, similar results are unknown for matrices with Δ≥ 3, and in future research, any similar results may be useful in extending Proposition <ref> to general Δ.

 
    Let A ∈^m × n, b ∈^m, c ∈^n with (A) = n such that the absolute value of any determinant of an n × n-submatrix of A is at most 2.
    
    Let x^* be a vertex of P := { x ∈^n : Ax ≤ b } and let Q be the convex hull of integer points satisfying all inequalities of Ax ≤ b that are tight at x^*.
    
    Then
    
    
        
  *  every vertex of Q lies on an edge of P that contains x^*, and 
        
        
  *  every edge of P that contains x^* and some integer point, contains an integer point y^* with x^* - y^*_∞≤ 1.
    






Let w ∈^n be an optimal solution of (I-MIP) and let 


    P := { x ∈^n : Ax ≤ b } .



We may assume that P is bounded.

Indeed, there exists some U∈_≥ 1 such that the polytope

P ∩{x∈^n : -U ≤ x_i ≤ U ∀ i∈ [n]}

contains w and an optimal solution of (J-MIP).

It is sufficient to find an optimal solution z of (J-MIP) contained in this polytope such that w-z_∞≤Δ. 

Also, the value of Δ for this polytope equals the value of Δ for P.

Therefore,
by replacing P with this polytope, we assume that P is bounded.

Since P is non-empty and bounded, it follows that (A) = n.



We split the remainder of the proof into four cases.



    Case 1: Assume that I = ∅, J = [n], and w is a vertex of P.

    
    Assume that w ∈^n. It follows that w is an optimal solution of ([n]-MIP). 
    
    Thus, setting z = w gives the desired bound w - z_∞ = 0 ≤Δ-1 ≤Δ.
    
    
    Assume that w∉^n. 
    
    Since w is a vertex of P, it must be the case that Δ = 2 (otherwise, A is totally unimodular, so w∈^n).
    
    Let Q be defined as in Lemma <ref> and let z' ∈^n be a vertex of Q maximizing x ↦ c^⊺ x.
    
    By Lemma <ref> <ref>, z' lies on an edge E of P that contains w.
    
    There is some z ∈^n ∩ E such that z-w_∞≤z̅ - w_∞ for all z̅∈^n∩ E. 
    
    
    The point z is in P and, by the optimality of w and z', it follows that z is optimal for ([n]-MIP).
    
    By Lemma <ref> <ref>, we obtain the desired result w - z_∞≤ 1 ≤Δ -1 ≤Δ.
    
    
    
    Note that the optimal ([n]-MIP) solution z satisfies w - z_∞≤Δ - 1 in Case 1.

    

Case 2: Assume that I = ∅ and J = [n].
    
    
    Let F ⊆ P be the face of all optimal solutions of (∅-MIP) and let z' be an optimal solution of ([n]-MIP).
    
    Set B:= {x∈^n : w_i≤ x_i ≤w_i ∀ i∈ [n]} and let w' be a vertex of B∩ F.
    
    By construction of B, it follows that w-w'_∞≤ 1.
    
    
    Define the index sets
    
    
    [                                   K_1                                    := {i ∈ [n] : z_i ≤w_i and  w'_i = w_i},;                                   K_2                                    := {i ∈ [n] : z_i ≥w_i and  w'_i = w_i},;                                   K_3                                    := {i ∈ [n] : z_i ≤w_i and  w'_i = w_i},;                                   K_4                                    := {i ∈ [n] : z_i ≥w_i and  w'_i = w_i}, ]

    
    and the polytopes
    
    
    [                                        P_1                                         :=       { x∈^n : x_i ≤w_i for all  i ∈ K_1},;                                        P_2                                         :=      { x∈^n : x_i ≥w_i for all  i ∈ K_2 },;                                        P_3                                         := { x∈^n : x_i ≤w_i for all  i ∈ K_3 },  and;                                        P_4                                         :=      { x∈^n : x_i ≥w_i for all  i ∈ K_4 }. ]

    
    The polyhedron P̃:= P ∩ P_1 ∩ P_2 ∩ P_3 ∩ P_4 is non-empty, as it contains w' and z', and is bounded since it is contained in P, which itself is bounded. 
    
    Also, every inequality of B∩ F that is tight at w' is present (up to multiplication by -1) as an inequality defining P̃. 
    
    Hence, w' is a vertex of P̃.
    
    
    Note that P̃ can be described by an integral inequality system whose coefficient matrix has rank equal to n and whose largest absolute value of a subdeterminant is equal to Δ.
    
    Thus, by Case 1, there is an integer point z ∈P̃ that maximizes x ↦ c^⊺ x over P̃∩^n such that w' - z_∞≤Δ - 1.
    
    Since z' and z are both in P̃ and z' is optimal for ([n]-MIP), the vector z is also optimal for ([n]-MIP).
    
    Furthermore, w - z_∞≤w - w'_∞ + w' - z_∞≤ 1 + (Δ - 1) = Δ.
    
    
    

Case 3: Assume that I = [n], J = ∅, and w is a vertex of { x ∈^n : Ax ≤ b }.
   
    
    Assume that Δ = 1. Hence, A is a totally unimodular matrix, so w is also an optimal solution of (∅-MIP). 
    
    Setting z = w, we obtain the desired result w - z_∞ = 0 ≤Δ.
    

    Assume that Δ = 2.
    
    The vector w is a vertex of the polytope R := { x ∈^n : Ax ≤ b }, so there exists a vector d∈^n such that 
    
    {x∈ R : d^⊺ x ≥ d^⊺x̃ ∀ x̃∈ R} = {w}.   
    
    Let F ⊆ P be the face of all optimal solutions of (∅-MIP).
    
    Choose λ≥ 0 large enough so that there exists a vertex x^* ∈ F that maximizes x ↦ (λ c + d)^⊺ x over P.
    
    Setting c̃ := λ c + d, for every point x ∈ R ∖{w} we have
    
    
    c̃^⊺ x
            = λ c^⊺ x + d^⊺ x
            < λ c^⊺ x + d^⊺ w
            ≤λ c^⊺ w + d^⊺ w
            = c̃^⊺ w,

    
    where the first inequality follows from the definition of d and the second inequality from the optimality of w.
    
    In other words, the point w is the unique maximizer of x ↦c̃ x over R.


    Given x^*, define Q as in Lemma <ref>.
    
    There exists a vertex v of Q that maximizes x ↦c̃ x over Q.
    
    Note that v∈^n. 
    
    By Lemma <ref> <ref>, v lies on an edge E of P that contains x^*. 
    
    Thus, v maximizes x ↦c̃ x over R. 
    
    Since w is the unique maximizer of this function over R, it follows that w = v. 
    
    In particular, w lies on the edge E of P that contains x^*. 
    

    Now, consider again the objective function x↦ c^⊺ x. 
    
    If c^⊺ x^* > c^⊺ w, the open line segment from x^* to w does not contain integer points.
    
    Hence, by Lemma <ref> <ref>, x^* - w_∞≤ 1.
    
    Set z = x^* to obtain the desired result z - w_∞≤ 1 ≤Δ.
    
    If c^⊺ x^* = c^⊺ w, then w is optimal for (∅-MIP).
    
    Setting z = w, we arrive at the desired result z - w_∞ = 0 ≤Δ.

    

Case 4: Assume that I = [n] and J = ∅.
    
    Since P is bounded, there exist vertices v^1, …,v^t of { x ∈^n : Ax ≤ b } and coefficients λ_1,…,λ_t > 0 with λ_1 + … + λ_t = 1 such that w = ∑_j=1^t λ_j v^j.
    
    Note that v^1,…,v^t are all optimal solutions for ([n]-MIP).
    
    Thus, by Case 3, for each j ∈ [t] there exists a point z^j that is optimal for (∅-MIP) with v^j - z^j_∞≤Δ.
    
    Define z := ∑_j=1^t λ_j z^j.
    
    The point z is also an optimal solution for the (∅-MIP) and satisfies
    
    
    w - z_∞
            = ∑_j=1^t λ_j (v^j - z^j)  _∞≤∑_j=1^t λ_j  v^j - z^j _∞
    ≤∑_j=1^t λ_j Δ
            = Δ.

    







§ ACKNOWLEDGEMENTS


The authors would like to thank Ahmad Abdi for referring us to <cit.>, where Olson's result was previously used. The second author was supported by the Alexander von Humboldt Foundation.





spmpsci

