Discrete (And Continuous) Optimization WI4 131: November - December, A.D. 2004
Discrete (And Continuous) Optimization WI4 131: November - December, A.D. 2004
Discrete (And Continuous) Optimization WI4 131: November - December, A.D. 2004
WI4 131
Kees Roos
Technische Universiteit Delft
Faculteit Informatietechnologie en Systemen
Afdeling Informatie, Systemen en Algoritmiek
e-mail: C.Roos@ewi.tudelft.nl
URL: http://ssor.twi.tudelft.nl/roos
November December, A.D. 2004
Course Schedule
1. Formulations (18 pages)
2. Optimality, Relaxation, and Bounds (10 pages)
3. Well-solved Problems (13 pages)
4. Matching and Assigments (10 pages)
5. Dynamic Programming (11 pages)
6. Complexity and Problem Reduction (8 pages)
7. Branch and Bound (17 pages)
8. Cutting Plane Algorithms (21 pages)
9. Strong Valid Inequalities (22 pages)
10. Lagrangian Duality (14 pages)
11. Column Generation Algorithms (16 pages)
12. Heuristic Algorithms (15 pages)
13. From Theory to Solutions (20 pages)
Optimization Group 1
Capter 3
Well-Solved Problems
Optimization Group 2
Properties of Easy Problems
For the moment we say that an algorithm on a graph G = (V, E) with n nodes and m
edges is ecient if, in the worst case, the algorithm requires O(m
p
) elementary calculations
(such as additions, divisions, comparisons, etc.) for some integer p. We assume m n.
(COP) z = max
c
T
x : x X R
n
Denition 1 The Separation Problem associated with (COP) is the problem: Given x
R
n
, is x conv (X)? If not, nd an inequality
T
x
0
satised by all points in X,
but violated by the point x
, i.e.,
T
x
>
0
. The plane
T
x =
0
is called a separating
plane.
For easy problems, i.e., problems for which there exists an ecient algorithm, the following
properties often go together:
(i) Ecient Optimization Property;
(ii) Strong Dual Property;
(iii) Ecient Separation Property;
(iv) Ecient Convex Hull Property.
Optimization Group 3
IPs with Totally Unimodular Matrices
Consider the following IP:
(IP) z = max
c
T
x : Ax b, x Z
n
+
We assume that A and b are integral. If we are lucky, then the linear relaxation
(LP) z
LP
= max
c
T
x : Ax b, x R
n
+
has an optimal solution that is integral. When can we guarantee this to happen?
From LO theory, any basic feasible solution has the form x = (x
B
, x
N
) = (B
1
b, 0),
where B is an mm nonsingular submatrix of (A, I), with I the mm identity matrix.
Observation 1 If the optimal basis B is unimodular, i.e., satises det(B) = 1, then
(LP) solves (IP).
Denition 2 The matrix A is called Totally Unimodular (TU) if every square submatrix of
A has determinant +1, 1 or 0.
Observation 2 If A is TU then a
ij
{+1, 1, 0} for all i, j.
Optimization Group 4
Properties of TU Matrices
Proposition 1 A is TU A
T
is TU (A, I) is TU.
Proposition 2 A is TU if
(i) a
ij
{+1, 1, 0} for all i, j.
(ii) Each column of A contains at most 2 nonzero elements.
(iii) There exists a partition (I, J) of the row indices such that for each column j with 2
nonzero elements one has
iI
a
ij
=
iJ
a
ij
.
Proof: Assume A is not TU, and let B be the smallest square submatrix for which det B / {+1, 1, 0}.
Then every column of B contains two nonzero elements. Now adding the rows of B in I and subtracting the
rows of B in J gives the zero vector, and so det B = 0, a contradiction.
Proposition 3 Given A, the LO problem (LP) has an integral optimal solution for all
integer vectors b for which it has an optimal solution, if and only if A is TU.
The last proposition implies that if A is TU, then the given IP can be solved by solving its LP
relaxation. It also implies that the Strong Dual Property, the Ecient Separation Property
and the Ecient Convex Hull Property hold.
It also has the Ecient Optimization Property, but this is less trivial, and goes beyond the
scope of this course. Among other things this requires an ecient algorithm for recognizing
TU, which indeed exists!
Optimization Group 5
Minimum Cost Network Flows
Given a digraph (or network) D = (V, A) with arc capacities h
ij
for all (i, j) A, demands
b
i
at each node i V , and unit ow costs c
ij
for all (i, j) A, the minimum cost network
ow problem consists of nding a feasible ow that satises all the demands at minimum cost.
The problem can be modelled as an LO problem:
min
(i,j)A
c
ij
x
ij
kV
+
(i)
x
ik
kV
(i)
x
ki
= b
i
, i V
0 x
ij
h
ij
, (i, j) A
where x
ij
denotes the ow in arc (i, j),
V
+
(i) = {k : (i, k) A} and
V
h
ij
c
T
x : Ax = b, 0 x h
.
We proceed by considering two special cases.
The Shortest Path Problem: Given two distinguished nodes s and t in V , and nonnegative
arc costs c
ij
, for (i, j) A, nd a minimum cost s-t path.
The Max Flow Problem: Given two distinguished nodes s and t in V , and nonnegative
capacities h
ij
, for (i, j) A, nd a maximum ow from s to t.
The shortest path problem is the special case of the general minimum cost ow problem with
c 0, h
ij
= for all (i, j) A, and b
s
= 1, b
t
= 1 and b
i
= 0 for i / {s, t}, but
with the additional requirement that x
ij
{0, 1} for all (i, j) A.
By adding an extra arc (t, s) to the network, the max ow problem can be characterized as
follows: b is the zero vector, and c
ij
= 0 for all arcs, except c
ts
= 1.
Optimization Group 9
The Shortest Path Problem
With A equal to the node-arc incidence matrix of the network D = (V, A) and b
s
= 1,
b
t
= 1 and b
i
= 0 for i / {s, t}, the shortest path problem can be written as
z = min
c
T
x : Ax = b, x 0, x integer
.
The linear relaxation is
z
LP
= min
c
T
x : Ax = b, x 0
.
By the duality theorem for LO we have
z
LP
= max
b
T
y : A
T
y c
.
Due to the denition of b, the dual object function is simply y
s
y
t
. The constraints can be
reformulated as
y
i
y
j
c
ij
, (i, j) A.
Changing the variable vector y to , putting
s
= 0, and using that z = z
LP
, because
A is TU, we have the following result.
Theorem 1 z is the length of a shortest s-t path if and only if there exist values
i
, for
i V such that
s
= 0,
t
= z and
j
i
c
ij
for all (i, j) A.
Optimization Group 10
The Max Flow Problem
Using the node-arc incidence matrix
A of the network D = (V, A {(t, s)}), the max ow problem is
z = max
x
ts
:
Ax = 0, 0 x
ij
h
ij
for (i, j) A
.
By the duality theorem for LO we have, with w
ts
= 0,
z = min
h
T
w :
A
T
u +w c, w 0
= min
(i,j)A
h
ij
w
ij
: u
i
u
j
+w
ij
0, u
t
u
s
1, w 0
Since
A is TU, both problems have integer optimal solutions. Moreover, we may take u
s
= 0. Given integer
optimal solutions x, u and w, we dene
X = {i V : u
i
0} ,
X = V \ X = {j V : u
j
1} .
Now
(i,j)A
h
ij
w
ij
(i,j)A,iX,j
X
h
ij
w
ij
(i,j)A,iX,j
X
h
ij
since w
ij
u
j
u
i
1 for i X, j
X. However, taking u
i
= 0 for i X, u
j
= 1 for j
X, w
ij
= 1
for i X, j
X and w
ij
= 0 otherwise, we have equality throughout, and hence this {0, 1}-solution is
optimal. Note that s X and t
X. For any set of nodes X with s X and t / X, the set of arcs
A
+
(X) :=
(i, j) A : i X, j
X
(i,j)A
+
(X)
h
ij
. We have proved the following theorem:
Theorem 2 A strong dual to the max s-t ow problem is the minimum s-t cut problem:
min
X
(i,j)A
+
(X)
h
ij
: s X V \ {t}
.
Optimization Group 11
Optimal Trees
Denition 3 A forest in a graph G = (V, E) is a subgraph G
= (V, E
) containing no
cycles.
Denition 4 A tree in a graph G = (V, E) is a subgraph G
= (V, E
) that is a forest
and is connected (i.e. contains a path between every pair of nodes).
Proposition 5 Let n = |V | and m = |E|. The following ve statements are equivalent:
(i) G is a tree.
(ii) G is a forest and m = n 1.
(iii) G is an edge-minimal connected graph spanning V .
(iv) G contains a unique path between every pair of nodes.
(v) Addition of an edge to E creates a unique cycle in G.
The Maximum Weight Forest (Tree) Problem: Given a graph G = (V, E) and edge
weights c
e
for e E, nd a maximum weight subgraph that is a forest (tree).
Surprisingly enough, this problem, which has many practical applications, can be solved by a
greedy algorithm.
Optimization Group 12
Greedy Algorithm for he Maximum Weight Forest (Tree) Problem
The method is very simple: Fist order the edges according to nonincreasing cost, and then seek
to use them in this order without destroying the forest structure; proceed until the number of
accepted arcs is n 1. Below we present an example.
1
2 4
3
5
6
7
5
9
10
3
3
5
6 12
9
2
4
6
9
8
1
2 4
3
5
6
7
5
9
10
3
3
5
6 12
9
2
4
6
9
8
edge weight used? cum. weight
e
1
{3, 4} 12 yes 12
e
2
{1, 5} 10 yes 22
e
3
{1, 3} 9 yes 31
e
4
{3, 6} 9 yes 40
e
5
{5, 6} 9 no
e
6
{6, 7} 8 yes 48
e
7
{5, 7} 6 no
e
8
{2, 6} 6 yes 54
Optimization Group 13
Correctness of the Greedy Algorithm
Theorem 3 (Kruskal, 1956) The greedy algorithm terminates with a maximal weight tree.
The theorem is an immediate consequence of the following lemma (due to L. Schrijver). Call
a forest F greedy if there exists a maximum weight tree T of G that contains F.
Lemma 1 Let F be a greedy forest, U one of its components and e (U). If e has
maximal length among all edges in (U) then F {e} is again a greedy forest.
U
e
P
y
Proof: Let T be a maximum weight tree containing F.
Let P be the unique path in T connecting the end vertices
of e. Then P contains at least one edge y that belongs
to (U). So T
) c(T).
Therefore, T
,
it follows that F {e} is a greedy forest.
Optimization Group 14
Linear Model for the Maximum Weight Tree Problem
The number of elementary operations during the execution of the greedy algorithm is O(m).
So the algorithm is polynomial and the maximum weight tree problem has the Ecient Op-
timization Property. What about the other three properties? To deal with this question we
need an IP model for the problem. The basic problem in this is how to avoid cycles. But we
have seen how to achieve this for TSP. Thus the following model is clear:
max
eE
c
e
x
e
eE
x
e
|S| 1, S V, 2 |S| n
x
e
0, for e E, x Z
|E|
.
Theorem 4 The convex hull of the incidence vectors of the forests in G is given by the
constraints in the above model.
By this theorem the Convex Hull Property holds. One may show that the Ecient Separation
property holds as well (Book of Wolsey, Section 3.6). What about the Strong Dual Property?
Optimization Group 15
The Steiner Tree Problem
An interesting and important generalization of the Maximum Weight Tree Problem problem
is the following problem.
Given a graph G = (V, E) and a set of terminals T V , a Steiner tree on T is an edge-
minimal acyclic subgraph of G containing a path joining every pair of nodes in T. Such a
subgraph may or may not contain edges incident to the nodes in V \ T.
Given weights c
e
on the edges, the Optimal Steiner Tree Problem is to nd a Steiner tree
with minimum weight.
Observe that when T = V then this is the optimal tree problem, and if |T| = 2, it is the
shortest path problem.
Optimization Group 16