In order to introduce the main result and also provide

some background material, we require some notation. Let

A= (aij )∈Zm×nwith m<nand let τ={i1, . . . , ik} ⊂

{1, . . . , n}with i1<··· < ikbe an index set. We will use

the notation Aτfor the m×ksubmatrix of Awith columns

indexed by τ. In a similar manner, given x∈Rn, we will

denote by xτthe vector (xi1,...,xik)T. The complement of

τin {1, . . . , n}will be denoted by ¯τ={1, . . . , n}\τ. We

will say that τis a basis if |τ|=mand the submatrix Aτis

nonsingular. In the scenario that τis a basis, we will replace τ

by γ. Further, denote by ∆(A)the maximum absolute valued

m-dimensional subdeterminant of A, namely

∆(A) = max{|det(Aτ)|:τ⊂ {1, . . . , n}with |τ|=m}.

If ∆(A)is positive, the notation gcd(A)will denote the great-

est common divisor of all m-dimensional subdeterminants of

the matrix A.

We assume without loss of generality that A∈Zm×n

with m<nhas full rank mand let b∈Zm. Consider the

polyhedron

P=P(A, b) = x∈Rn

≥0:Ax=b.

Upon further assuming that Pis nonempty, we take any vertex

x∗of P. Since Ahas rank mby assumption, it follows that

there exits a basis γof A such that

x∗

γ=A−1

γband x∗

¯γ=0.(1)

It is worth noting that in general, given a vertex x∗of P, the

basis γneed not be unique, however, if one assumes that x∗

is nondegenerate, i.e. exactly mof the x∗

i’s are nonzero, then

there is indeed a unique choice for the basis γ.

We will estimate the ℓ∞-distance from a vertex x∗of the

polyhedron P, which is given by a basis γas in (1), to the set

of its (feasible) lattice points z∈P∩Zn. It is worth noting

that bounds of this form provide information regarding the

level of accuracy when one “relaxes” an integer program (IP)

and instead solves the related linear program (LP). This type

of relaxation is often (see e.g. [6, Section 11.5]) implemented

since solving the decision version of an IP is in general NP-

complete (see e.g. [12, Chapter 18]), however, it is well-known

that one can solve an LP in polynomial time via the ellipsoid

[9] or the interior-point method [8].

Before stating our result, we recall some of the upper

bounds on the distance from a vertex x∗of Pto the set of

its lattice points z∈P∩Zn. For this purpose, let us assume

that Pis integer feasible, i.e. that P∩Zn=∅. The classical

sensitivity theorem of Cook et al. [4] implies that

∥x∗−z∥∞≤n·∆(A)(2)

holds. Eisenbrand and Weismantel [5] improved on this clas-

sical bound through a novel use of Steinitz Lemma [14] in

order to demonstrate that

∥x∗−z∥1≤m(2m∥A∥∞+ 1)m

holds, where ∥A∥∞= maxi,j |aij |is the maximum absolute

entry of A. Lee et al. [10] utilise bounds on the sparsity of

feasible integer points to show that

∥x∗−z∥1<3m2log 2√m·∆(A)1/m·∆(A)

holds. Lee et al. [11] demonstrate that

∥x∗−z∥1≤m(m+ 1)2·∆3(A)+(m+ 1) ·∆(A)

holds in a slightly more general setting. A very recent strong

improvement over the classical bound of Cook et al. [4]

obtained by Celaya et al. [3] demonstrates that we can replace

nby n/2in (2) provided n≥2. It remains an open

question how tight these bounds actually are. Despite this,

in the knapsack scenario, i.e. when m= 1, upon following

traditional vector notation, Aliev et al. [2] show that

∥x∗−z∥∞≤ ∥a∥∞−1

holds and that this bound is optimal.

Since the main result in this article provides an upper bound

on the ℓ∞-distance from any vertex x∗of Pto the set of its

Finding an Optimal Proximity Bound in a Very Special Scenario

ALED WILLIAMS

Department of Mathematics

London School of Economics and Political Science

London, UK

Abstract—Given A ∈ Zm×n and b ∈ Zm, we provide a sharp upper bound for the ℓ∞-distance from any vertex

of the polyhedron P(A, b) = {x ∈ Rn ≥0 : Ax = b} to a nearby feasible integral point under a strong assumption

regarding the dimensions of the matrix A. It is hoped that this result provides motivation for conducting

further research into providing more such upper bounds under certain additional assumptions.

Keywords: Integer programming, linear programming, optimisation, polyhedron, proximity.

Received: June 29, 2022. Revised: July 29, 2022. Accepted: August 3, 2022. Published: August 3, 2022.

1. Introduction

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.68

Aled Williams

E-ISSN: 2224-2880

600

Volume 21, 2022

lattice points, it is useful to deﬁne (as in [2]) the (maximum)

vertex distance d(A, b)as

d(A, b) = (max

x∗min

z∈P∩Zn∥x∗−z∥∞,if P∩Zn=∅,

−∞,otherwise,

where the maximum is taken over all vertices x∗of the

polyhedron P.

The following theorem provides a sharp upper bound for

the (maximum) vertex distance when n=m+ 1. As stated

in the abstract, it is hoped that this result provides motivation

for conducting further research into ﬁnding more such upper

bounds under additional assumptions. It should be noted that

by sharp we mean that we can construct an example where the

equality appearing in (3) is attained. We provide this example

directly after the statement of the theorem.

Theorem 1. Let A∈Zm×(m+1) with full rank mand b∈Zm.

If P∩Zm+1 =∅, then

d(A, b)≤∆(A)

gcd(A)−1.(3)

The following example demonstrates the sharpness of The-

orem 1 in the case when m= 2. Consider

A=3 11 7

−573and b=154

58 .

The absolute values of the 2×2subdeterminants of Aare

here 76, 44 and 16, respectively. In particular, ∆(A) = 76

and gcd(A)=4. The polyhedron Pis in this case a line

segment connecting x∗

1= (110/19,236/19,0)Tand x∗

(14/11,0,236/11)Tand, in addition, the only feasible integer

point is z= (2,2,18)T. The ℓ∞-norm distances from the two

vertices to zare

∥x∗

1−z∥∞= max 

110

19 −2

,

236

19 −2

,18= 18

and

∥x∗

2−z∥∞= max 

11 −2

,2,

236

11 −18=38

11 ,

respectively. In particular, we have d(A, b) = 18 and simply

noting that

∆(A)

gcd(A)−1 = 76

4−1 = 19 −1 = 18

holds demonstrates that the equality in (3) is attained.

Theorem 1 can be easily applied to estimate the (additive)

integrality gap for an IP with the assumed dimension. Given

A∈Zm×(m+1) with full rank m,b∈Zmand a cost vector

c∈Qn, we now consider the IP

min{cTx:x∈P∩Zm+1}(4)

and assume that (4) is feasible and bounded.

Denote by IP (c, A, b)and LP (c, A, b)the optimal values

of the IP (4) and its linear programming relaxation

min{cTx:x∈P},(5)

respectively. The (additive) integrality gap IG(c, A, b)asso-

ciated with the IP (4) is

IG(c, A, b) = IP (c, A, b)−LP (c, A, b).

Clearly, in this case, we have

IG(c, A, b)≤d(A, b)· ∥c∥1.(6)

Notice that the upper bound (3) is independent of the right-

hand side band, as such, it is possible to bound the integer

programming gap [7]. Given a pair (A, b), the integer pro-

gramming gap is the maximum IG(c, A, b)over all suitable

integral b, namely

Gap(c, A) = max

bIG(c, A, b),

where branges over all integer vectors such that the IP (4) is

feasible and bounded.

As a corollary of Theorem 1, we obtain the following upper

bound on the integer programming gap under the current

assumptions.

Corollary 1. Let A∈Zm×(m+1) with full rank m,b∈Zm

and c∈Qn. If P∩Zm+1 =∅, then

Gap(c, A)≤ ∆(A)

gcd(A)−1!· ∥c∥1.

The proof of this corollary follows immediately from (6)

and the statement of Theorem 1.

In order to simply the notation slightly during the proof of

the main result, we let Λ = Λ(A, b)denote the afﬁne lattice

in Rm+1 formed by taking integer points in the (afﬁne) ﬂat

that is described by the linear system Ax=b, namely

Λ = Λ(A, b) = x∈Rm+1 :Ax=b∩Zm+1.

Further, let π(·) : Rm+1 →Rdenote the projection onto the

ﬁnal coordinate, i.e. the projection which forgets about the ﬁrst

mcoordinates.

Proof. Reordering the columns of the matrix Aif necessary,

we may assume without loss of generality that

γ={1,2, . . . , m},

i.e. that A= (Aγ, A¯γ), where det(Aγ)= 0 . It should be

noted that A¯γis here an m-dimensional column vector. The

polyhedron Pcan be written as

P=nx∈Rm+1

≥0:Aγxγ+A¯γx¯γ=bo,

where x= (xγ, x¯γ)T, i.e. xγ∈Rmand x¯γ=xm+1 ∈R

contain the entries of the vector xcorresponding to Aγand

A¯γ, respectively. In this case, the conditions (1) on x∗become

x∗

γ=A−1

γband x∗

¯γ=x∗

m+1 = 0 .

2. Proof of Theorem 1

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.68

Aled Williams

E-ISSN: 2224-2880

601

Volume 21, 2022

Further, using Cramer’s Rule (see e.g. [13, Theorem 2.20]),

the vertex x∗has the form

x∗= det A1

γ(b)

det (Aγ),...,det Am

γ(b)

det (Aγ),0!T

,(7)

where Ai

γ(b)denotes the submatrix Aγwhose i-th column

has been replaced by b. Observe that if the polyhedron Pis

bounded, then Pis a line segment in Rm+1 connecting its

two vertices. If instead Pis unbounded, then the polyhedron

Pis a ray in Rm+1, where x∗is the only vertex of P.

Recall that we are upper bounding the distance with respect

to the ℓ∞-norm from the vertex x∗to some (feasible) integral

point. We denote such an integral point by

z= (z1, . . . , zm+1)T∈P∩Zm+1.

Further, we assume for technical reasons that zis the feasible

lattice point with minimal ﬁnal entry. In other words, we

assume the lattice point zis the closest (feasible) integral

point to the vertex x∗in the xm+1-th coordinate direction

with respect to the ℓ∞-norm.

Note that by the form (7) of the vertex x∗, its projection is

π(x∗)=0. Firstly, we upper bound

∥π(x∗)−π(z)∥∞=zm+1

before “lifting” to a (feasible) lattice point in Rm+1. Recall

that Λdenotes the afﬁne lattice in Rm+1 containing all integer

points which satisfy Ax=b. In particular, its projection π(Λ)

is a one-dimensional afﬁne lattice which, in light of [1, Lemma

10], has determinant

det(Λ) = |det(Aγ)|

gcd(A).

It follows that all projected afﬁne lattice points from π(Λ)

belong to the same congruence class. Further, upon noting that

the least residue in this congruence class is one of the integers

{0,1,...,det(Λ)−1}, it follows since zis by assumption the

closest to the vertex x∗in the ﬁnal coordinate direction that

π(z)satisﬁes

π(z) = zm+1 ≤det(Λ) −1 = |det(Aγ)|

gcd(A)−1.(8)

Observe that if one ﬁxes the value of zm+1, then the

corresponding m-dimensional integer solution zγis uniquely

determined by

zγ=A−1

γb−A¯γzm+1

since the submatrix Aγis nonsingular by assumption. In order

to simplify subsequent notation, we let

b=b−A¯γzm+1.

In particular, using Cramer’s Rule, for ﬁxed zm+1, the corre-

sponding m-dimensional integral solution zγis given by

zγ= (z1, . . . , zm)T

= det A1

γ(˜

b)

det (Aγ),...,det Am

γ(˜

b)

det (Aγ)!T

.(9)

Further, the m-dimensional solution (9) to the linear system

Aγxγ=˜

bcan be “lifted” to yield a solution to the original

linear system by simply appending the ﬁxed value zm+1 to

the (m+ 1)-th entry. In other words, we can write

z= (z1, . . . , zm, zm+1)T

= det A1

γ(˜

b)

det (Aγ),...,det Am

γ(˜

b)

det (Aγ), zm+1!T

Using (7), the vertex distance is

∥x∗−z∥∞

= max 

det Aj

γ(b)−det Aj

γ(˜

b)

det (Aγ)

, zm+1!,(10)

where 1≤j≤m. Recall (8) and, in particular, clearly

|x∗

m+1 −zm+1|=zm+1 ≤∆(A)

gcd(A)−1

holds as required by (3).

It remains to ﬁnally consider the other differences appearing

in (10). In particular, we consider

|x∗

j−zj|=

det Aj

γ(b)−det Aj

γ(˜

b)

det (Aγ)

(11)

for j∈ {1, . . . , m}. Upon noting that Aj

γ(b)and Aj

γ(˜

b)differ

only by their j-th column and recalling that

b=b−A¯γzm+1

for ﬁxed zm+1, it follows using several fundamental properties

of determinants that (11) can be equivalently expressed as

|x∗

j−zj|=

zm+1 ·det Aj

γ(A¯γ)

|det (Aγ)|

.(12)

It is worth noting that we could alternatively deduce (12)

from (11) by applying Laplace’s expansion formula (see e.g.

[13, Theorem 10.33]) and then performing some algebraic

manipulation.

Upon recalling (8), we can bound (12) by



zm+1 ·det Aj

γ(A¯γ)

|det (Aγ)|

≤det Aj

γ(A¯γ)·1

gcd(A)−1

|det(Aγ)|

(13)

Notice that the matrix Aj

γ(A¯γ)contains only columns from A

and, in consequence,

det Aj

γ(A¯γ)≤∆(A)

holds. Finally, since

gcd(A)≤det (Aγ)≤∆(A)

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.68

Aled Williams

E-ISSN: 2224-2880

602

Volume 21, 2022

holds, it follows that (13) is bounded by

det Aj

γ(A¯γ)·1

gcd(A)−1

|det(Aγ)|

≤

∆(A)·1

gcd(A)−1

∆(A)

=∆(A)

gcd(A)−1,

which implies that (3) holds as required and concludes the

proof of Theorem 1.

[1] Iskander Aliev, Marcel Celaya, Martin Henk, and Aled Williams.

Distance-sparsity transference for vertices of corner polyhedra. SIAM

Journal on Optimization, 31(1):200–216, 2021.

[2] Iskander Aliev, Martin Henk, and Timm Oertel. Distances to lattice

points in knapsack polyhedra. Mathematical Programming, 2019.

[3] Marcel Celaya, Stefan Kuhlmann, Joseph Paat, and Robert Weismantel.

Improving the cook et al. proximity bound given integral valued con-

straints. In Karen Aardal and Laura Sanit`

a, editors, Integer Programming

and Combinatorial Optimization, pages 84–97, Cham, 2022. Springer

International Publishing.

[4] William Cook, Albertus M H Gerards, Alexander Schrijver, and ´

Eva Tar-

dos. Sensitivity theorems in integer linear programming. Mathematical

Programming, 34(3):251–264, 1986.

[5] Friedrich Eisenbrand and Robert Weismantel. Proximity results and

faster algorithms for integer programming using the steinitz lemma.

ACM Transactions on Algorithms (TALG), 16(1):1–14, 2019.

[6] Frederick S Hillier and Gerald J Lieberman. Introduction to Operations

Research. McGraw-Hill, 9th edition, 2009.

[7] Serkan Hos¸ten and Bernd Sturmfels. Computing the integer program-

ming gap. Combinatorica, 27(3):367–382, 2007.

[8] Narendra Karmarkar. A new polynomial-time algorithm for linear

programming. In Proceedings of the sixteenth annual ACM symposium

on Theory of computing, pages 302–311, 1984.

[9] Leonid G Khachiyan. A polynomial algorithm in linear programming.

In Doklady Akademii Nauk, volume 244.5, pages 1093–1096. Russian

Academy of Sciences, 1979.

[10] Jon Lee, Joseph Paat, Ingo Stallknecht, and Luze Xu. Improving prox-

imity bounds using sparsity. In Mourad Ba¨

ıou, Bernard Gendron, Oktay

G¨

unl¨

uk, and A. Ridha Mahjoub, editors, Combinatorial Optimization,

pages 115–127, Cham, 2020. Springer International Publishing.

[11] Jon Lee, Joseph Paat, Ingo Stallknecht, and Luze Xu. Polynomial

upper bounds on the number of differing columns of δ-modular integer

programs. arXiv preprint arXiv:2105.08160, 2021.

[12] Alexander Schrijver. Theory of Linear and Integer Programming. John

Wiley & Sons, 1998.

[13] Igor R Shafarevich and Alexey O Remizov. Linear algebra and

geometry. Springer Science & Business Media, 2012.

[14] Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme.

Journal f¨

ur die reine und angewandte Mathematik, 143:128–176, 1913.

References

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the Creative

Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en_US

WSEAS TRANSACTIONS on MATHEMATICS

DOI: 10.37394/23206.2022.21.68

Aled Williams

E-ISSN: 2224-2880

603

Volume 21, 2022

Acknowledgment

I would like to thank Professor Iskander Aliev for

his comments and feedback in refining the

presented results.