Due: 11.59pm on Friday, March 4, 2022 on LMS.
10% penalty for each day late.
- Solve the primal and dual semidefinite programs:
What are the optimal solutions X and y, S? What are the optimal values?
- Use the network simplex algorithm to find the minimum cost flow for the problem with the following
linear programming representation:
Use the initial basic feasible solution with basic variables x12 = 1, x13 = 0, x41 = 1, with nonbasic
variables x23 = 1,x24 = 0,x34 = 1. You should need two iterations.
- (Bertsimas and Tsitsiklis 7.4) Assume we have a network flow problem on a simple graph G = (V,E)
where the cost fe(x) of shipping x units along arc e is a convex nonnegative piecewise linear
function with fe(0) = 0. Assume arc e has capacity ue. The supply bv at each node v is given and
the aim is to construct a minimum cost circulation. Show that we can construct an
equivalent problem on a modified graph G′ = (V ′,E′) where all the arc costs are linear. (The
graph G′ should also be simple. A directed graph is simple if it has no parallel arcs or
- (Bertsimas and Tsitsiklis 7.13) Suppose we are given a noninteger optimal solution to an
uncapacitated network flow problem with integer data. Show that there exists a cycle with every arc
on the cycle carrying a positive flow. What can you say about the cost of such a cycle? How
could you exploit the cycles to construct an optimal integral solution? (Note: Some arcs
may be oriented in the opposite direction from the cycle. The cost of the cycle is the
difference between the sum of the costs of the arcs oriented in the same direction as the
cycle and the sum of the costs of the arcs oriented in the opposite direction from the
- Consider a multicommodity network flow problem with three commodities on a graph G = (V,E)
with five nodes and seven edges. The seven edges and their costs and capacities are as
The costs are identical for each commodity. 25 units of commodity A need to be moved from node 1
to node 3. 20 units of commodity B need to be moved from node 5 to node 3. 20 units of
commodity C need to be moved from node 4 to node 1. The current set of paths consists of
1 → 2 → 3 and 1 → 5 → 4 → 3 for commodity A, 5 → 2 → 3 for commodity B, and 4 → 5 → 1 for
commodity C. Use the path based approach described in class to show that this is not an optimal
set of paths. What is the optimal solution?