15-451 Algorithms 11/02/11
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,..., s_p and p sinks
t_1,..., 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 *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.