Redundancies in Linear Systems with two Variables per
Inequality
Komei Fukuda

∗

May Szedlák†

arXiv:1610.02820v1 [cs.DS] 10 Oct 2016

October 10, 2016

Abstract
The problem of detecting and removing redundant constraints is fundamental in
optimization. We focus on the case of linear programs (LPs), given by d variables
with n inequality constraints. A constraint is called redundant, if after its removal,
the LP still has the same feasible region. The currently fastest method to detect all
redundancies is due to Clarkson: it solves n linear programs, but each of them has
at most s constraints, where s is the number of nonredundant constraints.
In this paper, we study the special case where every constraint has at most two
variables with nonzero coefficients. This family, denoted by LI(2), has some nice
properties. Namely, as shown by Aspvall and Shiloach, given a variable xi and a
value λ, we can test in time O(nd) whether there is a feasible solution with xi = λ.
Hochbaum and Naor present an O(d2 n log n) algorithm for solving the feasibility
problem in LI(2). Their technique makes use of the Fourier-Motzkin elimination
method and the earlier mentioned result by Aspvall and Shiloach.
We present a strongly polynomial algorithm that solves redundancy detection in
time O(nd2 s log s). It uses a modification of Clarkson’s algorithm, together with a
revised version of Hochbaum and Naor’s technique. Finally we show that dimensionality testing can be done with the same running time as solving feasibility.

1

Introduction

The problem of detecting and removing redundant constraints is fundamental in optimization. Being able to understand redundancies in a model is an important step
towards improvements of the model and faster solutions.
Throughout we consider linear systems of inequalities of form Ax ≤ b, for A ∈ Rn×d ,
b ∈ Rn , d < n. The j-th constraint, denoted Aj x ≤ bj , is called redundant, if its removal
does not change the set of feasible solutions. By removing Aj x ≤ bj from the system we
∗

Department of Mathematics and Department of Computer Science. Institute of Theoretical Computer Science, ETH Zürich. CH-8092 Zürich, Switzerland. komei.fukuda@math.ethz.ch
†
Department of Computer Science. Institute of Theoretical Computer Science, ETH Zürich. CH-8092
Zürich, Switzerland. may.szedlak@inf.ethz.ch
Research supported by the Swiss National Science Foundation (SNF Project 200021 150055 / 1)

1

get a new system denoted A[n]\{j} x ≤ b[n]\{j} . Assume that Ax ≤ b is feasible, then by
solving the following linear program (LP) we can decide redundancy of Aj x ≤ bj .
maximize
Aj x
subject to A[n]\{j} x ≤ b[n]\{j} .

(1)

Namely, a constraint Aj x ≤ bj is redundant if and only if the optimal solution has value
at most bj .
Let LP (n, d) denote the time needed to solve an LP with n inequalities and d variables. Solving n linear programs of form (1), with running time LP (n, d), is enough
for detecting all redundancies. The currently fastest method is due to Clarkson with
running time O(n · LP (s, d)) [2], where we initially assume an interior point is given.
This method also solves n linear programs, but each of them has at most s variables,
where s is the number of nonredundant variables. Hence, if s  n, this output-sensitive
algorithm is a major improvement.
In general no strongly polynomial time algorithm (polynomial in d and n) to solve
an LP is known. Although the simplex algorithm runs fast in practice, in general it
can have exponential running time [3, 8]. On the other hand the ellipsoid method runs
in polynomial time on the encoding of the input size, but is not practical [7]. A first
practical polynomial time algorithm, the interior-point method, was introcuded in [6],
and has been modified in many ways since.
In this paper we focus on the special case where every constraint has at most two
variables with nonzero coefficients, we denote this family by LI(2). Our main result is
that for a full-dimensional system Ax ≤ b in LI(2) we can detect all redundancies in time
O(nd2 s log s) (see Theorem 2), where we assume that an interior point solution is given.
To our knowledge, this is a first strongly polynomial time algorithm for redundancy
detection in LI(2).
To obtain this running time we use an alternated version of Clarkon’s algorithm,
which solves feasibility problems instead of optimization problems. Moreover our algorithm makes use of a modified version of Hochbaum and Naor’s algorithm, which for a
system in LI(2) finds a feasible point or a certificate for infeasibility in time O(d2 n log n)
[5]. This result is an improvement of Megiddo’s algorithm with running time O(d3 n log n)
[9]. Although their techniques are similar and both rely heavily on [1], the improved
version is much simpler.
We will give a summary of the Hochbaum-Naor Algorithm in Section 4. In Section
5 we will give a stronger version of this algorithm, which decides full-dimensionality
and in the full-dimensional case outputs an interior point. Using this variant of the
algorithm together with our modification of Clarkson’s algorithm we get an output
sensitive, strongly polynomial time redundancy detection algorithm. In Section 6 we
show how the results extend to non-full-dimensional systems (see Theorem 8).
In all cases the preprocessing can also be done in strongly polynomial time. Moreover,
we show that dimensionality testing of a polytope P = {x | Ax ≤ b} can be done with
the same running time as the feasibility testing method of Hochbaum and Naor (see
Corollary 11). Note that for general LP’s one needs to solve up to d optimization
2

problems.
Although in LI(2) one can find a feasible solution fast, it is not known how to find an
optimal solution in strongly polynomial time. For general LPs a standard technique for
converting an optimization problem into a feasibility problem is to use the dual linear
program. However, the dual of a system in LI(2) is generally not in LI(2). If the
objective function is in LI(2), one can apply binary search on the value of the optimal
solution, this gives an algorithm that depends on the input size.
Note that Clarkson’s algorithm relies on finding an optimal solution of a linear program. Since for LI(2) we do not have a fast way to optimize, this is the reason why we
modify the algorithm such that it only solves feasibility problems.

2

Definitions and Preliminaries

As already mentioned in the introduction we throughout consider linear systems of the
form
Ax ≤ b,
where A ∈ Rn×d , b ∈ Rn .
The set of inequalities of Ax ≤ b is denoted by G. A point x∗ ∈ Rd is a feasible
solution or feasible point of Ax ≤ b (or G) if Ax∗ ≤ b. It is called an interior point
solution of Ax ≤ b (or G) if all inequalities are satisfied with strict inequality, i.e.,
Ax∗ < b (where ”<” denotes the componentwise strict inequality). The system Ax ≤ b
(or G) is called feasible if a feasible solution exists, otherwise it is called infeasible. If an
interior point solution exists, the system is called full-dimensional. The system Ax ≤ b
is called k-dimensional if the solution set {x | Ax ≤ b} is k-dimensional.
For a subset S ⊆ [n] := {1, . . . , n} we denote by AS x ≤ bS the subsystem of Ax ≤ b
containing only the inequalities indexed by S. In particular the j-th constraint is denoted
by Aj x ≤ bj . This constraint is called redundant if A[n]\{j} x ≤ b[n]\{j} implies Aj x ≤ bj
or equivalently if there is no solution to the system
A[n]\{j} x ≤ b[n]\{j}
Aj x > bj .
As mentioned in the introduction, we can test redundancy of a constraint Aj x ≤ bj by
solving an LP of form (1).
max ] be the projection of
For a feasible system Ax ≤ b and a variable xi let [xmin
i , xi
the solution space of Ax ≤ b to the xi -axis, we call this the range of xi . This interval is
exactly the set of values of xi for which a solution of the entire system can be constructed.
It is possible that xmin
= −∞ or xmax
= ∞.
i
i
In this paper we are interested in sparse linear systems, in particular the family
LI(2). A linear system is in LI(2), if every constraint has at most two variables with
nonzero coefficients. That means all inequalities have form αxi + βxj ≤ γ for some α,
β, γ ∈ R, α 6= 0.

3

We define the neighbors of xi in G, denoted N (xi , G), as the set of variables xj ,
j ∈ [d] \ {i} for which there exists an inequality in G containing xi and xj with nonzero
coefficients.
The system (Ax ≤ b)|xi =c (or G|xi =c ) is obtained form Ax ≤ b (or G) by substituting
the variable xi by the constant c, it hence has one variable less than the original system.

3

A Strongly Polynomial Time Redundancy Detection Algorithm for Linear Programs with two Variables per Inequality

In this section we will prove our main result, the running time of the strongly polynomial
algorithm to detect all redundancies in LI(2) (see Theorem 2).
nonredundant

redundant
Aj x ≤ bj

Aj x ≤ bj

Aj x ≤ bj

Aj x ≥ bj

Aj x ≥ bj

Aj x ≥ bj

Figure 1: Redundancy Certificates
We make use of the following modified version of Hochbaum and Naor’s result (Theorem 1). We will discuss their original result in Section 4 and the validity of the modification in Section 5. In Section 6 we will discuss how the results extend to non-fulldimensional systems.
Theorem 1. For a system Ax ≤ b in LI(2) one can decide in time O(d2 n log n) whether
the system is full-dimensional, and in the full-dimensional case output an interior point
solution.
Theorem 2. Let Ax ≤ b a full-dimensional system in LI(2). Let z be an interior point
solution of Ax ≤ b and let z  := z + (, . . . , d )T for some  small enough, i.e., z  is
a generic interior point. Then the following algorithm detects all redundancies in time
O(nd2 s log s).

4

Algorithm Modified Clarkson (A,b,z);
begin
R := ∅, S := ∅;
while R ∪ S 6= [n] do
pick any r ∈ [n] \ (R ∪ S) and use Theorem 1 on {AS x ≤ bS , ar x ≥ br };
if AS x ≤ bS , ar x ≥ br not full-dimensional then
R = R ∪ {r};
else let x∗ be an interior point solution of AS x ≤ bS , ar x ≥ br then
S = S ∪ {q}, where q = RayShoot(A, b, z  , x∗ − z  );
endif;
endwhile;
output S;
end.
The function RayShoot(A, b, z, t) returns the index q of a facet-inducing hyperplane {x :
Aq x = bq }, which is hit first by the ray starting at z along the direction of t.
Note that Theorem 1 immediately implies that the interior point z of Theorem 2 can
be found in strongly polynomial time O(nd2 log n). It follows that finding all redundancies and the preprocessing can be achieved in strongly polynomial time.
Using Theorem 1 and the following observation (see also Figure 1) we can prove
Theorem 2.
Observation 3. Let Ax ≤ b be a full-dimensional system in LI(2). Then for j ∈ [n]
the following are equivalent.
1. Aj x ≤ bj is nonredundant in Ax ≤ b.
2. Aj x ≤ bj is facet-inducing for P = {x | Ax ≤ b}.
3. The system A[n]\{j} x ≤ b[n]\{j} , Aj x ≥ bj is full-dimensional.
Proof of Theorem 2. We have to show that the modified Clarkson Algorithm returns
S 0 , the indices of the set of nonredundant constraints. We first discuss correctness of
the algorithm by induction. We claim that in every step S ⊆ S 0 and R ⊆ [n] \ S 0 .
This is trivially true in the beginning. Assume that in some step of the algorithm we
have S ⊆ S 0 , R ⊆ [n] \ S 0 and r ∈ [n] \ (S ∪ R). If AS x ≤ bS , ar x ≥ br is not fulldimensional, then AS 0 x ≤ bS 0 , Ar x ≥ br is not full-dimensional and hence r is redundant
by Observation 3.
If AS x ≤ bS , ar x ≥ br is full-dimensional and x∗ is an interior point, then we do ray
shooting from z  to x∗ . Note that ar x∗ > br , hence x∗ is not in the feasible region of
Ax ≤ b. Then the first constraint hit (with index q) is nonredundant. This constraint
is unique, since z  is generic and x∗ is not a feasible solution. Denote the intersection
point of the hyperplane given by Aq x = bq with the ray by y ∗ . It follows that q ∈
/ S
since Aq y ∗ = bq and we know that AS y ∗ < bS . This proves correctness of the algorithm.
5

It remains to discuss the running time. Since in every round we add either a variable
to S or R, the outer loop is executed n times. In every round we run the Algorithm
of Theorem 1 on at most s inequalities. This takes time O(nd2 s log s) by Theorem 1.
Moreover there are at most s stages of ray shooting which takes O(nds) time in total.
The running time follows.

4

Revision of the Hochbaum-Naor Method

Since we modify Hochbaum and Naor’s Method in the next section, for completeness we
review the basic components and the key ideas of the algorithm.
Theorem 4. [5] For a system Ax ≤ b in LI(2) one can decide whether the problem is
feasible in time O(d2 n log n), and in the feasible case output a solution.
In Section 4.1 we will give all relevant tools to prove the theorem. We then discuss
the feasible case in Sections 4.2 and 4.3, and finally the infeasible case in Section 4.4

4.1

The Ingredients

The Hochbaum-Naor Theorem is a mix of an efficient implementation of the FourierMotzkin method and the result by Aspvall and Shiloach described below [1]. In general
the Fourier-Motzkin method may generate an exponential number of inequalities, however in the LI(2) case one can implement it efficiently.
The Fourier-Motzkin Method (for general LPs) (For more details please refer
to [10, pp. 155 - 156]). Let G be a set of inequalities on the variables x1 , . . . , xd . The
Fourier-Motzkin Method eliminates the variables one by one to obtain a feasible solution
or a certificate of infeasibility. At step i, the LP only contains variables xi , . . . , xn . Let
us denote this system by Gi . To eliminate variable xi all inequalities that contain xi are
written as xi ≤ h or xi ≥ `, where h and ` are some linear functions in xi+1 , . . . , xd . Let
us denote the two families of inequalities obtained by H and L, respectively. For each
h ∈ H and each ` ∈ L we add a new inequality ` ≤ h. This yields a set of inequalities
Gi+1 , on the variables xi+1 , . . . , xn . The method is feasibility preserving and given a
solution to Gi+1 , one can construct a solution of Gi in time O(|Gi |).
The Aspvall-Shiloach Method [1] Hochbaum and Naor’s algorithm highly relies
on a the following result by Aspvall and Shiloach [1].
For Ax ≤ b ∈ LI(2) let g, h ∈ G be of form g : α1 x + β1 y ≤ γ1 , h : α2 y + β2 z ≤ γ2 ,
for α1 , α2 , β1 6= 0, i.e., g and h share a variable. If β1 > 0 and α2 < 0, one can update g
with h to get a bound on x in terms of z as follows:
1y
2z
Assume that α1 > 0, it follows that x ≤ γ1 −β
and y ≥ γ2 −β
α1
α2 , and hence
2z
γ1 − β1 γ2 −β
γ1 − β 1 y
α2
x≤
≤
.
α1
α1

6

In the case that α1 < 0 we get a lower bound on x in terms of z. If β1 > 0 and
α2 < 0 one can similarly update x. If the the signs of β1 and α2 are the same, then no
update on x is possible.
For a family of {gi : αi xi + βi yi ≤ γi } ⊆ G, i = 1, . . . , k (k ≥ 1) we can do a
sequence of updates to the bound on xi , iff for all i = 1, . . . , k − 1, yi = xi+1 and
sign(βi ) = −sign(αi+1 ) 6= 0. If βk = 0 this is called a chain of length k. If βk 6= 0 and
yk = x1 , this is called cycle of length k. A chain or a cycle is called simple, if every
inequality appears at most once. (This concept was first introduced in [11]).
For example g1 : x − 31 y ≤ 1, g2 : y − 14 z ≤ 1, g3 : z ≤ 1 defines a chain of length 3 as
follows:
1
1
1
1
1
17
x ≤ 1 + y ≤ 1 + (1 + z) ≤ 1 + (1 + ) = .
3
3
4
3
12
12
Similarly g1 : x − 13 y ≥
x≥

1
12 ,

g2 : y − 14 z ≥ 0, g3 : z − 13 x ≥ 0 defines a cycle of length 3,

1
1
1
1 1
1
1 1 1
+ y≥
+ · z≥
+ · · x,
12 3
12 3 4
12 3 4 3

3
. A cycle results in an inequality of form x ≤ c + ax (or x ≥ c + ax).
which implies x ≥ 35
If a = 1, c < 0 (or a = 1, c > 0, respectively), then this is an infeasibility certificate for
Ax ≤ b.
For a variable xi we denote by xlow
(xhigh
), the best lower (upper) bound that can
i
i
be obtained by considering all chains and cycles of length at most d. If the system
high
max ]. Recall that the interval
Ax ≤ b is feasible, one can show that [xlow
] = [xmin
i , xi
i , xi
min
max
min
max
[xi , xi ] denotes the range of xi , xi (xi ) is the smallest (largest) value that xi
max ] ⊆
can take such that the system still has a feasible solution. The direction [xmin
i , xi
high
[xlow
] follows immediately from the definitions. For the other direction let p be a
i , xi
point of P = {x | Ax ≤ b} such that pi = xmin
i . Looking at the simple chains and simple
cycles of the halfspaces that contain p on their boundary, gives us the lower bound xmin
i .
high
max
The case for xi
and xi
is equivalent.
On the other hand if the system is infeasible then two things can happen. If xhigh
<
i
low
xi , then the range of xi is empty and this is a certificate for infeasibility. Such a
certificate may not exist in general. This is the case for example if the linear system
consists of two independent subsystems, one feasible and one infeasible. Also for the
small (infeasible) example y + z ≤ −1, y + z ≥ 1, x + y ≤ 1, we have that xlow = −∞
and xhigh = ∞.
From now on we will only discuss the case where Ax ≤ b is feasible. In Section 4.4
we will discuss how to get an infeasibility certificate using the same algorithm.

Theorem 5. [1] Given a feasible system Ax ≤ b in LI(2), a variable xi and a value
λ ∈ R, one can decide in time O(nd) whether λ < xmin
, λ = xmin
, λ ∈ (xmin
, xmax
),
i
i
i
i
max
max
λ = xi
or λ > xi .
Therefore in the feasible case this algorithm decides whether λ lies in the open range
on boundary of the range, or outside of the range (and on which side).

max ),
(xmin
i , xi

7

The proof of Theorem 5 requires many technical details. In the following we will
summarize the method and provide an intuitive idea. For detailed proofs refer to [1, 5].
Let xi be a fixed variable and λ ∈ R. For all j ∈ [n] let us denote by lo(xj ) (up(xj ))
the trivial lower (upper) bound on xj given by G, which may also be infinite.
The following algorithm fixes xi = λ and returns upper and lower bounds on xi
accordingly. In d rounds, it updates the lower and upper bounds, denoted by xj and xj ,
respectively, on all variables, where initially we are given xj := lo(xj ) and xj := up(xj ).

Algorithm Aspvall-Shiloach (G, i, λ);
begin
for j = 1, . . . , d do
xj := lo(xj ), xj := up(xj );
endfor;
xi := max{xi , λ}, xi := min{xi , λ} ;
for j = 1, . . . , d do
for g ∈ G, with g : axj + bxk ≤ c, a, b 6= 0 do
if a > 0, b > 0 then
c−ax
c−bx
xj ≤ a k =: xgj , xk ≤ b j =: xgk ;
elseif a > 0, b < 0 then
c−ax
k
xj ≤ c−bx
=: xgj , xk ≥ b j =: xgk ;
a
elseif a < 0, b > 0 then
c−ax
k
xj ≥ c−bx
=: xgj , xk ≤ b j =: xgk ;
a
else /*a < 0, b < 0*/ then
c−ax
c−bx
xj ≥ a k =: xgj , xk ≥ b j =: xgk ;
end for;
for ` = 1, . . . , d do
x` := maxg {x` , xg` }, x` := ming {x` , xg` };
endfor;
endfor;
output xi , xi ;
end.
The algorithm runs in d rounds of O(n) steps each, which results in the running time of
O(nd).
Since the output of the algorithm depends on λ we denote the outputs by xi (λ) and
xi (λ). By the properties of the algorithm it follows that the function xi (λ) is convex,
whereas xi (λ) is concave (see Figure 2).
max ], if and only if x (λ) ≤ λ ≤ x (λ). It follows
One can show that λ ∈ [xmin
i
i
i , xi
max = max{λ | x (λ) ≤ λ ≤ x (λ)}. To
that xmin
=
min{λ
|
x
(λ)
≤
λ
≤
x
(λ)}
and
x
i
i
i
i
i
i
distinguish between all cases of Theorem 5, we additionally need the (left and right)
slopes of xi (λ) and xi (λ). It is not hard to modify the Aspvall-Shiloach Algorithm in
8

xi

xi (λ)

λ = xi
xi (λ)

xmax
i

xmin
i

λ

Figure 2: Output Aspvall-Shiloach
such a way that it keeps track of the slopes as well. For instance if xi (λ) = λ ≤ xi (λ)
and the slope of xi is smaller than one at λ, then λ = xmin
i . In the case where the slope
max
is greater than one λ = xi . Using a careful case distinction one can show that the for
given λ, the values of xi (λ) and xi (λ) and their (left and right) slopes at λ are enough
to decide all cases of Theorem 5.

4.2

The Algorithm for the Feasible Case

The rough idea of the algorithm is the following. At step i we want to efficiently find
max ] and set x = λ to obtain a system with one less
λ in the current range [xmin
i
i , xi
variable. Whenever this is not possible, we eliminate xi efficiently in a Fourier-Motzkin
step. After this first part we set all variables that were eliminated to values in their
current range in the normal Fourier-Motzkin backtracking step.
First Part The first part of the algorithm runs in d steps. In step i we update two
linear systems Gi+1 and H i+1 from Gi and H i respectively, where initially G1 = H 1 = G.
The systems Gi (on d − i + 1 variables) and H i (on d variables) do basically encode
the same solution system, we will see later why a distinction is necessary. During the
execution of the algorithm, Gi is used to do Fourier-Motzkin elimination method, H i is
used to run the algorithm of Theorem 5. We denote by FM(xi , G) the set of inequalities
obtained by eliminating xi from G by using one step of the Fourier-Motzkin elimination
method.
For any two variables xj and xk in G, with j < k we represent the set of inequalities
containing xj and xk (with nonzero coefficients) in the (xj , xk ) plane as two envelopes,
the upper envelope and the lower envelope. The feasible region of xj and xk is contained between the envelopes (in the pink region of Figure 3) and each envelope can
be represented as a piecewise linear function with breakpoints. The projection of the
breakpoints onto the j-axis is denoted by Bkj (G). If the envelope is unbounded in the
xj -direction we add points at infinity to Bkj (G). The range of xj is hence contained in
the interval given by the leftmost and rightmost point of Bkj (G).
9

Below follows the pseudo code and the explanation of the algorithm.
Algorithm Hochbaum-Naor (G);
begin
G1 = H 1 = G;
for i = 1, . . . , d − 1 do
Generate B i = (bi1 , . . . , bim ), the sorted sequence of the points in
S
i
i
xj ∈N (xi ,Gi ) Bj (G );
Use Theorem 5 to do binary search on B i ;
i
max (H i ) then
if ∃` ∈ {1, . . . , m} such that xmin
i (H ) ≤ b` ≤ xi
Gi+1 := Gi |xi =b` ;
H i+1 := H i ∪ {xi ≤ b` } ∪ {xi ≥ b` };
i
max (H i ) < b
else if ∃`(1 ≤ ` < m) s.t. b` < xmin
`+1 then
i (H ) and xi
i
i
G := rel(G ) ∪ {xi ≥ b` } ∪ {xi ≤ b`+1 };
Gi+1 := FM(xi , Gi );
H i+1 := H i ;
else /* system infeasible */ then
output system infeasible;
endif;
endfor;
end.
Here rel(Gi ) denotes the so called relevant inequalities in Gi which we obtain by
removing some redundant inequalities. The exact definition follows in the description of
the algorithm below.
In step i the algorithm has computed Gi and H i , where originally G1 = H 1 = G.
For every pair (xi , xj ), such that xj is a neighbor of xi in Gi , i.e., xj ∈ N (xi , Gi ), it
computes the projections of the breakpoints Bji (Gi ). The union of those points are sorted
and denoted by B i . The idea is now to run a binary search on B i using Theorem 5, in
the hope of finding a point in the range of xi .
i
max (H i ),
If the algorithm finds a breakpoint b` ∈ B i such that xmin
i (H ) ≤ b` ≤ xi
then we set xi := b` (see Figure 3). We set H i+1 = H i ∪ {xi ≤ b` } ∪ {xi ≥ b` } and
Gi+1 := Gi |xi =b` .
i
If there is no such b` , the algorithm finds b` , b`+1 such that b` < xmin
i (H ) and
max
i
xi (H ) < b`+1 . In that case for any neighbor xj of xi the number of inequalities
containing both is reduced to at most two (bold lines of 4), the ones that define the
upper and lower envelope respectively on the interval [b` , b`+1 ] (blue part of Figure 4).
max ] ⊆ [b , b
This can be done since [xmin
` `+1 ] and therefore all other inequalities are
i , xi
redundant and can be removed. We denote the set of inequalities obtained after the
removal of the redundant ones by rel(Gi ). The normal Fourier-Motzkin elimination is
applied on rel(Gi ) ∪ {xi ≥ b` } ∪ {xi ≤ b`+1 } to obtain Gi+1 . By the above discussion
rel(Gi ) ∪ {xi ≥ b` } ∪ {xi ≤ b`+1 } has the same solution space as Gi . As the number of
inequalities between xi and any neighbor xj is reduced to at most two, the algorithm
10

z

y

b`

x
x

xmin

xmin

xmax

xmax

Figure 3: First case Hochbaum-Naor, example with 3 variables
adds at most four inequalities between any pair of neighbors of xi . This prevents the
usual quadratic blowup of the Fourier-Motzkin Method. The system H i+1 does not need
to be updated, i.e., H i+1 = H i .
We observe that in every step only a constant number of constraints are added to
H i , which guarantees the running time of the binary search to be O(nd log n). The size
of Gi can be of order Θ(n + d2 ) (as we may add up to 4d constraints in each step),
hence running Theorem 5 on Gi would not guarantee the running time in case where
n = o(d2 ).
Second Part The second part of the algorithm is now the normal backtracking of
the Fourier-Motzkin Method. Assume that the variables that were eliminated (in the
elseif-step) are xi1 , . . . , xik , where k ≤ d and i1 < i2 < · · · < ik. In the end of part one
we are left with the system Gd on variable xd . By the properties of the Fourier-Motzkin
elimination Gd is feasible and the range of xd is the same as its range in H d . Now choose
a feasible value of xd and continue inductively by backtracking through Gik , . . . , Gi1 .
The geometric interpretation is similar to the first part: for each variable we pick a
value in its current range.

4.3

Discussion of the Algorithm

We briefly discuss the main points of the proof of Theorem 4 (for more detail see [5]).
Proof sketch of Theorem 4 for the feasible case. Building and updating all enve-lopes takes
O(dn log n) time per step, hence O(d2 n log n) in total. Since for all i, the size of H i is
O(n) and |B i | ≤ n + 4d , in each step the binary search runs Theorem 5 O(log n) times,
where each evaluation takes time O(dn). It follows that the first part of the algorithm
takes time O(d2 n log n). For the second part consider the step where we find a solution
11

b`+1

b`

y

z

x
x

xmin

xmax

xmin

xmax

Figure 4: Second case Hochbaum-Naor, example with 3 variables
for a variable xj in the backtracking step in Gi . Then xj shares at most two inequalities
with each of its neighbors, therefore the whole second part only takes time O(d2 ).
During the whole algorithm, the variable xi is set to some value λ if and only if λ is
max ]. Therefore in the feasible case, it correctly outputs a
in the current bounds [xmin
i , xi
feasible point of Ax ≤ b.

4.4

Discussion of the Algorithm in the Infeasible Case

In the previous Section we showed that if Ax ≤ b is feasible, then the Hochbaum-Naor
Method always correctly outputs a feasible point. We now show that in the infeasible
case, infeasibility is always detected, which completes the proof of Theorem 4.
Proof sketch of Theorem 4 for the infeasible case. Assume that Ax ≤ b is infeasible. We
now run the first part of the algorithm as in the feasible case. If during the execution at
some point during binary search, we detect a contradiction in form of xmax
< xmin
this
i
i
is a certificate for infeasibility and we are done. It is however possible that in every call
min max ],
of the algorithm of Theorem 5 we get some (wrong) output λ < xmin
i , λ ∈ [xi , xi
max
d
λ > xi . In that case G is an infeasible system on the variable d. This follows since
the Fourier-Motzkin elimination is feasibility preserving and setting some variables to
fixed values in an infeasible system, keeps the system infeasible. Detecting infeasibility
in a system with one variable can be trivially done in linear time in the number of
constraints. It follows that infeasibility is always detected, which concludes the proof of
Theorem 4.

12

5

Modification of the Hochbaum-Naor Method

We now show how to modify the Hochbaum-Naor Method from Section 4, such that it
decides full-dimensio-nality of the problem and in the full-dimensional case outputs an
interior point (see Theorem 1). For this we need some preparatory lemmas.
max ). Then y := (λ, y , . . . , y ) is
Lemma 6. Let Ax ≤ b feasible and let λ ∈ (xmin
2
d
1 , x1
0
an interior point solution of Ax ≤ b if and only if y := (y2 , . . . , yd ) is an interior point
solution of A0 x ≤ b0 , where A0 x ≤ b0 is the system obtained by (Ax ≤ b)|x1 =λ .

Proof. Let y be an interior point solution of Ax ≤ b. Then by definition Ay < b and
obviously A0 y 0 < b0 . On the other hand let y 0 be an interior point solution of A0 x < b0 ,
i.e., A0 y 0 < b0 . Then y satisfies any inequalities containing some xi 6= x1 strictly. The
only inequalities that might be satisfied with equality are the ones containing only x1 ,
max ).
but this is a contradiction to λ ∈ (xmin
1 , x1
Lemma 7. In the Fourier-Motzkin Method Gi+1 has an interior point solution, if Gi
has one. Moreover if an interior point solution of G1 = G exists, it can be obtained in
the running time of the Fourier-Motzkin algorithm.
Proof. The first part follows by Lemma 6. For the second part is is enough to consider a
slight variant of the Fourier-Motzkin elimination. Instead of running the algorithm on a
system Ax ≤ b, we run it on Ax < b. In each step the inequalities obtained are of form
l < h instead of l ≤ h. By induction, using Lemma 6 one can see that finding a solution
using this variant, is equivalent to finding an interior point of Ax ≤ b.
Proof of Theorem 1. Assume that Ax ≤ b is feasible. We run the Hochbaum-Naor
Algorithm almost in the same way as described in Section 4. The only difference is in the
if-loop of the algorithm. The original algorithm distinguishes between the cases λ < xmin
i ,
max ] and λ > xmax of Theorem 5. Our algorithm however distinguishes
λ ∈ [xmin
,
x
i
i
i
min max ) and λ ≥ xmax .
between λ ≤ xmin
i , λ ∈ (xi , xi
i
In the first case we only set xi = b` if there exists a breakpoint b` ∈ B, such that
i
max (H i ). We only fix x to some value b , if b is in the open range
xmin
i
`
`
i (H ) < b` < xi
i ), xmax (H i )), (in the original Theorem we were considered the closed range).
(xmin
(H
i
i
The second case accordingly changes to finding an interval [b` , b`+1 ] (1 ≤ ` < k) such that
i
max (H i ) ≤ b
min
i
max (H i ) < b
b` ≤ xmin
`+1 , (originally b` < xi (H ) and xi
`+1 ).
i (H ) and xi
We see that in this case, the number of inequalities on each edge adjacent to xi is still
reduced to at most two.
min
min max ), λ = xmax
As Theorem 5 distinguishes the cases λ < xmin
i
i , λ = xi , λ ∈ (xi , xi
max
λ > xi
and certificate for infeasibility in time O(nd), the running time remains the
same.
It remains to show that the modified algorithm detects full-dimensionality and in the
full-dimensional case an interior point.
The discussion of the case where Ax ≤ b is infeasible is equivalent as in the proof of
Theorem 4. Hence assume that the system is feasible.
13

Let Ax ≤ b be full-dimensional. By Lemma 6, after the first part of the algorithm
(and Gd ) are associated with a system of inequalities whose interior point solutions
can be extended to an interior point solution of Ax ≤ b. The interior point solution of
Ax ≤ b can now be found in the backtracking step using Lemma 7. Assume such a point
can not be found. Then by Lemma 7 there is no interior point of Ax ≤ b, which is a
contradiction to full-dimensionality.
Let Ax ≤ b be feasible but non-full-dimensional. Then at some point of the backtracking the algorithm finds xmin
= xmax
for the current bounds. Suppose this does not
i
i
happen, then by Lemma 6 the algorithm finds an interior point, which is a contradiction
to non-full-dimensionality.
Hd

6

The Non-Full-Dimensional Case

In the non full-dimensional case redundancies are dependent on each other, meaning
that a redundant constraint can become nonredundant after the removal of another
redundant constraint. The problem is therefore to find a maximal set of nonredundant
constraints.
Clarkson’s Algorithm can be extended for redundancy removal in the non-full-dimensional
case as follows: In a preprocessing step one can find the dimension k of the system
Ax ≤ b, by solving at most d linear programs [4]. Of all the inequalities that are forced
to equality, we can find a set of (d − k) equalities that defines the k-dimensional space
where P = {x | Ax ≤ b} lies in. Let us denote the remaining system of inequalities
(the ones not forced to equality) by A2 x ≤ b2 . One can now rotate the the system such
that P lies in Rk . Clarkson’s algorithm can now be applied in Rk , where the constraints
are the intersections of the rotated system of A2 x ≤ b2 intersected with Rk . After the
preprocessing the running time is hence O(n · LP (s, k)).
In the case of LI(2) we observe that such a rotation may destroy the structure of
two variables per inequality. It results that we are still able to match Clarkson’s running
time, using substitution of variables.
Theorem 8. Let Ax ≤ b a k-dimensional system in LI(2), for 0 ≤ k ≤ d. Then given
a relative interior point solution of Ax ≤ b, all redundancies can be detected in time
O(nk 2 s log s + d2 n).
The d2 n term comes from Gaussian elimination, which is dominated by the preprocessing time needed to find the relative interior point (see Proposition 10). Note that
the typically larger term nk 2 s log s is dependent on the dimension of the polytope k and
not d.
We need the following observation for the proof of Theorem 8.
Observation 9. Let Ax ≤ b in LI(2) and αxi + βxj ≤ γ, β 6= 0, an inequality of the
system that is forced to equality, i.e., αx∗i + βx∗j = γ, for all solutions x∗ . Let Ax ≤ b be
the system obtained by substituting xj = βγ − αβ xi . Then the following holds.
14

• Ax ≤ b is still in LI(2).
• A constraint is redundant in Ax ≤ b if and only if it is redundant in the system
Ax ≤ b.
Proof. Given a relative interior point x∗ , one can find A1 x ≤ b1 , the subsystem of
Ax ≤ b that is forced to be equality, in time O(nd). The remaining system is denoted
by A2 x ≤ b2 . Finding a minimal subsystem A∗1 x = b∗1 of A1 x = b1 with (d − k) linearly
independent equalities that defines the k-dimensional space containing P = {x | Ax ≤
b}, takes O(d2 n) time using the Gaussian elimination. Using these equalities we can
substitute d − k variables of A2 x ≤ b2 in the same fashion as explained in Observation
9. Hence we get a k-dimensional representation of Ax ≤ b which is in LI(2).
We can now run the algorithm given by Theorem 2 on A02 x ≤ b02 , the system obtained
from A2 x ≤ b2 after substitution. These detected nonredundant constraints together
with A∗1 x = b∗1 give us a minimal set of nonredundant inequalities.
The following proposition shows that finding a relative interior point can also be
done in strongly polynomial time.
Proposition 10. Given Ax ≤ b, one can find a relative interior point of Ax ≤ b or a
certificate for infeasibility in time O(d2 n log n).
Proof. Using a similar argument as in Lemma 6, one can show the following.
• If xmin
< λ < xmax
, then y := (λ, y2 , . . . , yd ) is a relative interior point of Ax ≤ b
1
1
0
if and only if y := (y2 , . . . , yd ) is a relative interior point of (Ax ≤ b)|x1 =λ .
• If xmin
= xmax
= λ, then y := (λ, y2 , . . . , yd ) is a relative interior point of Ax ≤ b
1
1
if and only if y 0 := (y2 , . . . , yd ) is a relative interior point of (Ax ≤ b)|x1 =λ .
The algorithm for finding a relative interior point is very similar to the modified HochbaumNaor Method. The first part runs equivalently. In the second part of the backtracking
if at some point xmin
= xmax
, we set xi := xmin
= xmax
. Infeasibility is detected by
i
i
i
i
the same argument as in Theorem 4. Correctness follows from the above argument, the
running time is the same as in Theorem 1.
Corollary 11. The dimension of Ax ≤ b or a certificate for infeasibility can be found
in time O(d2 n log n), i.e., the same running time as finding a feasible point solution of
a certificate for infeasibility.
Proof. Consider the algorithm of the proof of Proposition 10. Since we know that infeasibility will be detected, assume that Ax ≤ b is feasible. Let us denote the current
polytope by P , where initally P = {x | Ax ≤ b} the polytope defined by Ax ≤ b. Every
max ), the dimension of the current
time xi is set to a value in the open range (xmin
i , xi
polytope P decreases by 1, as we intersect it with a hyperplane not containing P . If
= xmax
, then the dimension of the current polygon
xmin
= xmax
and we set xi := xmin
i
i
i
i
stays the same, as we intersect it with a hyperplane containing P . Since after setting all
to some value we end up with a point (polygon of dimension 0), the dimension of Ax ≤ b
max ).
is exactly the number of times we set xi to a value in the open range (xmin
i , xi
15

7

Acknowledgments

The authors would like to thank Seffi Naor for insights into the problem. Moreover we
would like to thank Jerri Nummenpalo and Luis Barba for interesting discussions. We
are especially grateful to Jerri Nummenpalo for making us aware of some important
literature and helping us during the writeup of this paper.

References
[1] B. Aspvall and Y. Shiloach. A polynomial time algorithm for solving systems of
linear inequalities with two variables per inequality. Siam Journal on Computing,
9:827–845, 1980.
[2] K. L. Clarkson. More output-sensitive geometric algorithms. In Proc. 35th Annu.
IEEE Sympos. Found. Comput. Sci., pages 695–702, 1994.
[3] G. B. Dantzig. Linear Programming and Extensions. Princeton University Press,
Princeton, NJ, 1963.
[4] K.
Fukuda.
Lecture
notes:
Polyhedral
computation.
ETH,
Zurich,
Switzerland,
2016.
https://www.inf.ethz.ch/personal/fukudak/lect/pclect/notes2016/PolyComp2016.pdf
[5] D. S. Hochbaum and J. Naor. Simple and fast algorithm for linear and integer
programs with two variables per inequality. Siam Journal on Computing, 23:1179–
1192, 1994.
[6] N. Karmarkar. A new polynomial time algorithm for linear programming. Combinatorica, 4(4):373–395, 1984.
[7] L. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademiia
Nauk SSSR, 244:1093–1096, 1979. (Translated in Sovjet Mathematics Doklady 20,
191-194, 1979).
[8] V. Klee and G. J. Minty. How good is the simplex algorithm? In O. Shisha, editor,
Inequalities III, pages 159–175. Academic Press, 1972.
[9] Nimrod Megiddo. Towards a genuinely polynomial algorithm for linear programming. Siam Journal on Computing, 12:347–353, 1983.
[10] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley &
Sons, Chichester, 1986.
[11] R. Shostak. Deciding linear inequalities by computing loop residues. Journal of the
Association for Computing Machinery, 28:769–679, 1981.

16

