Topics in Combinatorial Optimization
Orlando Lee – Unicamp
10 de abril de 2014
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Agradecimentos
Este conjunto de slides foram preparados originalmente para o
curso T´
opicos de Otimiza¸c˜
ao Combinat´oria no primeiro
semestre de 2014 no Instituto de Computa¸c˜
ao da Unicamp.
Preparei os slides em inglˆes simplesmente porque me deu
vontade, mas as aulas ser˜
ao em portuguˆes (do Brasil)!
Agradecimentos especiais ao Prof. M´
ario Leston Rey. Sem
sua ajuda, certamente estes slides nunca ficariam prontos a
tempo.
Qualquer erro encontrado nestes slide ´e de minha inteira
responsabilidade (Orlando Lee, 2014).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Basic definitions
We need some definitions and notation related to linear
algebra, convexity, polyhedra and linear programming. We
assume some familiarity with these topics and present just the
minimum needed in order to present the following topics:
integral polyhedra
total dual integral (TDI) systems
totally unimodular (TU) matrices
Fix Rn as the grounding vector space. For vectors x, y let xy
denote the inner product of x and y .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Linear independence
A vector v is a linear combination of x1 , . . . , xk if there exist
λ1 , . . . , λk such that
λ1 x1 + · · · + λk xk = v .
We say that vectors x1 , . . . , xk are linearly independent if there do
not exist λ1 , . . . , λk , not all equal to 0, such that
λ1 x1 + · · · + λk xk = 0.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Affine independence
A vector v is an affine combination of x1 , . . . , xk if there exist
λ1 , . . . , λk such that
λ1 x1 + · · · + λk xk = v and λ1 + . . . + λk = 1.
We say that vectors x1 , . . . , xk are affinely independent if there do
not exist λ1 , . . . , λk , not all equal to 0, such that
λ1 x1 + · · · + λk xk = 0 and λ1 + . . . + λk = 0.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Linear and affine independence
So
v is an affine combination of x1 , . . . , xk if and only if
linear combination of x11 , . . . , x1k ,
v
0
or
x1 , . . . , xk are affinely
independent if and only if
x1
xk 0 , . . . , 0 are linearly independent.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
is a
Linear and affine hull
Let X be a subset of Rn . Let
lin(X ) := {λ1 x1 + · · · + λk xk : k > 1, x1 , . . . , xk ∈ X ,
λ1 , . . . , λk ∈ R}
be the linear hull of X .
Let X be a subset of Rn . Let
aff(X ) := {λ1 x1 + · · · + λk xk : k > 1, x1 , . . . , xk ∈ X ,
λ1 , . . . , λk ∈ R, λ1 + . . . + λk = 1}
be the affine hull of X .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Dimension and (affine) rank
The rank of a subset X ⊆ Rn , denote rank(X ), is the size of a
maximal subset of linear independent vectors of X .
From basic linear algebra, we know that every maximal subset of
linearly independent vectors of a set X ⊆ Rn has the same size. So
rank is well-defined.
The affine rank of a subset X ⊆ Rn , denoted aff-rank(X ), is the
size of a maximal subset of affine independent vectors of X .
Exercise. Prove that this concept is well-defined, that is, every
maximal subset of affinely independent vectors of a set X ⊆ Rn
has the same size.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Dimension and (affine) rank
Exercise.
(a) Prove that if 0 ∈ aff(X ) then aff-rank(X ) = rank(X ) + 1.
(b) Prove that if 0 6∈ aff(X ) then aff-rank(X ) = rank(X ).
The dimension of a set X ⊆ Rn is
dim(X ) := aff-rank(X ) − 1.
We say that X ⊆ Rn is full-dimensional if dim(X ) = n.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Dimension and (affine) rank
In linear independence, the vector 0 is privileged.
To generate Rn with linear combinations, we need n linear
independent vectors.
In affine independence, there is no privileged vector.
To generate Rn with affine combinations, we need n + 1 affine
independent vectors.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Convexity
A subset C of Rn is convex if λx + (1 − λ)y ∈ C for every
x, y ∈ C and every λ ∈ R with 0 6 λ 6 1.
A vector v is a convex combination of x1 , . . . , xk if there exist
λ1 , . . . , λk > 0 such that
λ1 x1 + · · · + λk xk = v and λ1 + . . . + λk = 1.
Let X be a subset of Rn . Let
conv(X ) := {λ1 x1 + · · · + λk xk : k > 1, x1 , . . . , xk ∈ X ,
λ1 , . . . , λk > 0, λ1 + . . . + λk = 1}
be the convex hull of X .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Convexity
Theorem. (Carath´eodory, 1911) For any subset X ⊆ Rn and any
vector x ∈ conv(X ), there exist affinely independent vectors
x1 , . . . , xk ∈ X such that x ∈ conv({x1 , . . . , xk }).
Roughly speaking, every element of conv(X ) can be written as a
convex combinatiorn of k affine independent vectors of X , where k
is at most the affine rank of X .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Cones
A subset C of Rn is a (convex) cone if C 6= ∅ and λx + µy ∈ C for
every x, y ∈ C and every λ, µ ∈ R+ .
A vector v is a conic combination of x1 , . . . , xk if there exist
λ1 , . . . , λk > 0 such that
λ1 x1 + · · · + λk xk = v .
Let X be a subset of Rn . Let
cone(X ) := {λ1 x1 + · · · + λk xk : x1 , . . . , xk ∈ X ,
λ1 , . . . , λk > 0}
be the cone generated by X .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Cones
Theorem. (Carath´eodory, 1911) For any subset X ⊆ Rn and any
vector x ∈ cone(X ), there exist affinely independent vectors
x1 , . . . , xk ∈ X such that x ∈ cone({x1 , . . . , xk }).
Roughly speaking, every element of cone(X ) can be written as a
conic combination of k affinely independent vectors of X , where k
is at most the affine rank of X .
In the statement, if we assume that 0 6∈ X , then we can also write
linearly independent vectors instead of affinely independent vectors.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Hyperplanes and half-spaces
A subset H of Rn is a hyperplane if there exist c ∈ Rn \ {0} and
δ ∈ R such that
H = {x : cx = δ}.
We say that the set
S := {x : cx 6 δ}
is a half-space.
If δ = 0 we say that H (S) is a linear hyperplane (half-space).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Polyhedra
A cone C is polyhedral if there is a matrix A such that
C = {x : Ax 6 0}.
Equivalently, C is the intersection of finitely many linear
half-spaces.
Several researchers showed that
a convex cone is polyhedral if and only if is finitely generated
where C being finitely generated means that there exists X such
that C = cone(X ).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Polyhedra
A subset P of Rn is a polyhedron if there exists an m × n matrix A
and a vector b ∈ Rm such that
P = {x : Ax 6 b}.
Equivalently, P is the intersection of finitely many half-spaces.
We say that the system Ax 6 b determines P. An inequality
cx ≤ δ is valid if cx 6 δ holds for every x ∈ P.
A polyhedra or cone is rational if the linear system of inequalities
that determines them contains only rational inequalities (dx 6 δ
with d and δ rational).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Polyhedra
A subset P of Rn is a polytope if there exists X such that
P = conv(X ). It can be shown that
P is a polytope if and only if P is a bounded polyhedron.
For subsets A, B of Rn let
A + B := {a + b : a ∈ A, b ∈ B}.
Minkowski (1936) proved the following fundamental result.
Theorem. A set P is a polyhedron if and only if P = Q + C for
some polytope A and some polyhedral cone C .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Farka’s lemma
Farka’s lemma has several equivalent statements. It characterizes
when a given system of linear (in)equalities Ax 6 b has a feasible
solution (or, the polyhedron determined by the system is
nonempty).
Theorem. Ax 6 b is feasible if and only if yb > 0 for every y > 0
such that yA = 0.
Corollary. Ax = b has a solution with x > 0 if and only if yb > 0
for every y such that yA > 0.
Corollary. Ax 6 b has a solution with x > 0 if and only if yb > 0
for every y > 0 such that yA > 0.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Linear programming
Linear programming concerns the problem of maximizing or
minimizing a linear function over a polyhedron. One of the most
important results in the area is the (strong) duality theorem that
relates two optimization problems – the primal and the dual – by a
minimax equality.
Theorem. Let A be a matrix and b, c be vectors. Then
max{cx : Ax 6 b} = min{yb : y > 0, yA = c}.
There exist several equivalent forms of duality theorem, for
example:
max{cx : Ax 6 b, x > 0} = min{yb : y > 0, yA > c},
max{cx : Ax = b, x > 0} = min{yb : yA > c}.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Complementary slackness
Consider the linear problem:
max{cx : Ax 6 b} = min{yb : y > 0, yA = c}.
By weak duality we have
cx = (yA)x = y (Ax) 6 yb.
So a pair x, y of feasible solutions for the primal and the dual,
respectively, are both optimum if and only if, the inequality holds
with equality.
Equivalently, if and only if the following complementary slackness
conditions hold:
(Ax)i = bi for each i with yi > 0.
There exist other forms of complementary slackness, one for each
pair of primal and dual problems.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Optimality geometrically
Using Carath´eodory’s theorem we can prove the following result.
Theorem. If the optimum value of
max{cx : Ax 6 b} = min{yb : y > 0, yA = c}
is finite, then the minimum is attained by a vector y such that the
rows of A corresponding to the positive components of y are
linearly independent.
Geometrically, this says that c belongs to the cone generated by
the rows of A.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Optimality geometrically
Sketch of proof. Let x ∗ be an optimum solution of the primal and
let δ := cx ∗ . Let y > 0 be a optimum dual solution; so δ = yb.
Then
(c δ) = y [A b],
that is, the vector (c δ) belongs to the cone generated by the rows
of the [A b].
By Carath´eodory’s theorem, c belongs to the cone generated by a
linearly independent subset of rows of this matrix. So we may
assume that the positive entries of y correspond to a submatrix
[A′ b ′ ] of full row rank. By complementary slackness, A′ x ∗ = b ′
and hence, A′ has full row rank.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Faces, facets and vertices
Let P := {x : Ax 6 b} be a polyhedron in Rn . Let c a nonzero
vector and let
δ := max{cx : Ax 6 b}.
The hyperplane H := {x : cx = δ} is called a supporting
hyperplane of P.
A subset F of P is a face of P if F = P or F = P ∩ H for some
supporting hyperplane H of P.
F is a face of P
⇐⇒
F is the set of optimum solutions of
max{cx : Ax 6 b} for some c ∈ Rn .
An inequality cx ≤ δ determines or induces a face F if
F = {x ∈ P : cx = δ}.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Faces, facets and vertices
Equivalently, F is a face of P if and only if
F = {x ∈ P : A′ x = b ′ }
for some subsystem A′ x 6 b ′ of Ax 6 b. So a face itself is a
polyhedron.
An inequality ax 6 β from Ax 6 b is tight or active in a face F if
ax = β holds for every x ∈ F .
An inequality ax 6 β from Ax 6 b is an implict equality if Ax 6 b
implies ax = β.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Faces, facets and vertices
Theorem. Let P := {x : Ax 6 b} be a polyhedron of Rn . Let
A′ x 6 b ′ be a subsystem of implicit equalities in Ax 6 b. Then
dimP = n − rank(A′ ).
A facet is an inclusionwise maximal face F of P with F 6= P.
A system Ax 6 b is minimal or irredundant if each proper
subsystem A′ x 6 b ′ has a solution x not satisfying Ax 6 b.
If a system Ax 6 b is irredundant and P is full-dimensional, then
each of its inequalities determines a facet.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Faces, facets and vertices
A face F of P is minimal if it is an inclusionwise minimal face. Any
minimal face is an affine subspace of Rn and all minimal faces are
translates of each other. They all have dimension n − rank(A).
If each minimal face has dimension 0 then P is called pointed. A
vertex or extremal point of P is an element x such that {x} is a
minimal face. A polytope is the convex hull of its vertices.
For any element z of P = {x : Ax 6 b}, let Az x ≤ bz the
subsystem of Ax 6 b consisting of those inequalities that are
satisfied by z with equality.
Theorem. Let P = {x : Ax 6 b} be a polyhedron in Rn and let
z ∈ P. Then z is a vertex of P if and only if rank(Az ) = n.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Linear programming
In the 60’s Dantzig introduced the Simplex algorithm for
solving linear programming problems. The algorithm was very
efficient in practice but it was known that there were (rare)
cases in which it could take an exponential number of
iterations to converge.
In late 70’s, Kaichyan showed that linear programming
problems could be solved in polynomial time using the
ellipsoid method, which was a method used previously to solve
nonlinear problems. In practice, the algorithm was very slow
and numerically unstable (it uses square root).
In the 80’s, interior points methods were proposed to solve
linear programming problems. The algorithms were
competitive with the Simplex method.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Optimization versus separation
The separation problem with respect to a convex subset P of Rn
consists in given a vector y
(a) either answers correctly that y ∈ P,
(b) or returns a (separating) hyperplane cx = δ such that
P ⊆ {x : dx 6 δ} and cy > δ.
This problem is trivial if P is a polyhedron given by a linear system
of inequalities Ax 6 b.
It is perhaps surprising that this can be solved in some cases even
if the linear system of inequalities has exponential size (on the
dimension).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Optimization versus separation
A classical result of Gr¨
otschel, Lov´
asz and Schrijver (1982) roughly
says that we can solve an optimization problem over
max{cx : x ∈ P}
in polynomial time as long as there is a separation oracle for P,
that is, an efficient algorithm that solves the separation problem.
So P can be given/described implicitly by this oracle.
The exact description of the result is very technical. Moreover, its
proof is very complex and relies on the ellipsoid method.
Informally, it establishes that the optimization problem and its
separation problem are polynomially equivalent.
The result itself has several implications in combinatorial
optimization problems.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Primal-dual method
The primal-dual method is a method for solving LP problems.
Many efficient combinatorial algorithms are based on this idea.
Suppose we want to solve the following LP problem:
max{cx : Ax = b, x > 0}.
The dual problem is
min{yb : yA ≥ c}.
Complementary slackness
xj > 0 ⇒ yaj = cj
where aj denotes the vector corresponding to the column j of A.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Primal-dual method
Idea: let y be a feasible dual solution. Let A= be the submatrix of
A consisting of those columns aj of A for which y aj = cj holds. To
find a feasible primal solution we solve the restricted linear
program:
A= x ′ = b, x ′ > 0.
If such x ′ exists, by adding components 0, we obtain a vector
x > 0 such that Ax = 0 satisfying complementary slackness.
Thus, x and y are optimum solutions of the primal and the dual
problems.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Primal-dual method
On the other hand, if no solution exists, by Farka’s lemma, there
exists y ′ such that y ′ A= > 0 and y ′ b < 0.
Let ǫ be the largest real number such that
(y + ǫy ′ )A > c.
If ǫ = ∞, then the problem is unbounded and the LP is infeasible.
Otherwise, note that ǫ > 0. So (y + ǫy ′ )b < yb.
Start a new iteration with y ← y + ǫy ′ .
The algorithm for the Maximum Weight Perfect Maching
Problem we described uses the primal-dual method.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Integral polyhedra
A vector x is said integral if each of its components is integer.
A polyhedron P is integral if it is rational and each face of P
contains an integral vector. In particular, every vertex is integral.
If P = {x : Ax 6 b} is integral then the LP problem
max{cx : Ax 6 b}
has an integral optimum solution, if it is finite.
Hence, in this case
max{cx : Ax 6 b, x ∈ Zn } = max{cx : Ax 6 b}.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Integral polyhedra
Theorem. Let P be a rational polyhedron in Rn . Then P is
integral if and only if for each rational vector c ∈ Rn , the LP
max{cx : Ax 6 b}
has an integral optimum solution, if it is finite.
Theorem. (Edmonds and Giles, 1977) A rational polyhedron P in
Rn is integral if and only if for each integral vector c ∈ Rn the
value of
max{cx : Ax 6 b}
is integer if it is finite.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Totally unimodular matrices
Totally unimodular matrices play an important role in integer
programming and combinatorial optimization.
A matrix A is totally unimodular (TU) if each square submatrix of
A has determinant in {0, +1, −1}. In particular, each component
of a TU matrix is in {0, +1, −1}.
Theorem. Let A be a TU m × n matrix and let b ∈ Zm . Then the
polyhedron
P := {x : Ax 6 b}.
is integral.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
TU matrices
Sketch of proof. We prove only the case in which P is pointed. Let
x be a vertex of P.
So there exists a submatrix A′ of A consisting of linearly
independent columns of A with rank n such that xj 6= 0 only if the
column aj of A is in A′ .
Let x ′ be the vector obtained from x by deleting the (zero) entries
which do no correspond to columns of A′ . Hence, A′ x ′ = b and
therefore, x ′ = (A′ )−1 b.
(Jump of the cat) From matrix theory each entry of the inverse
(A′ )−1 is equal to a determinant of a cofactor of A divided by the
determinant of A. Since A is TU, this implies that (A′ )−1 is
integral and since b is integral, it follows that x is integral.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
TU matrices
Corollary. Let A be a TU m × n matrix and let b ∈ Zm . Then the
polyhedron
P := {x : Ax = b, x > 0}
is integral.
Proof. Note that P can be described as
A
b
P = x : −A x 6 −b .
−I
0
Since A is TU, the constraint matrix above is also TU and the
result follows from the previous theorem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
TU matrices
Corollary. Let A be a TU m × n matrix, b ∈ Zm and l , u ∈ Zn+ .
Then the polyhedron
P := {x : Ax = b, l 6 x 6 u}
is integral.
Proof. Similar to the previous one.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Two important examples of TU matrices
Let G = (V , E ) be a graph. The incidence matrix of G is the
{0, 1}-matrix M with rows indexed by V and columns indexed by
E such that:
1 if e ∈ δ(v ),
M[v , e] =
0 otherwise.
Let D = (V , A) be a digraph. The incidence matrix of D is the
{0, +1, −1}-matrix M with rows indexed by V and columns
indexed by A such that:
1 if a ∈ δout (v ),
−1 if a ∈ δin (v ),
M[v , a] =
0 otherwise.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Incidence matrices of bipartite graphs are TU
Theorem. Let G be a bipartite graph. Then the incidence matrix
M of G is TU.
Proof. Suppose G = (V , E ) is (X , Y )-bipartite. Then there exist
matrices MX , MY with rows indexed by X and Y respectively,
and both with columns indexed by E such that:
MX
M=
MY
and each MX , MY has exacty one 1 in each column. So if we
add rows in MX by 1 and subtract rows in MY we obtain the
zero vector. So rank(M) 6 |V | − 1.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Incidence matrices of bipartite graphs are TU
Let B a submatrix of M. We prove by induction that
det(B) ∈ {0, +1, −1}. If B has order 1 then det(B) ∈ {0, +1}.
So suppose that B has order at least two. Then B satisfies one of
the following:
(a) every column has exactly two 1’s, or
(b) there exists a column of zeroes, or
(c) there exists a column with exactly one 1.
If (a) or (b) holds then det(B) = 0.
If (c) holds, then assume that B[v , e] = 1. Let B ′ the matrix
obtained from B by deleting row v and column e. Then
det(B) = (−1)v +e det(B ′ ). By induction det(B ′ ) ∈ {0, +1, −1}
and therefore det(B) ∈ {0, +1, −1}.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Incidence matrices of bipartite graphs are TU
Corollary. Let G be a bipartite graph containing a perfect
matching. Then every extreme point of the polytope
x(δ(v )) = 1 for every v ∈ V ,
x(e) > 0 for every e ∈ E
is integral.
Corollary. Let G = (V , E ) be a bipartite graph and w ∈ ZE+ . Then
every extreme point of the polyhedron
y(u) + y (v ) > w(e) for every e = uv ∈ E ,
is integral.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Incidence matrices of digraphs are TU
Theorem. Let D be a digraph.Then the incidence matrix M of D
is TU.
Proof. Let B be a submatrix of M. We prove by induction that
det(B) ∈ {0, +1, −1}. If B has order 1 then det(B) ∈ {0, +1, −1}.
So suppose that B has order at least two. Then B satisfies one of
the following:
(a) every column has exactly one +1 and one −1, or
(b) there exists a column of zeroes, or
(c) there exists a column with exactly one +1 or one −1.
If (a) or (b) holds then det(B) = 0.
If (c) holds, then assume that B[v , e] = ±1. Let B ′ the matrix
obtained from B by deleting row v and column e. Then
det(B) = ±(−1)v +e det(B ′ ). By induction det(B ′ ) ∈ {0, +1, −1}
and therefore det(B) ∈ {0, +1, −1}.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Minimum cost flow/circulation
Let D = (V , A) be a digraph, let b ∈ ZV be a demand/supply
function, let c : A 7→ R be a cost function and let l , u : A 7→ Z+ be
capacity functions. Consider the following problem:
P
max
a∈A c(a)x(a)
s.t. x(δout (v )) − x(δin (v )) = b(v ) for every v ∈ V ,
l(a) 6 x(a) 6 u(a)
for every a ∈ A.
This is known as Minimum Cost Flow/Circulation problem.
This can be rewritten as min{cx : Mx = b, l 6 x 6 u}.
From the total unimodularity of M we have that
P := {x : Mx = b, l ≤ x ≤ u}
is integral.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Minimum cost flow/circulation
min{cx : Mx = b, l 6 x 6 u}.
This can be used to model (and solve) several combinatorial
problems: Shortest Path problem, MaxFlow problem, Directed
Chinese Postman problem etc.
There also exist (several) combinatorial polynomial algorithms for
the Minimum Cost Flow problem. Many real applications can be
modeled as a problem of this type. We will not discuss them here.
Consult the references.
Let us show how to model two well-known problems in this
framework.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Typical problems in this framework
Minimum/shortest st-path problem: take l = 0, u = 1 and
+1 if v = s
b(v ) :=
−1 if v = t
0 otherwise.
If (D, c) contains no negative cycle, then
min{cx : Mx = b, 0 6 x 6 1} is equivalent to the Shortest Path
problem.
If (D, c) contains a negative cycle, the integral solution may not
have any combinatorial interpretation for the Shortest st-Path
problem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Typical problems in this framework
Maxflow problem: add a new arc (t, s) with cost c(t, s) = −1,
take as objective function min x(t, s)c(t, s) = max x(t, s); all the
remaining arcs have zero cost. Take l = 0 and b = 0.
So max{x(t, s) : Mx = 0, 0 6 x 6 u} is equivalent to the
Maxflow problem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Integral polyhedra
Edmonds (1965) in a seminal paper characterized the perfect
matching polytope of a graph G = (V , E ).
More precisely, let
MG := {χM : M is a perfect matching of G }.
The matching polytope of G is Ppm (G ) := conv(MG ).
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Perfect matching polytope
We have seen that when G = (V , E ) is bipartite then Ppm (G ) is
determined by
x(δ(v )) = 1 for every v ∈ V ,
x(e) > 0 for every e ∈ E .
If G is not bipartite, then the previously result does not necessarily
hold.
However, Edmonds showed a nice characterization of Ppm (G ),
albeit with an exponential number of constraints.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Perfect matching polytope
Let G = (V , E ) a graph with a perfect matching (so |V | is even).
We say that a cut δ(X ) is odd if |X | is odd. It is easy to see that if
δ(X ) is an odd cut and M is a perfect matching then
|M ∩ δ(X )| > 1 (in fact, it must be odd).
Theorem. (Edmonds, 1965) Let G = (V , E ) be a graph. Then
Ppm (G ) is determined by:
x (δ(v )) = 1 for every v ∈ V ,
x (δ(X )) > 1 for every X ⊆ V odd,
x(e) > 0 for every e ∈ E .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Integral polyhedra
How can we show that such description is actually complete, that
is, those linear inequalities do determine Ppm (G )?
There are some possibilities:
using standard arguments from polyhedral combinatorics, or
showing that for any objective function, the corresponding
linear programming problem has always an integral optimum
solution.
We will not use the first method, but a more refined approach of
the second one.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
TDI systems
A system Ax 6 b is totally dual integral (TDI) if A and b are
rational and for every integral vector c ∈ Zn , the dual problem in:
min{cx : Ax 6 b} = max{yb : yA = c, y > 0}
has an integral optimum solution y , if it exists.
The importance of this concept comes from the following result of
Edmonds and Giles (1977).
Theorem. If Ax 6 b is TDI and b is integral, then Ax 6 b
determines an integral polyhedron.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
TDI systems
We list some useful results.
Theorem. Suppose Ax > 1, x > 0 is a TDI system. Then the
system Ax > 1, 0 6 x 6 1 is also TDI.
Theorem. A system Ax 6 b, x ≥ 0 is TDI if and only if for every
c ∈ Zn the dual in:
min{cx : Ax 6 b, x > 0} = max{yb : yA > c, y > 0}
has an integral optimum solution y , if it exists.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
The perfect matching polytope
Theorem. Let G = (V , E ) be a graph. Then the system
x (δ(v )) = 1 for every v ∈ V ,
x (δ(X )) > 1 for every X ⊆ V odd,
x(e) > 0 for every e ∈ E .
is TDI. Furthermore, it determines Ppm (G ).
A typical way to prove this is to design an (primal-dual) algorithm
that finds an integral optimal dual solution (and an integral
optimum primal solution) for each integral vector c. In the result
above, this is complicated, but we will show some other examples.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Path polyhedra
Let D = (V , A) be a digraph and let s, t ∈ V with s 6= t. Let
Pst-path (D) := conv{χP : P is an st-path of D}.
Since the problem of finding a longest st-path is NP-hard, there is
little hope of finding a complete characterization of Pst-path (D).
↑
(D) of Pst-path (D).
However, we can consider the dominant Pst-path
Formally, the dominant of a polyhedron P is the polyhedron P ↑
consisting of vectors x such that x > z for some z ∈ P.
Equivalently, P ↑ = P + RA
+.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Path polyhedra
Consider the LP problem:
P
min
a∈A c(a)x(a)
s.a x(δout (X )) > 1 for every s t¯-set X ,
x(a) > 0
for every a ∈ A.
and its dual:
max
s.a
P
P
X
yX
X :a∈δ(X ) y X
yX > 0
6 c(a) for every a ∈ A,
for every s t¯-set X .
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Packing st-cuts
When c is integral, then an integral dual solution corresponds to a
collection C of st-cuts such that each arc a ∈ A belongs to at most
c(a) st-cuts in C.
We have seen the following result (Exercise).
Theorem. Let D = (V , A) be a digraph, let s, t ∈ V with s 6= t
and let c : A 7→ Z+ a capacity function. Then the length of a
shortest (weighted) st-path is equal to maximum size of a
collection C of st-cuts such that each arc a ∈ A belongs to at most
c(a) st-cuts in C.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Path polyhedra
Theorem. Let D = (V , A) be a digraph and let s, t ∈ V with
s 6= t. Then the system
x(δ(X )) > 1 for every s t¯-set X ,
x(a) > 0 for every a ∈ A.
↑
(D).
is TDI. Furthermore, it determines Pst-path
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Cut polyhedra
Let D = (V , A) be a digraph and let s, t ∈ V with s 6= t. Let
Pst-cut (D) := conv{χC : C is an st-cut of D}.
Again, there is little hope of finding a system describing this
polytope, because MaxCut is NP-hard.
↑
(D) rather than Pst-cut (D).
So we consider the dominant Pst-cut
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Cut polyhedra
Consider the LP problem:
P
min
a∈A c(a)x(a)
s.a x(P) > 1
x(a) > 0
for every st-path P,
for every a ∈ A.
and its dual:
max
s.a
P
P
P
yP
P:a∈A(P)
y P 6 c(a) for every a ∈ A,
yP > 0
Orlando Lee – Unicamp
for every st-path P.
Topics in Combinatorial Optimization
Packing st-paths
When c is integral, then an integral dual solution corresponds to a
collection P of st-paths such that each arc a ∈ A belongs to at
most c(a) st-paths in P.
We have seen the following result.
Theorem. (Integral MaxFlow MinCut Theorem) Let D = (V , A) be
a digraph, let s, t ∈ V with s 6= t and let c : A 7→ Z+ a capacity
function. Then the weight of a minimum st-cut is equal to
maximum size of a collection P of st-paths such that each arc
a ∈ A belongs to at most c(a) st-paths in P.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Cut polyhedra
Theorem. Let D = (V , A) be a digraph and let s, t ∈ V with
s 6= t. Then the system
x(P) > 1 for every st-path P,
x(a) > 0 for every a ∈ A.
↑
(D).
is TDI. Furthermore, it determines Pst-cut
Note that the dual problem consists in finding a maximum
(fractional) packing of st-paths. So, it is equivalent to the
MaxFlow problem (recall the Flow Decomposition Theorem). It
provides another polyhedral formulation of the MaxFlow problem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Chain polytope
Let (S, 4) be a poset. Let
Pchain (S) := conv{χC : C is a chain of S}.
Theorem. Let (S, 4) be a poset. Then the system
x(A) 6 1 for every antichain A,
x(s) > 0 for every s ∈ S.
is TDI. Furthermore, it determines Pchain (D).
This follows from the weighted Mirsky’s theorem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
Antichain polytope
Let (S, 4) be a poset. Let
Pantichain (S) := conv{χA : A is an antichain of S}.
Theorem. Let (S, 4) be a poset. Then the system
x(C ) 6 1 for every chain C ,
x(s) > 0 for every s ∈ S.
is TDI. Furthermore, it determines Pantichain (D).
This follows from the weighted Dilworth’s theorem.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
References
A. Schrijver, Theory of Linear and Integer Programming,
Wiley. (a classic book)
C.E. Ferreira and Y. Wakabayashi, Combinat´oria Poli´edrica e
Planos-de-Corte Faciais. (Escola de Computa¸c˜ao)
A. Schrijver, Combinatorial Optimization, Vol. A, Springer.
A. Frank, Connections in Combinatorial Optimization, Oxford.
Orlando Lee – Unicamp
Topics in Combinatorial Optimization
© Copyright 2024 ExpyDoc
