Transcript Notes (part 1)

Minimum Cost Flows
The Minimum Cost Flow Problem
uij = capacity of arc (i,j).
cij = unit cost of shipping flow from node i to
node j on (i,j).
xij = amount shipped on arc (i,j)
(i,j)A cijxij
Minimize
j xij
-
k xki = bi
for all i  N.
and 0  xij  uij for all (i,j)  A.
2
Find the shortest path from node 1 to node 6
0
2
0
4
4
2
2
1
b(1) = 1 1
2
3
4
6 b(6) = -1
2
3
0
3
5
0
The optimal flow is to send one unit of flow along
1-2-5-6.
This transformation works so long as there are no
negative cost cycles in G.
(What if there are negative cost cycles?)
3
Find the Maximum Flow from s to t
1
10, 8
1,1
s
6, 5
2
b(i) = 0 for all i;
8,7
t
10,6
add arc (t,s) with a
cost of -1 and
large capacity.
The cost of every
other arc is 0.
13
The optimal solution in the corresponding minimum
cost flow problem will send as much flow in (t,s) as
possible.
4
Transshipment Problems
Plants with given production capabilities for a
product.
One can ship directly from the plants to retailers, or
from plants to warehouses, and then from
warehouses to retailers.
There is a given demand for each retailer.
Costs of shipment are given.
What is the minimum cost method for satisfying
demands?
5
A Network Representation
4
Demands
190 1
6
400
7
180
310 2
Retailers
100
3
5
Plants
Warehouses
6
The Caterer Problem
Demand for di napkins on day i for i = 1 to 7 (so, j  [1..7]).
Cost of new napkins: a cents each,
2-day laundry: b cents per napkin
1-day laundry: c cents per napkin.
Minimize the cost of meeting demand.
0
a
clean
demand
arcs
dirty
2
1
c
1’
3
4
5
6
7
3’
4’
5’
6’
7’
b
2’
7
Purchase arcs
In any period of the seven periods, one can purchase
napkins, at a cost of a cents per napkin.
clean napkins
0
a
1
2
3
4
5
6
7
8
Demand Arcs
You must use di napkins on day i
dirty napkins
0
a
lower
bound on
flows
2
1
d1
1’
4
3
d2
2’
d3
3’
5
d4
4’
6
d5
5’
7
d6
6’
d7
7’
9
The rest of the arcs
You may launder napkins in 2 days at b cents each
You may launder napkins in 1 day at c cents each
You may store clean napkins for free
You may store dirty napkins for free
Application to
airplane
maintenance.
0
a
2
1
c
1’
3
4
5
6
7
3’
4’
5’
6’
7’
b
2’
10
Some Assumptions
1. All data is integral. (Needed for some proofs,
and some running time analysis).
2. The network is directed.
3.
i=1 to n b(i) = 0.
(Otherwise, there cannot be a feasible solution)
4. There is a feasible solution (see next slide)
11
Artificial Solutions
To create a feasible
solution, add a
dummy node d.
Add an arc from d
to each demand
node, each with a
large cost M, and
large capacity.
3
2
-4
4
1
1
3
6
3
5
2
-5
d
Add an arc to d from each supply node, each with a
large cost M, and a large capacity.
In an optimal solution, arcs with large cost will have
a flow of 0.
12
Overview of the solution procedure
Reduced costs
 recall replacing cij – i + j for the shortest path
problem. The same transformation is very useful
for min cost flow algorithms.
Optimality conditions
 Most iterative optimization algorithms stop when
“optimality conditions are satisfied”. We
describe optimality conditions for the min cost
flow problem.
13
Reduced Costs
Let i denote the node potential (or dual price) for node i.
cij  cij   i   j
For unit of flow out of node i, subtract i from the cost
For unit of flow into node j, add j to the cost.
$3
1
2
$1
-$5
3
1
$3 – 1 + 2
2
$1 – 2 + 3
-$5 – 3 + 1
3
14
More on Using Reduced Costs
Claim: For any feasible solution x, cx - cx = b.
Thus a feasible flow x that minimizes cx will also
minimize cx.
Proof:
cx  c x   ( i , j )A ( i   j ) xij
  i  i ( j xij   j x ji )
  i  i bi   b
15
Optimality Conditions
Let x be a flow and let  be a vector of node
potentials.
The pair (x, ) is optimal if it satisfies the following:
1.
x is a feasible flow
cij
2.
If
> 0, then xij = 0
3.
If cij < 0, then xij = uij
1
3
$3
-$5
2
4
If x,  satisfy (1) – (3), we say that x is an optimal
flow, and  is an optimal set of node potentials.
16
Calculating A Spanning Tree Flow
1 1
-6 2
1
2
4
3
7
3
A tree with
supplies and
demands.
(Assume that all
other arcs have a
flow of 0)
6 -4
5 3
What is the flow
in arc (4,3)?
See the animation.
17
What would happen if the flows in nontree arcs were not 0?
1 1
-6 2
7 3
3
1
3
Suppose that nontree arcs had a nonzero flow. How
would this change
the computations?
6
-4
2
1
4
5
2
3
18
What would happen if the flows in nontree arcs were not 0?
1 1
Adjust the
supplies/demands.
-6 2
3
1
3
6
-4 2
2
0
1
4
5
2
3
4
7 3
6
They will be
interpreted as
excesses and
deficits.
The compute flows
as in the previous
method; e.g., what is
the flow in (4,3)?
19
What would happen if the flow were
negative?
If the direction of (4,3)
were reversed, the flow
in (3,4) would be
negative.
1 1
4
3
-6 2
6
1
-2
2
4
7
4
3
6 -4
3
5 3
3
A spanning tree flow is
guaranteed to satisfy the
supply/demand
constraints. It may
violate an upper or lower
bound.
A spanning tree flow is
called feasible if it
satisfies its upper and
lower bound. Otherwise,
it is infeasible.
20
Basic Flows
A basis structure consists of a spanning tree T, a set L of arcs,
and a set U of arcs, such that T  L  U = A.
For each (i,j) L, xij = 0.
For each (i,j)  U, xij = uij.
The arc flows in T are selected so that each node satisfies its
supply/demand constraint.
The basis structure is feasible if the arc flows also satisfy the
upper and lower bounds.
It is possible for a basis structure to be infeasible. In fact, this
is normally the case in the dual simplex algorithm.
21
Another way of calculating flows in arcs
Case 1. If (i,j) is not in the tree, then xij = 0.
1 1
-6 2
1
2
4
3
7 3
6 -4
The total supply in
subset S = (3,4,5) of
nodes is 6. How can
one satisfy the
supply/demand
constraints for S?
5 3
22
Another way of calculating flows in arcs
1 1
-6 2
1
2
4
3
6 -4
5 3
7
Deleting an arc (i,j) of
T splits the nodes
into two subsets, S
and N-S.
3
To compute the flow
in (i,j), compute jS
b(j).
23
Another way of calculating flows in
arcs, general case
Case 2. If (i,j) is not in the tree, then xij = 0 or uij
1 1
2
Deleting an arc (i,j) of
T splits the nodes
into two subsets, S
-6 2
7
and N-S.
3 Let f(S, N-S) denote the
3
flow across the cutset (S,
1 3
6 -4
N-S) from the non-tree
arcs.
1
To compute the flow
4
5 3
in (i,j), compute
2
jS b(j)
-
f(S, N-S).
24
Calculating Simplex Multipliers for a
Spanning Tree
To calculate node
potentials,
0
1
5
-6
2
3
-2
4
7
-4
3
1. Let i = 0;
6
2. Choose other
multipliers so that for
each arc (i,j) in the tree
cij - i + j = 0.
1
5
See the animation.
What is the node
potential for node
2?
25
An alternative approach for calculating
simplex multipliers
0
1
5
-6
2
-4
3
3
-2
4
7
6
1
5
Let i be the cost
of the path from
node i to node 1
(the root node) in T.
If (j,k) is backward,
then use cost -cjk.
What is the
simplex multiplier
for node 4?
What is the
simplex multiplier
for node 6?
26
Optimality Conditions (again)
Optimality Conditions for Spanning Tree Solutions:
The following are conditions under which x is an
optimal solution for the minimum cost flow
problem and  is optimal for the dual problem:
1.
The basic flow x is feasible
1
2.
 is the vector of simplex multipliers.
0
3.
For each non-tree arc (i,j)
2
0
a. if cij > 0, then xij = 0
0
3
6
b. if cij < 0, then xij = uij
What is the flow on arc
(5,6) if arc (5,6) satisfies
the optimality conditions?
0
0
4
5
0
7
-4
27
Violating Arcs
(T, L, U) :
x:
p:
cij
a spanning tree structure.
basic feasible flow
simplex multipliers.
reduced costs
A non-tree arc is a violating arc and eligible for
entering the basis if
i.
ii.
cij < 0 and xij = 0 or
cij > 0 and xij = uij.
28
The Network Simplex Pivot
1. Choose a violating non-tree arc. If no such arc exists, then
the solution x is optimal.
2. Add (i,j) to T creating a unique cycle C. Send a maximum
flow around C while maintaining feasibility. Suppose the
exiting arc is (p,q).
3. Update the multipliers so that the reduced costs of all tree
arcs are 0 after the pivot.
T-(p,q) partitions into two subtrees, T1 and T2 with the root
node in T1.
Let d = |cij|.
If i Î T1, then add |cij| to each node v Î T2.
If i T2, then subtract d from each node in T2.
29
The Steps for the network simplex
1. Select the entering arc.
Key data structure: maintain the simplex multipliers
O(1) step to determine if (i,j) is violating.
2. Determine the basic cycle C. Determine the flow around
the basic cycle. Send the flow.
3. Determine the subtree T2 obtained upon deleting the
exiting arc from the current spanning tree. Update all
multipliers in T2.
Fact: Lots of computational work was done in trying to figure
out how to do steps 2 and 3 efficiently. For many choices
of data structures, the running time to be proportional to
|C| + |T2|, and the major concern is the "proportion" or the
"constant term."
30
Some Remaining Issues
How can we avoid cycling in the simplex method?
(Or what do we do if the amount of flow sent
around a cycle is 0).
What is the worst case performance of the simplex
method?
What are some good heuristics to speed up
performance in practice?
31
Summary
1. Network simplex is extremely fast in practice.
2. Relying on network data structures, rather than matrix
algebra, causes the speedups. It leads to simple rules for
selecting the entering and exiting variables.
3. Running time per pivot :
(i) arcs scanned to identify an entering arc
(ii) arcs scanned of the basic cycle
(iii) nodes of the subtree
4. A good pivot rule can dramatically reduce running time in
practice.
32