Geometry of Integer Optimization
Shuvomoy Das Gupta
November 22, 2024
In integer programming we minimize a linear cost function subject
to the constraint set being the integer points in a polyhedron. In this
note, we study fundamental geometric objects of integer optimization,
namely integral generating set and integral basis. They lead to i) op-
timality conditions in integer programming, ii) characterize integral
polyhedra, and iii) play very important role in integer programming
algorithms such as cutting plane and integral basis algorithms.
The note is based on
1
.
1
Dimitris Bertsimas and Robert Weis-
mantel. Optimization over integers,
volume 13. Dynamic Ideas Belmont,
2005
Definition
Notation
• Set of integers and real numbers are
denoted by Z and R respectively.
• If S ⊆ R
n
is a set, then the set of all
integer points in S is denoted by S
Z
, i.e.,
S
Z
= S ∩ Z
n
.
• P = {x ∈ R
n
| Ax ⪯ b}.
• P
Z
=
{
x ∈ Z
n
| Ax ⪯ b
}
.
• Convex hull of a set S is denoted by
conv(S).
• x
+
i
= max{0, x
i
}, x
−
i
= max{0, −x
i
},
x
+
= (x
+
1
, . . . , x
+
n
), x
−
=
{x
−
1
, . . . , x
−
n
}.
Integral generating set and integral basis. Consider a set F, which is a
set of integer points. For example, F could be the set
{
x ∈ Z
n
| Ax ⪯ b
}
,
which is the constraint set for an integer programming problem. We
look for a subset of F, preferably much smaller than F , which can
generate all the points in F with respect to nonnegative combinations
of its elements. Such sets are called integral generating sets. The
integral generating set of minimum size is called the integral basis.
Definition 1. (Integral generating set and integral basis) Consider the set
F, which is a set of integer points in Z
n
. A subset of F, denoted by igs(F ),
is called an integral generating set of F, if
(
∀x ∈ F
) (
∃{h
1
, . . . , h
k
} ⊆ igs(F )
) (
∃{λ
1
, . . . , λ
k
} ⊆ Z
+
)
x =
k
∑
i=1
λ
i
h
i
.
An integral generating set igs(F ) of F is called an integral basis, and
denoted by ib(F ) if it is the smallest integral generating set. More specifi-
cally,
(
∀G : integral generating set of F
)
ib(F ) ⊆ G.
Note that, F is its own integral generating set, however it is not an
integral basis in general.
Cone in polyhedral theory. The concept of cone is very important in
integer optimization.
Definition 2. (Cone) A set C ⊆ R
n
is called a cone if
(
∀x ∈ C
) (
∀λ ≥ 0
)
λx ∈ C.
geometry of integer optimization 2
Now we define some other types of cone: polyhedral cone, ratio-
nal cone, and pointed cone.
Definition 3. (Polyhedral cone) A cone C ⊆ R
n
is called a polyhedral cone
if
2
2
A polyhedral cone is always convex.
∃V ∈ R
n×k
C = cone(V) =
n
Vλ | λ ∈ R
k
+
o
.
The matrix V is called the generator of the cone. If the ith column of V
is denoted by v
i
, then we can write Vλ =
∑
k
i=1
λ
i
v
i
. So, each element
of C is generated by a nonnegative combination of the columns of V.
We say that the polyhedral cone C is generated by V, and write it as
C = cone(V). If V ∈ Q
n×k
, i.e., all the elements of V are rational,
then we say that C is a rational polyhedral cone. Another equivalent
representation of a rational polyhedral cone is the set
{
x ∈ R
n
| Ax ⪰ 0
}
,
where A ∈ Q
m×n
.
Definition 4. (Pointed cone) A cone is pointed if there exists a halfspace
h = {x|a
T
x ≤ 0} such that
3
3
A pointed cone does not contain a
line.
h ∩ C = {0}.
Similar to integral generating set and integral basis, we can define
analogous concepts for a set of real numbers.
Definition 5. (Real generating set and real basis) Consider a set R, a set
of real points in R
n
. A subset of R, denoted by rgs(R), is called a real
generating set of R, if
(
∀x ∈ R
) (
∃{h
1
, . . . , h
k
} ⊆ rgs(F )
) (
∃{λ
1
, . . . , λ
k
} ⊆ R
+
)
x =
k
∑
i=1
λ
i
h
i
.
An real generating set rgs(R) of R is called an real basis, and denoted by
rb(R) if it is the smallest real generating set. More specifically,
(
∀G : real generating set of R
)
rb(R) ⊆ G.
If cone(V) is a pointed rational polyhedral cone, then the any
element in rb
(
cone(V)
)
is an extreme ray.
Integral generating sets and bases in cones.
Set of integer points in a rational polyhedral cone has a finite integral gen-
erating set. In this section we study the following problem. We are
given a rational polyhedral cone C = cone(V), with V ∈ Q
n×k
. The
number of integer points in C, i.e., in C
Z
= C ∩ Z
n
, is infinite. What
about its integral generating set? It turns out that there is a finite
integral generating set. So a finite number of integer points would
generate all the elements in a countably infinite set!
geometry of integer optimization 3
Theorem 6. If C = cone(V) is rational, then there exists an igs
C
Z
,
which has a finite number of elements.
Set of integer points in a rational polyhedral cones has a finite unique
integral basis. The theorem above is an encouraging one; it moti-
vates us to ask to look for the smallest of all the integral generating
sets - an integral basis, which will contain the smallest and finite
number of generating points. However, the integral basis sets of
cone(V)
Z
= cone(V) ∩ Z
n
may note be unique, though the cardi-
nality of each of those integral basis sets will be the same. But, if we
add the attribute - pointedness to cone(V), then we have a unique
integral basis.
Theorem 7. Suppose C is a rational polyhedral cone. Then, ib
C
Z
is
unique and is given by
ib
C
Z
=
n
h ∈ (C
Z
\ {0}) |
∀v, w ∈ (C
Z
\ {0})
h = v + w
o
.
In words, the integer points in a rational polyhedral cone has a unique
integral basis.
Change in the cone generator. Suppose we are given a rational poly-
hedral cone C = cone(V), where V =
h
v
1
v
2
· · · v
k
i
∈ Z
n×k
,
4
4
In fact C is an integral polyhedral
cone.
and we have calculated an integral generating set of C
Z
= C ∩ Z
n
,
denoted by igs
C
Z
. Now we pick a point c from C
Z
, negate it and
add it to V, so we have a new matrix
V
′
=
h
v
1
v
2
· · · v
k
−c
i
.
Consider the rational polyhedral cone generated by V
′
, i.e., C
′
=
C(V
′
). What would be an integral generating set of C
′Z
? Turns out
that, all we have to do is to take igs
C
Z
and union the vector −c to
it, i.e., igs
C
′Z
= igs
C
Z
∪
{
−c
}
.
Theorem 8. Suppose, V =
h
v
1
v
2
· · · v
k
i
∈ Z
n×k
, and C = cone(V)
is a rational (integral) polyhedral cone. For any c ∈ C
Z
, suppose V
′
=
h
V −c
i
and C
′
= C(V
′
). Then,
igs
C
′Z
= igs(C
Z
) ∪
{
−c
}
.
Extension of Caratheodory’s theorem to integer points in a rational poly-
hedral cone. Caratheodory’s theorem is a key result in linear pro-
gramming theory. Consider a rational polyhedral cone generated
by V ∈ Q
n×k
, denoted by cone(V) ⊆ R
n
. Suppose its real generat-
ing set is denoted by rgs(cone(V)). Now all points in cone(V) can For cone(V),
rgs
(
cone
(
V
))
= {v
1
, . . . v
i
, . . . , v
k
},
where v
i
is the ith column of V.
geometry of integer optimization 4
be represented as a nonnegative combinations of the elements in
rgs
(
cone(V)
)
. A natural question is, if we are given an arbitrary ele-
ment of cone(V), how many elements from rgs(cone(V)) is required
to express it? Caratheodory’s theorem says that the magic number is
n, same as the dimension of the space where cone(V) resides.
Theorem 9. (Caratheodory’s theorem) Suppose cone(V) ⊆ R
n
is a rational
polyhedral cone. Any element of cone(V) ⊆ R
n
can be represented by a
nonnegative combination of at most n elements from rgs
(
cone(V)
)
.
A natural question is if Caratheodory’s theorem holds for the
integer points in cone(V). The answer is no in generally
5
. We need
5
Holds for n = 2 and 3, but does not
for n ≥ 6.
almost twice as many points.
Theorem 10. (Extension of Caratheodory’s theorem to integer points in
a pointed rational polyhedral cone) Suppose cone(V) ⊆ R
n
is a pointed
rational polyhedral cone. Any element of cone(V)
Z
⊆ Z
n
can be repre-
sented by a nonnegative integral combination at most 2n − 2 elements from
ib
cone(V)
Z
.
Optimality conditions in integer programming
Review of optimality conditions in linear programming. Consider the
standard for linear programming problem given below.
maximize
x
c
T
x
subject to x ∈ P =
{
x ∈ R
n
| Ax = b, 0 ⪯ x ⪯ u
}
(1)
Here, A ∈ Z
m×n
, b ∈ Z
m
.
An orthant in a finite n-dimensional vector space is a set which
contains the zero vector and the sign component of all vectors in it is
the same. Any finite n−dimensional vector space can be divided into
2
n
orthants
6
. We denote the jth orthant by O
j
for j = 1, 2, . . . , 2
n
. Note
6
E.g., for n = 2, we have 4 orthants.
that, if we multiply any point of an orthant by a nonnegative number,
the sign components does not change and the resultant component
stays in the same orthant. So, an orthant is also a cone. Now for
j = 1, 2, . . . , 2
n
, we denote the nullspace of A in orthant O
j
by C
j
, i.e.,
C
j
= {x ∈ R
n
| Ax = 0} ∩ O
j
= {x ∈ O
j
| Ax = 0}.
The set C
j
is a pointed rational polyhedral cone too
7
. Now the set of
7
C
j
is a cone, which we can show as
follows. First, by definition,
x ∈ C
j
⇔ x ∈ O
j
, Ax = 0.
Consider any λ ≥ 0. By definition of an
orthant, λx ∈ O
j
, and A(λx) = λ Ax =
0. So, λx ∈ C
j
, i.e., C
j
is a cone. As, C
j
is
also a pointed rational polyhedron, it is
a pointed rational polyhedral cone.
all extreme rays
8
in C
j
, i.e., the real basis of C
j
, is denoted by rb
C
j
.
8
•Extreme rays of a cone are the
directions associated with the edges
of a cone which extend to infinity.
•The set of extreme rays of a rational
polyhedral cone and its real basis are
the same set.
Using the rb(C
j
)s we can come up with the optimality condition for
the linear programming problem (1).
geometry of integer optimization 5
Theorem 11. (Optimality conditions in linear programming) Consider any
feasible solution x ∈ P for the linear programming problem (1). Then x is
optimal if and only if
∀h ∈
2
n
[
j=1
rb
C
j
c
T
h ≤ 0, or
c
T
h > 0, and x + λh ∈ P
(
∀λ > 0
)
.
The first disjunctive statement means that if we move away from
x to any other feasible point, then the objective function cannot in-
crease anymore. The second disjunctive statement means that if we
can get to a point from x, where we have a larger objective value,
then that first point will be infeasible.
Optimality conditions in integer programming. Now let’s see how the
optimality conditions change for integer programming problem.
Consider the integer programming problem
9
:
9
Compare with linear programming
problem (1).
maximize
x
c
T
x
subject to x ∈ P
Z
=
{
x ∈ Z
n
| Ax = b, 0 ⪯ x ⪯ u
}
.
(2)
The optimality conditions for the problem above has structural
similarity to that of the linear programming problem. The optimality
conditions are stated in the theorem below.
Theorem 12. (Optimality conditions in integer programming) Consider
any feasible solution x ∈ P
Z
for the integer programming problem (2). Then
x is optimal if and only if
∀h ∈
2
n
[
j=1
ib
C
Z
j
c
T
h ≤ 0, or
c
T
h > 0, and x + h ∈ P.
Note the surprising structural similarity between Theorems (11)
and (12).
From cones to polyhedra
Integer points in a polyhedron may not have a finite integral generating set.
In this section we discuss the existence and uniqueness of integral
bases of the constraint set arising in integer optimization problem:
F =
{
x ∈ Z
n
| Ax ⪯ b
}
,
where A ∈ Z
m×n
, b ∈ Z
m
. Recall that the integer points in a rational
polyhedral cone has a finite integral generating set. However, the
set of integer points in a polyhedron may not have a finite integral
generating set. This is a disappointing result. So, we relax one of
geometry of integer optimization 6
the specifications for the integral generating set - the generators i.e.,
members of the integral generating set coming from the integer set
F itself, and ask if we can find a finite number of points, not neces-
sarily in F, which generate F. This has a positive answer, which we
present next.
Theorem 13. Consider the polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b, x ⪰ 0
}
,
where A ∈ Z
m×n
and b ∈ Z
m
. The polyhedral cone associated with P is
C =
{
x ∈ R
n
| Ax ⪯ 0, x ⪰ 0
}
,
and the real basis of C (the set of all extreme rays of C) is The set of all integer points in P is
denoted by
P
Z
= {x ∈ Z
n
| Ax ⪯ b, x ⪰ 0}.
The set of all integer points in C is
denoted by
C
Z
= {x ∈ Z
n
| Ax ⪯ 0, x ⪰ 0}.
rb(C) = {v
1
, . . . , v
t
} ⊆ Z
n
.
Then,
• There exists a finite set W ⊆ P
Z
such that
∀x ∈ P
Z
(
∃w ∈ W
) (
∃λ
1
, . . . , λ
t
∈ Z
+
)
x = w +
t
∑
i=1
λ
i
v
i
.
• The convex hull of P
Z
, denoted by conv(P
Z
) satisfies
conv(P
Z
) = conv(W) + C.
Nonnegative resource vector b leads to a finite integral basis. Is there any
condition under which we have a finite integral generating set for
the integer points in a polyhedron? The answer is yes, if we have a
nonnegative resource vector, then we have a finite integral generating
set, more specifically a finite integral basis.
Theorem 14. Consider the polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b, x ⪰ 0
}
,
where A ∈ Z
m×n
and b ∈ Z
m
. If b ⪰ 0, then P
Z
has finite integral basis
ib(P
Z
) given by
ib(P
Z
) =
(
v ∈ P
Z
| ¬
(
∃λ
1
, . . . , λ
k
∈ Z
+
)
∃v
1
, . . . , v
k
∈ P
Z
\ {v, 0}
v =
k
∑
i=1
λ
i
v
i
!)
=
(
v ∈ P
Z
|
(
∀λ
1
, . . . , λ
k
∈ Z
+
)
∀v
1
, . . . , v
k
∈ P
Z
\ {v, 0}
v =
k
∑
i=1
λ
i
v
i
)
.
geometry of integer optimization 7
A more general condition for the existence of a finite integral basis. Is
there a more general theorem than this, which would guarantee the
existence of a finite integral basis? The answer is yes and it is related
to how many integer points of the polyhedral cone is missing from
P
Z
; if it is finite, then we have a finite integral basis.
Theorem 15. Consider the polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b, x ⪰ 0
}
,
where A ∈ Z
m×n
and b ∈ Z
m
. The polyhedral cone associated with P is
C =
{
x ∈ R
n
| Ax ⪯ 0, x ⪰ 0
}
.
There exists a finite integral generating set of P
Z
if and only if P
Z
contains
all but a finite number of points in C
Z
. Moreover, if a finite integral generat-
ing set of P
Z
exists, then there is a unique integral basis of P
Z
.
Algorithms to compute integral generating sets and integral bases.
Suppose we are given a set of integer points F, and we want to find
out its integral generating sets and integral bases.
Integral generating set when F is finite and given explicitly. If F is finite
and given explicitly, then F itself is its integral generating set.
Integral generating set when F consists of the integer points of a rational
polyhedral cone. Suppose we are given a rational polyhedral cone
C = cone(V), where V =
h
v
1
v
2
· · · v
k
i
∈ Z
n×k
, then
igs
C
Z
=
{
v
1
, . . . , v
k
}
[
(
k
∑
i=1
λ
i
v
i
|
(
λ
i
)
k
i=1
⊆ [0, 1)
)
.
Integral generating set when F consists of the integer points in a polyhe-
dron. The set in consideration is
F =
{
x ∈ Z
n
| Ax ⪯ b, x ⪰ 0
}
,
where A ∈ Z
m×n
and b ∈ Z
m
and b ⪰ 0. Recall that in this case,
we have a finite integral generating set and finite integral basis by
Theorem (14). We want to find igs(F ). The algorithm to find it is
given by Algorithm (1), which terminates in finite time.
Integral basis when F consists of the integer points in a polyhedron. After
we have found igs
(
F
)
via Algorithm (1). Now, we want to find out
the integral basis from the integral generating set. The algorithm is
given by (2).
geometry of integer optimization 8
Algorithm 1 Calculating integral generating set of
{
x ∈ Z
n
| Ax ⪯ b, x ⪰ 0
}
.
input: A ∈ Z
m×n
, b ∈ Z
m
, b ⪰ 0
output: igs(F), where
F =
{
x ∈ Z
n
| Ax ⪯ b, x ⪰ 0
}
.
algorithm:
1. initialization:
T
0
:= ∅
T := {e
i
| i = 1, . . . , n}▷e
i
is the ith unit vector.
2. main iteration:
while T
0
= T
repeat
T
0
:= T
(
∀v, w ∈ T
0
)
z := v + w
if
(
∃y ∈ T
)
y ⪯ z
(Ay)
+
⪯ (Az)
+
(Ay)
−
⪯ (Az)
−
then z := z − y
end if
if z = 0
then T := T ∪
{
z
}
end if
end repeat
3. return igs(F ) := T ∩ F.
Integral basis when F consists of the integer points in a pointed rational
polyhedral cone. When the set in consideration is a pointed rational
polyhedral cone, then Algorithm (2) can be simplified using follow-
ing theorem.
Theorem 16. Suppose C is a pointed rational polyhedral cone, and h ∈
igs
C
Z
\ {0}. Then h ∈ ib
C
Z
if and only if there exists a h
j
∈
igs
C
Z
such that h − h
j
∈ C.
Due to the theorem above, we can simplify the algorithm for calcu-
lating the integral basis of a pointed rational polyhedral cone. Check-
ing whether h − h
j
∈ C is a linear feasibility problem. The algorithm
is given by Algorithm (3). If we are given igs
C
Z
explicitly, then we
can find ib
C
Z
in polynomial time by solving
|igs( C
Z
)|(|igs(C
Z
)|−1)
2
linear feasibility problems.
Total dual integrality
The concept of total dual integrality is handy to guarantee the in-
tegrality of a polyhedron. Total dual integrality of a polyhedron is
geometry of integer optimization 9
Algorithm 2 Calculating integral basis of
{
x ∈ Z
n
| Ax ⪯ b, x ⪰ 0
}
.
input: A ∈ Z
m×n
, b ∈ Z
m
, b ⪰ 0, igs
(
F
)
=
{
h
1
, . . . , h
k
}
, where
F =
{
x ∈ Z
n
| Ax ⪯ b, x ⪰ 0
}
.
output: ib(F ).
algorithm:
1. initialization
T := igs
(
F
)
2. main iteration:
for i = 1, . . . , k do
Solve the integer feasibility problem
find y
subject to
k
∑
j=1,j=i
y
j
h
j
= h
i
y ∈ Z
k−1
+
.
(3)
if problem (3) is feasible
then T := T \
{
h
i
}
end if
end for
3. return ib(F ) := T.
Algorithm 3 Calculating integral basis of
{
x ∈ Z
n
| Ax ⪯ 0, x ⪰ 0
}
.
input: A ∈ Z
m×n
, b ∈ Z
m
,
C = {x ∈ R
n
| Ax ⪯ 0, x ⪰ 0},
igs
C
Z
=
{
h
1
, . . . , h
k
}
.
output: ib(C
Z
)
algorithm:
1. initialization
T := igs
C
Z
2. main iteration:
for i = 1, . . . , k do
Solve the linear feasibility problem
minimize 0
subject to
(
∀j ∈ {1, . . . , k} \ {i}
)
h
i
− h
j
∈ C
(4)
if problem (4) is feasible
then T := T \
{
h
i
}
end if
end for
3. return ib(C
Z
) := T.
geometry of integer optimization 10
associated with the a system of linear inequalities which represents a
polyhedron.
Definition 17. (Totally dual integral system) Consider the polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b
}
,
where A ∈ Z
m×n
, b ∈ Z
m
. The system of inequalities Ax ⪯ b is called
totally dual integral if for every face
10
F = {x ∈ P | A
I
x = b
I
} we
10
Face: Suppose we have a polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b
}
,
where A ∈ Z
m×n
, b ∈ Z
m
. If
˜
a
T
x ≥
˜
b
is a valid inequality for a P, then the
set
x ∈ P |
˜
a
T
x =
˜
b
is called a face of
P. For any face F of P, we can find an
index set I ⊆ {1, 2, . . . , m} such that F
has the equivalent representation
F =
{
x ∈ P | A
I
x = b
I
}
,
where A
I
is the square submatrix
consisting of rows a
T
i
for i ∈ I, and
b
I
is the associated subvector of b. For
example, if I = {1, 10} ⊆ {1, 2, . . . , 15},
then A
I
=
a
T
1
a
T
10
, and b =
b
1
b
2
.
have
n
a
T
i
| i ∈ I
o
= igs
cone
{a
T
i
| i ∈ I}
Z
.
There may exist different systems of linear inequalities each repre-
senting P. Only one among them is totally dual integral, and to get to
that system we may need to add many redundant inequalities. There
is a nice connection between dual integrality of a system of linear
inequalities and duality theory.
Theorem 18. Suppose A ∈ Z
m×n
, b ∈ Z
m
. Consider the optimization
problem
p
∗
=
maximize c
T
x
subject to Ax ⪯ b
x ∈ R
n
,
and its dual
d
∗
=
minimize b
T
y
subject to A
T
y = c
y ⪰ 0
y ∈ R
m
.
Then the following are equivalent.
(i) The system of inequalities associated with the primal problem Ax ⪯ b
is totally dual integral.
(ii) For any c ∈ Z
n
such that d
∗
is finite, there is an integral optimal
solution y
∗
∈ Z
m
.
The following theorem shows the connection between totally dual
integral system and the integrality of the associated polyhedron.
Theorem 19. Consider the polyhedron
P =
{
x ∈ R
n
| Ax ⪯ b
}
,
where A ∈ Z
m×n
, b ∈ Z
m
. If the system of inequalities Ax ⪯ b is totally
dual integral, then P is integral
11
.
11
If the polyhedron P = {x ∈ R
n
| Ax ⪯
b} is integral, then to solve the integer
optimization problem
minimize
x
c
T
x
subject to Ax ⪯ b
x ∈ Z
n
,
we can just solve the relaxed linear program
minimize
x
c
T
x
subject to Ax ⪯ b
x ∈ R
n
,
which will give an integer optimal solution
due to integrality of P.
Theorem 20. Every rational polyhedron P can be described by a totally
dual integral system of the form Ax ⪯ b with A integral. Additionally, if b
is integral then P is integral, and vice versa.
geometry of integer optimization 11
References
[1] Dimitris Bertsimas and Robert Weismantel. Optimization over
integers, volume 13. Dynamic Ideas Belmont, 2005.
