MATP6640/ISYE6770 Linear Programming, Homework 4.

Solutions

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?

Solution:

We can rewrite the primal problem as the nonlinear program

The equality constraint implies X

_{12}= (2 - X_{11}), Making this substitution gives the equivalent problemAt optimality, we must have X

_{22}= , so we get the equivalent single variables problemWe have

and the function is strictly convex for 0 < X

_{11}. Thus the optimal primal solution is to take X_{11}= , withwith value z

_{P }^{*}= - 1.The dual slack matrix is

so we require

The roots of the quadratic q(y) = y

^{2}+ y - 1 areso the largest feasible value of y is

and so the optimal dual value is z

_{D}^{*}= - 1.Note that the primal and dual optimal values agree.

As a check, you can calculate the product of the optimal X

^{*}and dual slack matrix S^{*}and confirm that X^{*}S^{*}= 0 ∈ IR^{2×2}. - 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.Solution:

The initial solution is

Note that as presented in the question, the signs in the adjacency matrix are reversed from those in the notes. We have dual constraints

Complementary slackness requires:

Dual feasibility also requires w

_{ij},z_{ij}≥ 0∀(i,j) ∈ E.Calculate dual variables from complementary slackness on basic edges. Take y

_{1}= 0, solve y_{j}- y_{i}= c_{ij}for basic edges.We need y

_{j}- y_{i}+ z_{ij}- w_{ij}= c_{ij}for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:So arc (2,4) is a candidate to enter the basis. Flow is adjusted around the cycle 1 - 2 - 4 - 1.

We have to take ϵ = 0 and arc (1,2) leaves the basis. The updated solution is:

Calculate dual variables from complementary slackness on basic edges. Take y

_{1}= 0, solve y_{j}- y_{i}= c_{ij}for basic edges.We need y

_{j}- y_{i}+ z_{ij}- w_{ij}= c_{ij}for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:So arc (2,3) is a candidate to enter the basis. Flow is adjusted around the cycle 1 - 3 - 2 - 4 - 1.

We have to take ϵ = 1 and arc (2,3) moves from being nonbasic at its upper bound to being nonbasic at its lower bound. The updated solution is:

Calculate dual variables from complementary slackness on basic edges. Take y

_{1}= 0, solve y_{j}- y_{i}= c_{ij}for basic edges.We need y

_{j}- y_{i}+ z_{ij}- w_{ij}= c_{ij}for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:Since w

_{ij},z_{ij}≥ 0∀(i,j) ∈ E, we are optimal. Optimal value is c^{T }x = -24 = -u^{T }w. - (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.)Solution:

It is given that the cost of pushing x

_{ij}units of flow along arc (i,j) is given by a piecewise linear function of the formwhere the function consists of k

_{ij}+ 1 line segments and where c_{ij}^{1}< c_{ij}^{2}< … < c_{ij}^{kij+1}. We can represent the problem as a problem with linear costs by introducing an extra 2k_{ij}edges and k_{ij}vertices for each original edge. Edge (i,j) is replaced by the complex below: - (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.)
Solution:

Assume x

_{v0v1}is fractional. Since all the capacities and demands are integral, there must be another edge (v_{1},v_{2}) with x_{v1v2}fractional. Since b_{v2}is integral, can find another (v_{2},v_{3}) with x_{v2v3}fractional. By continuing this process, a vertex will eventually be repeated, giving a cycle, with every edge on the cycle having fractional flow.Flow can be increased or decreased around this cycle, while still maintaining feasibility. Since the current flow is optimal, the cost of the cycle must be zero. Decreasing the flow around the cycle will drive at least one x

_{e}value to an integral value, while only modifying fractional values.If the resulting flow is still fractional, we can repeat this process, eventually obtaining an integral optimal flow.

- 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?

Solution:

Need to set up linear programming formulation, so need to calculate costs of the paths:

The LP is

Optimal solution is

Dual problem is

From complementary slackness, dual solution is

with

The subproblems require solving shortest path problems for each commodity, with costs

Shortest paths with the modified costs:

- Commodity A: 1 - 2 - 4 - 3, cost 24 < σ
_{A}= 25. - Commodity B: 5 - 4 - 3, cost 14 < σ
_{B}= 23. - Commodity B: 4 - 2 - 1, cost 18 < σ
_{C}= 19.

All three paths have negative reduced cost. Add the one with the most negative reduced cost, namely path 5 - 4 - 3 for Commodity B. The cost of this path is c

_{45}+ c_{34}= 14. The updated primal LP isOptimal solution is

Updated dual problem is

From complementary slackness, one dual solution is

with

(There are multiple dual optimal solutions, with 25 ≥ σ

_{A}= 16 + w_{12}, w_{12}≥ 0.)The subproblems require solving shortest path problems for each commodity, with costs

Shortest paths with the modified costs:

- Commodity A: 1 - 2 - 3, cost 17 = σ
_{A}. - Commodity B: 5 - 4 - 3, cost 14 = σ
_{B}. - Commodity B: 4 - 2 - 1, cost 19 = σ
_{C}.

Thus, no path has negative reduced cost, so we are dual feasible in the full problem, so we are optimal.

- Commodity A: 1 - 2 - 4 - 3, cost 24 < σ

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

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