Complementary Slackness and More Dual Examples
October 20, 2006
Complementary Slackness
We begin by looking at the notion of complementary slackness.
Consider the following primal LP and its dual:
Primal: min cx, Ax = b, \(x\geq 0\)
Dual: max yb, \(yA \leq
c\)
We can rewrite the dual using slack variables s to put it in the
form:
Dual: max yb, yA + s = c, \(s
\geq 0\)
Using this formulation, we arrive at the following lemma.
Lemma: The following are all equivalent:
(i) x, y are optimal
(ii) \(s\cdot x = 0\)
(iii) \(x_{j}s_{j} = 0\) \(\forall j\)
(iv) \(s_{j} \geq 0 \rightarrow x_{j} =
0\)
Proof. First note that (iii) and (iv) are just restatements
of (ii). Therefore we only need to show (i) and (ii) are
equivalent.
(i) \(\leftrightarrow\) (ii): x, y are
both optimal if and only if cx = yb (by strong duality) and cx = yb can
be rewritten as (yA + s)x = yAx which holds if and only if \(s \cdot x = 0\)
◻
The interpretation of this lemma is the following. At the optimum, it is
not possible to have \(x_j\) and \(s_j\) both ’slack’. At least one of them
has to be at the limit. Conversely, if at least one of the two is tight
for every j, then the point is an optimum. We will see how this notion
of complementary slackness can be used to gain insight in our analysis
of the following dual problems.
Two Dual Examples
Max Flow
Consider the max flow problem on a graph G with source node s and
sink node t. In order to formulate this problem as an LP, we augment G
with an extra edge from t to s having infinite capacity. Then the LP is
to maximize the flow along that edge while requiring the flow to be both
feasible (obey the capacity constraints) and a circulation:
Letting \(x_{u,v}\) be the flow value
on edge (u, v), we can then write the primal LP as:
Primal: max \(x_{t,s}\) subject to:
\(\sum_{w}x_{v,w} - x_{w,v} = 0\) \(\forall v\) (flow is a circulation)
\(x_{v,w} \leq u_{v,w}\) \(\forall (v,w)\) (flow values do not exceed
capacities)
\(x_{v,w} \geq 0\) \(\forall (v,w)\) (flow values are all
positive)
What is the dual for this LP? We introduce a variable for every
constraint in the primal problem: a variable \(z_v\) for each of the constraints on each
node (the circulation constraints) and a variable \(y_{v,w}\) for each of the capacity
constraints. Then by following the ’cookbook method’ for finding duals
as described in previous lectures we get the following dual
problem.
Dual: min \(\sum
u_{v,w}y_{v,w}\) subject to:
\(y_{v,w} \geq 0\)
\(z_v - z_w + y_{v,w} \geq 0\) \(\forall (v,w) \neq (t,s)\)
\(z_t - z_s + y_{t,s} \geq 1\)
We can first simplify this by noting that since \(u_{t,s} = \infty\), an optimal solution to
the dual must have \(y_{t,s} = 0\).
Using this and moving terms in the constraints allows us to rewrite them
as:
\(y_{v,w} \geq 0\)
\(z_w \leq z_v + y_{v,w}\) \(\forall (v,w) \neq (t,s)\)
\(z_t - z_s \geq 1\)
Using the above, we can interpret the dual problem in the following way.
Consider the \(u_{v,w}\) as cross
section areas, and the \(y_{v,w}\) as
lengths. Then the problem is to minimize the total volume, while
maintaining a distance of at least 1 between nodes s and t.
As a sanity check for what we have done, let (S,T) be a min s-t cut on
G. Set \(y_{v,w} = 1\) for all edges
crossing the cut and \(y_{v,w} = 0\)
for all other edges. This is a feasible solution to the dual problem and
the objective function in the dual takes on value \(\sum_{v \in S, w \in T} u_{v,w}\) which is
just the value of the min-cut. Therefore, by weak duality the value of
the primal is no greater than the value of the dual, and so we have
shown that max-flow \(\leq\)
min-cut.
Now, let’s see what further insight we can gain by using the
complementary slackness results proven earlier. First, note that for any
solution of the dual, we can subtract the same value from all \(z_{w}\) without changing the value of the
objective function or breaking any of the constraints. Therefore, we can
choose to have \(z_s = 0\). This is
equivalent to having the \(z_{w}\)
represent distances from node s.
Now consider an optimal solution to the dual problem (with the choice as
above of \(z_s = 0\)). Let \(S = \{v \mid z_v < 1\}\) and \(T = V \smallsetminus S\). Then
S,T is an s-t cut.
For any edge (v,w) crossing the cut from S to T, we have \(y_{v,w} \geq z_w - z_v > 0\). Therefore,
for these edges, the variables \(y_{v,w}\) are not 0. Since we are at an
optimum point, by complementary slackness, the corresponding constraint
for the primal problem must be tight. The constraint corresponding to
the variable \(y_{v,w}\) is \(x_{v,w} \leq u_{v,w}\). Therefore we must
have that \(x_{v,w} = u_{v,w}\) for all
edges (v,w) crossing the cut from S to T.
Similarly, consider any edge (v,w) crossing the cut from T to S. From
the definition of S and T, we know that \(z_v
> z_w\) and since \(y_{v,w} \geq
0\) we must have \(z_v + y_{v,w} >
z_w\). Therefore, the constraint \(z_v
+ y_{v,w} \geq z_w\) is not tight and so the corresponding
variables in the primal must be zero and so \(x_{v,w} = 0\).
Therefore, the flow on all edges from S to T is at capacity, and the
flow on all edges from T to S is 0, and so the flow on the graph is
equal to the capacity of the cut given by (S,T). Therefore, using
complementary slackness we have proven the max flow = min-cut
theorem.
Min-Cost Circulation
We can quickly find an LP for min-cost circulation by noting that the
formulation is very similar to that for max-flow. In particular, none of
the constraints need to be changed. The only difference is that we now
want a circulation and we want to minimize cost, and so only the
objective function needs to be changed. The primal LP then
becomes:
Primal: min \(\sum
c_{v,w}x_{v,w}\) subject to:
\(\sum_{w}x_{v,w} - x_{w,v} = 0\) \(\forall v\) (flow is a circulation)
\(x_{v,w} \leq u_{v,w}\) \(\forall (v,w)\) (flow values do not exceed
capacities)
\(x_{v,w} \geq 0\) \(\forall (v,w)\) (flow values are all
positive)
Because only the objective function on the primal has changed, the only
change in the dual problem is on the constraints and the sign of the
objective. The dual LP becomes:
Dual: max \(\sum
u_{v,w}y_{v,w}\) subject to:
\(y_{v,w} \leq 0\)
\(z_v - z_w + y_{v,w} \leq
c_{v,w}\)
Let \(p_v = - z_v\). Then the dual
problem can be rewritten as:
Dual: max \(\sum
u_{v,w}y_{v,w}\) subject to:
\(y_{v,w} \leq 0\)
\(y_{v,w} \leq c_{v,w} + p_v -
p_w\)
If we consider the \(p_v\) to be
prices, then the dual problem is to maximize the weighted sum of the
arcs of negative reduced cost.
Again, we use the results of complementary slackness to see what further
insight we can gain. Suppose that \(x_{v,w}
< u_{v,w}\). Then the constraint \(x_{v,w} \leq u_{v,w}\) isn’t tight and so
the corresponding variable in the dual \(y_{v,w} = 0\). If the reduced cost \(c^p_{v,w} < 0\) then \(y_{v,w} < 0\) and so \(x_{v,w} = u_{v,w}\). So negative reduced
cost arcs must be saturated.
Similarly, suppose \(c^p_{v,w} >
0\). Then the constraint \(y_{v,w} \leq
c_{v,w} + p_v - p_w\) must be slack (since \(y_{v,w} \leq 0\)) and so the corresponding
variable in the primal \(x_{v,w} = 0\).
Therefore, positive reduced cost arcs must have zero flow.
Therefore, using complementary slackness we have proven that in a
min-cost flow negative reduced cost arcs are saturated and positive
reduced cost arcs have zero flow.