Solving Mixed-Integer Optimization Problems using
Benders Decomposition
Shuvomoy Das Gupta
September 17, 2024
This is a blog on how to solve mixed-integer optimization problems us-
ing Benders decomposition algorithm, due to Jacques F. Benders. The
formulation presented here closely follows [Garfinkel and Nemhauser,
1972, Section 4.8].
Figure 1: Jacques F. Benders
(1925-2017).
Contents
Things to recall. 1
Mixed-integer optimization problem to solve. 2
Problem (P) for fixed x
′
∈ Z
n
+
. 2
Dual of the minimization problem associated with p
⋆
sub
(x
′
). 3
Relationship between (P), (P(x
′
)) and (D(x
′
)). 4
Representation of (P) via extreme points of S. 5
Setup for the decomposition algorithm. 6
Decomposition algorithm. 6
Benefits of the algorithm. 7
Things to recall.
We recall the following facts that we will use to develop the algo-
rithm.
Notation.
• The symbol ⪯ or ⪰ corresponds to
element-wise greater than or smaller than
type inequlaity.
• Consider the polyhedron P = {x ∈ R
4
|
Ax ⪰ b} where
A =
a
⊤
1
a
⊤
2
. . .
a
⊤
5
∈ R
5×4
, b =
b
1
b
2
. . .
b
5
∈ R
5
.
Consider a feasible point
˜
x ∈ P, where
a
⊤
i
˜
x = b
i
for i ∈ {1, 3, 5} and a
⊤
i
˜
x > b
i
for
i ∈ {2, 4}. At
˜
x, we have
A
˜
x
active
=
a
⊤
1
a
⊤
3
a
⊤
5
∈ R
3×4
, A
˜
x
nonactive
=
a
⊤
2
a
⊤
4
∈ R
2×4
.
• Fact 1: Strong duality in linear programming problems (LPs).
Strong duality does not hold in LPs if and only if both primal and
dual problems are infeasible.
• Fact 2: Extreme point of a polyhedron. Consider the polyhedron
P = {x | Ax ⪰ b} where A ∈ R
m×n
, b ∈ R
m
with m ≥ n. A point
˜
x ∈ P is an extreme point of P if rank(A
˜
x
active
) = n.
• Fact 3: Extreme ray of a recesion cone and a polyhedron. Con-
sider the recesion cone C = {x | Ax ⪰ 0}, where A ∈ R
m×n
,
b ∈ R
m
with m ≥ n. A point
˜
r ∈ C is an extreme ray of C if
rank(A
˜
r
active
) = n − 1. An extreme ray of C is also called the the
extreme ray of the underlying polyhedron {x | Ax ⪰ b}.
solving mixed-integer optimization problems using benders decomposition 2
• Fact 4: Optimal cost of an LP. Consider the LP
minimize
x∈R
d
c
⊤
x
subject to Ax ⪰ b.
where A ∈ R
m×n
, b ∈ R
m
with the feasible set {x | Ax ⪰ b} having
at least one extreme point. Then,
– [Bertsimas and Tsitsiklis, 1997, Theorem 4.14] The polyhedron
{x | Ax ⪰ b} can have only a finite number of extreme points
and extreme rays.
– [Bertsimas and Tsitsiklis, 1997, Theorem 4.14] The optimal cost
of this problem is −∞ if and only if some extreme ray r of {x |
Ax ⪰ b} satisfies c
⊤
r < 0 . In other words, the optimal cost
of this problem is finite if and only if for every extreme ray r of
{x | Ax ⪰ b}, we have c
⊤
r ≥ 0.
– [Bertsimas and Tsitsiklis, 1997, Theorem 2.7] If the optimal cost
of this problem is finite, then there exists an optimal solution
which is an extreme point of {x | Ax ⪰ b}.
Mixed-integer optimization problem to solve.
We want to solve the following mixed-integer optimization problem
(MIP):
p
⋆
=
maximize
x∈Z
n
, v∈R
p
c
⊤
1
x + c
⊤
2
v
subject to A
1
x + A
2
v ⪯ b,
x ⪰ 0, v ⪰ 0,
(P)
where A
1
∈ R
m×n
, A
2
∈ R
m×p
, b ∈ R
m
, c
1
∈ R
n
, c
2
∈ R
p
. We will
assume that p
⋆
is finite and denote the optimal solution by x
⋆
, v
⋆
.
Note that we are not saying anything about the boundedness of the
feasible set.
Problem (P) for fixed x
′
∈ Z
n
+
.
Let us consider some x
′
∈ Z
n
+
, i.e., some fixed integer-valued x
′
⪰ 0,
and define:
p
⋆
(x
′
) =
maximize
v∈R
p
c
⊤
1
x
′
+ c
⊤
2
v
subject to A
1
x
′
+ A
2
v ⪯ b,
v ⪰ 0.
= c
⊤
1
x
′
+
maximize
v∈R
p
c
⊤
2
v
subject to A
2
v ⪯ b − A
1
x
′
,
v ⪰ 0.
solving mixed-integer optimization problems using benders decomposition 3
= c
⊤
1
x
′
−
minimize
v∈R
p
−c
⊤
2
v
subject to A
2
v ⪯ b − A
1
x
′
, ▷ d.v. u ⪰ 0
−v ⪯ 0. ▷ d.v. λ ⪰ 0
|
{z }
p
⋆
sub
(x
′
)
= c
⊤
1
x
′
− p
⋆
sub
(x
′
). (P(x
′
))
Any x ∈ Z
n
+
such that p
⋆
(x) is finite, is called an admissible solu-
tion. As p
⋆
is finite, we can write
p
⋆
= max
x∈Z
n
+
,
x:admissible
p
⋆
(x). (1)
Clearly the optimal x
⋆
to (P) is an admissible solution.
Dual of the minimization problem associated with p
⋆
sub
(x
′
).
We will follow the style of [Boyd and Vandenberghe, 2004, Chapter
5]. The Lagrangian of the minimization problem associated with
p
⋆
sub
(x
′
) is:
L(v, u, λ) = −c
⊤
2
v + u
⊤
A
2
v − (b − A
1
x
′
)
− v
⊤
λ
=
−c
2
+ A
⊤
2
u − λ
⊤
v − u
⊤
(b − A
1
x
′
),
with the dual function:
g(u, λ) = inf
v
L(v, u, λ) =
−u
⊤
(b − A
1
x
′
), if − c
2
+ A
⊤
2
u − λ = 0,
−∞, else.
As a result, the dual problem of the minimization problem associ-
ated with p
⋆
sub
(x
′
) is:
d
⋆
sub
(x
′
) =
maximize
u∈R
m
, λ∈R
p
−(b − A
1
x
′
)
⊤
u
subject to −c
2
+ A
⊤
2
u − λ = 0,
u ⪰ 0, λ ⪰ 0.
=
maximize
u∈R
m
, λ∈R
p
−(b − A
1
x
′
)
⊤
u
subject to −c
2
+ A
⊤
2
u = λ ⪰ 0,
u ⪰ 0.
=
maximize
u∈R
m
−(b − A
1
x
′
)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
Now, due to weak duality, we always have d
⋆
sub
(x
′
) ≤ p
⋆
sub
(x
′
). For
solving mixed-integer optimization problems using benders decomposition 4
notational convenience, define:
d
⋆
(x
′
) = c
⊤
1
x
′
+
minimize
u∈R
m
(b − A
1
x
′
)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
(D(x
′
))
So, the relationship between (P(x
′
)) and (D(x
′
)) is as follows.
p
⋆
(x
′
) = c
⊤
1
x
′
− p
⋆
sub
(x
′
)
≤ c
⊤
1
x
′
− d
⋆
sub
(x
′
)
= c
⊤
1
x
′
−
maximize
u∈R
m
−(b − A
1
x
′
)
⊤
u
subject to A
⊤
2
u ⪰ c
2
u ⪰ 0.
= c
⊤
1
x
′
+
minimize
u∈R
m
(b − A
1
x
′
)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
= d
⋆
(x
′
) (2)
Relationship between (P), (P(x
′
)) and (D(x
′
)).
We can have two possible relationships
1
between (P), (P(x
′
)) and
1
Note that, the case that (D(x
′
)) does not
have a feasible solution for some x
′
∈ Z
n
+
cannot happen, which we can see as follows.
Suppose (D(x
′
)) does not have a feasible
solution some x
′
∈ Z
n
+
, i.e.,
∃
x
′
∈Z
n
+
d
⋆
(x
′
) = ∞.
This means that the feasible set of
(D(x
′
)), which is the polyhedron
S ≜
u | A
⊤
2
u ⪰ c
2
, u ⪰ 0
= ∅ (which
does not contain x
′
), is empty. This also
means that, d
⋆
(x
′
) = ∞ for some x
′
∈ Z
n
+
also
implies d
⋆
(
˜
x) = ∞ for every
˜
x, be it real or
integer valued.
Recalling Fact 1, in Case 1, for every
˜
x,
(P (
˜
x)) will be either infeasible, i.e., p
⋆
(
˜
x) =
∞ or unbounded, i.e., p
⋆
(
˜
x) = −∞ [Bertsimas
and Tsitsiklis, 1997, Table 4.2, Page 151]. In
other words, (P ) itself will be infeasible or
unbounded. This is a contradiction to our
assumption that p
⋆
is finite for some (x
⋆
, v
⋆
).
(D(x
′
)).
• Case 1. (D(x
′
)) is unbounded for some x
′
∈ Z
n
+
. If (D(x
′
)) is
unbounded for some x
′
∈ Z
n
+
, i.e.,
∃
x
′
∈Z
n
+
d
⋆
(x
′
) = −∞,
then strong duality will hold due to Fact 1, and we will have
∃
x
′
∈Z
n
+
p
⋆
(x
′
) = −∞,
which means that (P(x
′
)) will be infeasible for that x
′
∈ Z
n
+
. This
can happen.
• Case 2. (D(x
′
)) has a finite optimal solution for some x
′
∈ Z
n
+
. If
(D(x
′
)) has a finite optimal solution for some x
′
∈ Z
n
+
, then strong
duality will hold for that x
′
.
So, combining both cases above, we have for every x
′
∈ Z
n
+
,
p
⋆
≥ d
⋆
(x
′
) = p
⋆
(x
′
), (3)
where the inequality follows from (1).
solving mixed-integer optimization problems using benders decomposition 5
Representation of (P) via extreme points of S.
Let us denote the extreme points and extreme rays of the polyhedron
S by E and R, respectively.
Using Fact 4, from 1, we can construct the following integer linear
program, which we then will use to construct the decomposition
algorithm:
p
⋆
=
maximize
x∈Z
n
+
x:admissible
p
⋆
(x)
=
maximize
x∈Z
n
+
x:admissible
c
⊤
1
x +
minimize
u∈R
m
(b − A
1
x)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
=
maximize
x∈Z
n
+
∀
r∈R
(b−A
1
x)
⊤
r≥0
c
⊤
1
x +
minimize
u∈R
m
(b − A
1
x)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
▷ because x being admissible is the
same as ∀
r∈R
(b − A
1
x)
⊤
r ≥ 0 due to
Fact 4.
=
maximize
x∈Z
n
+
∀
r∈R
(b−A
1
x)
⊤
r≥0
c
⊤
1
x +
minimize
u∈R
m
(b − A
1
x)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0.
=
maximize
x∈Z
n
+
∀
r∈R
(b−A
1
x)
⊤
r≥0
c
⊤
1
x + min
u∈E
(b − A
1
x)
⊤
u
▷ because we are enforcing the admis-
sibility, an optimal solution to the inner
LP can be found just by searching over
E (due to Fact 4).
=
maximize
x
c
⊤
1
x + min
u∈E
(b − A
1
x)
⊤
u
subject to ∀
r∈R
(b − A
1
x)
⊤
r ≥ 0,
x ∈ Z
n
+
.
=
maximize
x,t
t
subject to t ≤ min
u∈E
c
⊤
1
x + (b − A
1
x)
⊤
u
,
∀
r∈R
(b − A
1
x)
⊤
r ≥ 0,
x ∈ Z
n
+
.
=
maximize
x,t
t
subject to ∀
u∈E
t ≤ c
⊤
1
x + (b − A
1
x)
⊤
u,
∀
r∈R
(b − A
1
x)
⊤
r ≥ 0,
x ∈ Z
n
+
.
(P
enum
)
One may think that now we can find the optimal solution via
enumeration in (P
enum
). Of course, doing that is impractical, as we
need to know all the extreme points and extreme rays of S, which can
be an astronomically large number. However, we can use (P
enum
) to
construct a decomposition algorithm as follows.
solving mixed-integer optimization problems using benders decomposition 6
Setup for the decomposition algorithm.
• Notation. At k-th iteration (k ∈ {1, 2, 3, . . .}) of the decomposition
algorithm, the subset of E is denoted by E(k) and the subset R is
denoted by R(k).
• Master problem. At iteration k, denote the master problem by
p
⋆
(
E(k), R(k)
)
=
maximize
x,t
t
subject to ∀
u∈E(k)
t ≤ c
⊤
1
x + (b − A
1
x)
⊤
u,
∀
r∈R(k)
(b − A
1
x)
⊤
r ≥ 0,
x ∈ Z
n
+
,
(M(k))
with its solution denoted by x
(k)
, t
(k)
. As (M(k)) is a relaxation of
(P
enum
), we have
p
⋆
≤ p
⋆
(
E(k), R(k)
)
. (4)
• Subproblem. Denote the subproblem by
d
⋆
(x
(k)
) = c
⊤
1
x
(k)
+
minimize
u∈R
m
(b − A
1
x
(k)
)
⊤
u
subject to A
⊤
2
u ⪰ c
2
,
u ⪰ 0,
(S(k))
with its solution denoted by u
(k)
.
Decomposition algorithm.
• Step 1: Initialization. Here k = 1. If the E(1) or R(1) is nonempty,
then go to step 2. If E(1) = R(1) = ∅, let d
⋆
(k) be arbitrarily large
and x
(1)
be any non-negative integer vector and go to Step 3.
• Step 2: Solve the master problem. Solve (M(k)) with the current
value of E(k) and R(k) . There are two possibilities
2
:
2
Note that p
⋆
(k) = −∞ cannot happen. If
p
⋆
(k) = −∞, then (M(k)) is infeasible, and
because (M(k)) is a relaxation of (P
enum
), we
must have (P
enum
) infeasible, which violates
our assumption that p
⋆
is finite.
– If p
⋆
(
E(k), R(k)
)
= ∞, then then (M(k)) is not bounded above.
Set t
(k)
to be an arbitrarily large number and compute an x
(k)
that is a feasible solution to (M(k)) for the fixed value of t
(k)
.
Proceed to step 3. (Note that this case would not happen, if
x ∈ {0, 1}
n
.)
– If p
⋆
(
E(k), R(k)
)
is finite, then we collect x
(k)
, t
(k)
and proceed
to step 3.
Note that for both the cases, we must have
p
⋆
≤ p
⋆
(
E(k), R(k)
)
≤ p
⋆
(
E(k − 1), R(k − 1)
)
,
as M(k − 1) is a relaxation of M(k) and M(k) is a relaxation of (P)
(or (P
enum
)).
solving mixed-integer optimization problems using benders decomposition 7
• Step 3: Solve the subproblem. Solve (S(k)) for the current value
of x
(k)
, t
(k)
. There are two possibilities again:
– If d
⋆
(x
(k)
) = −∞, then we have found one extreme point u
(k)
∈
E and one extreme ray r
(k)
∈ R such that d
⋆
(x
(k)
) can decrease
as much as we vary θ ≥ 0 in u
(k)
+ θr
(k)
. We set E(k + 1)
:
=
E(k) ∪ {u
(k)
} and R(k + 1)
:
= R(k) ∪ {r
(k)
}, i.e., we add the
following constraints lazily to (M(k) ):
t ≤ c
⊤
1
x + (b − A
1
x)
⊤
u
(k)
,
(b − A
1
x
′
)
⊤
r
(k)
≥ 0,
Then we set k
:
= k + 1 and go to Step 2.
– If d
⋆
(x
(k)
) finite, then we have found one optimal solution
u
(k)
∈ E, i.e. u
(k)
is an extreme point of S. Using (3) and (4)
we have:
d
⋆
(x
(k)
) ≤ p
⋆
≤ p
⋆
(
E(k), R(k)
)
. (5)
In this d
⋆
(x
(k)
) finite case, one of two things can happen:
*
If d
⋆
(x
(k)
) =
(
E(k), R(k)
)
, then from (5) we must have, p
⋆
=
d
⋆
(x
(k)
) =
(
E(k), R(k)
)
. So we have found the optimal value
and x
⋆
:
= x
(k)
is an optimal solution to (P). By solving
P(x
(k)
)
, we can compute an optimal v
⋆
:
= v
(k)
to (P).
*
If d
⋆
(x
(k)
) <
(
E(k), R(k)
)
, then we E(k + 1)
:
= E(k) ∪ {u
(k)
},
i.e, we add the following constraints lazily to (M(k))
t ≤ c
⊤
1
x + (b − A
1
x)
⊤
u
(k)
.
Then we set k
:
= k + 1 and proceed to Step 2.
In worst case, the number of iterations of this algorithm is bounded
by |E| + |R|.
Benefits of the algorithm.
When S(k) has an optimal solution with finite objective value, after
step 3, we have a feasible solution to (P) along with a measure of
suboptimality p
⋆
(
E(k), R(k)
)
− d
⋆
(x
(k)
) from (5). So, in practice, even
if we terminate early, we can have a good enough feasible solution
with small suboptimality gap.
References
Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear opti-
mization, volume 6. Athena Scientific Belmont, MA, 1997.
solving mixed-integer optimization problems using benders decomposition 8
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cam-
bridge university press, 2004.
R. Garfinkel and G. Nemhauser. Integer Programming. John Wiley and
Sons, New York, 1972.
