Homework 5 Network Simplex Algorithm

CS 6890: Linear and Integer Programming
Homework 5

Learning Objectives
1. Network Simplex Algorithm
Problem 1 (10 point)
Implement the following network simplex algorithm discussed in Lecture 10.
1. Given a feasible basis represented by a rooted spanning tree, compute
the flows by starting at the end nodes of the tree and working toward
the root and compute the node potentials by starting at the root node
and working toward the end nodes of the tree.
2. Check for optimality (i.e., zij − cij ≤ 0, for all i, j). If the solution is
optimal, stop. If not, determine the entering arc (i, j).
3. Add the entering arc to the spanning tree and induce the flow around
the formed cycle to determine ∆. If no departing arc can be found,
the problem has no solution. Otherwise, let (p, q) be the departing
arc.
4. Remove the departing arc (p, q) from the tree. Set the flow of the
entering arc (i, j) to ∆ and update the flows of the other arcs around
the cycle. Go to step 2.
We have not finished discussing the flow induction principle. We will do it in
Lecture 11. In the meantime, you can start working on steps 1 and 2. You
1
can package your solution as NetSimplex.java/py. The class NetSimplex
should have a method NetSimplex.doSimplex(G, T), where G is a network
graph and T is a spanning tree of G.
Problem 2 (10 points)
Let G(N, A) be a flow network where N = {1, 2, 3, 4, 5} and A = {(1, 2),(1, 3),
(1, 4),(2, 3),(2, 5),(3, 4),(3, 5),(4, 5),(5, ∞)}. The arc (5, ∞) simply means
that 5 is the root node with the arc from 5 going into space.
Let b(i) be the balance of node i. G(N, A) has the following balances:
1. b(1) = 12;
2. b(2) = 7;
3. b(3) = 3;
4. b(4) = −8;
5. b(5) = −14.
Let cij be the cost of the arc (i, j). The network’s arcs have the following
costs:
• c12 = 2;
• c13 = 3;
• c14 = 4;
• c23 = 4;
• c25 = 3;
• c34 = 1;
• c35 = 5;
• c45 = 6
2
Assume that a starting basic feasible solution is given by the following rooted
spanning tree T(N, A), where N = {1, 2, 3, 4, 5} and A = {(1, 3),(1, 4),(2, 3),
(3, 5),(5, ∞)}. Use your implementation of the network simplex algorithm
to find an optimal flow for this network.
Implement your solution in the method NetSimplex.problem2(G, T) where
G = G(N, A) is the network graph defined above and T = T(N, A). The
output of this method should have the following format (the actual flow
values for this problem are different):
x12 = 10
x14 = 15
x25 = 20
x14 = 78
z = 89
What To Submit
Submit your source as NetSimplex.java/py.
3