Principles of Mathematics in Operations Research

Web material

Fig. 8.3. Starting bfs solution for our multi-commodity flow instance

b) Let Vk be the set of paths from source node sk to sink node tk for commod-
ity k. For P e V, let fp: flow on path P (decision variable),
r. , 1, if a is in P
lap =

= 1}

0, otherwise
Ckp: unit cost of flow = ^a Iapcka
Dk- demand for the circulation
fip: upper bound on flow = min {uka '•
Give the Path-Cycle formulation, relate to the Node-Arc formulation, and dis-
cuss the size.
c) Take the path cycle formulation. Let wa be the dual variable of the capac-
ity constraint and TTk the dual variable of the demand constraint. What will
be the reduced cost of path PI What will the reduced cost of path P at the
optimality? Write down a subproblem (column generation) that seeks a path
with lower cost to displace the current flow. Discuss the properties.
d) Solve the example instance using column generation starting from the so-
lution given in Figure 8.3. Let us fix all capacities at 10 and all positive
supplies/demands at 10 with unit carrying costs.
e) Sketch briefly the row generation, which is equivalent to the Dantzig-
Wolfe/Bender's decompositions' viewpoint.

Web material

http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new04.pdf

http://archives.math.utk.edu/topics/linearProg.html

http://catt.bus.okstate.edu/itorms/volumes/voll/papers/murphy/

http://cepa.newschool.edu/het/es says/math/convex.htm#minkowski

http://cgm.cs.mcgill.ca/~beezer/Publications/avis-kaluzny.pdf

http://cis.poly.edu/rvslyke/simplex.pdf

http://citeseer.ist.psu.edu/62898.html