MATP6640/ISYE6770 Linear Programming, Homework 4.

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 x

_{12}= 1, x_{13}= 0, x_{41}= 1, with nonbasic variables x_{23}= 1,x_{24}= 0,x_{34}= 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 f
_{e}(x) of shipping x units along arc e is a convex nonnegative piecewise linear function with f_{e}(0) = 0. Assume arc e has capacity u_{e}. The supply b_{v}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 loops.) - (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 cycle.)
- 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
follows:
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?

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj |