15-451 Algorithms 10/28/09
recitation notes
* solution to 1(b) on mini 4. Make sure everyone understands residual graphs.
* basic setup of LP. Code up flow problem in mini4 as LP.
* two more examples of coding up a problem as an LP.
=================================================================
Another example of coding up a problem as an LP
===============================================
Let's see if we can code up the shortest-path problem as an LP.
Input: directed graph G with lengths on the edges, start s, dest t.
Let's have a variable x_e for each edge e, all in [0,1].
(think of x_e=1 meaning we use that edge, and x_e=0 meaning we don't, but
of course the LP might assign fractional values)
Goal is to minimize sum_e length(e)*x_e, subject to:
Sum of x_e out of s equals 1.
Sum of x_e into t equals 1.
For any vertex v, flow in equals flow out.
But what if the LP solver returns fractional values? The claim is that in
that case, all paths from s to t that you get by following non-zero x_e's
are shortest paths (otherwise you could get a better LP solution by rerouting
that flow on the shortest path).
OK, so we really coded this problem up as a min-cost flow, but it is
interesting to think of it as an LP. We got lucky here that the fractional
values didn't hurt us. For other problems (e.g., like the ones we will see
in the next lectures like 3SAT and vertex-cover) you can't necessarily
convert a fractional solution into an integer one.
Yet another example of coding up a problem as an LP
===================================================
Modeling MULTICOMMODITY FLOW as a linear program.
The multicommodity flow problem is just like the standard network flow
problem except we have $p$ sources $s_1, \ldots, s_p$ and $p$ sinks
$t_1, \ldots, t_p$. The stuff flowing from $s_1$ has to go to $t_1$,
the stuff from $s_2$ has to go to $t_2$, and so on. For each sink
$t_i$ we have a {\em demand} $d_i$. (E.g., we need to get $d_1$
trucks from $s_1$ to $t_1$, $d_2$ trucks from $s_2$ to $t_2$, and so
on.) Each directed edge has a capacity indicating the maximum
total amount of traffic that can go on it. Want to know if problem
is feasible.
How to set up as an LP?
What are the variables? for each commodity i and each edge
e we have a variable x_{ei}.
What are the constraints?
- for all i, for all e, x_{ei} >=0.
- for all e, sum_i x_{ie} <= c_e.
- for all i, for all v (except s_i,t_i),
sum_{e in in(v)} x_{ei} = sum_{e in out(v)} x_{ei}
- for all i, sum_{e in in(t_i)} x_{ei} - sum_{e in out(t_i)} x_{ei} >= d_i
in(v) means the set of edges going into v.
out(v) means the set of edges leaving v.