MATP6640/ISYE6770 Linear Programming, Homework 4.

Due: 11.59pm on Friday, March 4, 2022 on LMS.
10% penalty for each day late.

  1. Solve the primal and dual semidefinite programs:
              [      ]
            1  0                             max         2   2y
minX ∈S2+    0  1   ∙X                            y∈IR,S∈S+
          [      ]                                 [ 1  1 ]             [ 1  0 ]
s.t.         1  1   ∙X   =   2    (SDP )      s.t.  y  1  0     +  S   =    0  1      (SDD  )
            1  0
                    X   ≽   0                                    S   ≽  0

    What are the optimal solutions X and y, S? What are the optimal values?

  2. Use the network simplex algorithm to find the minimum cost flow for the problem with the following linear programming representation:
    min               -  2x13  -   x23 -   2x24          -   10x41
subject to  - x12  -   x13                            +     x41  =  0
             x12           -   x23 -    x24                     =  0
                      x13  +   x23           -  x34             =  0
                                        x    +  x    -     x    =  0
                                         24       34         41
                                        0 ≤ x12,x13,x23,x24,x34 ≤  1
                                                  0  ≤     x41  ≤  10

    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.

  3. (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 Gshould also be simple. A directed graph is simple if it has no parallel arcs or loops.)
  4. (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.)
  5. 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:
              |
-edge-----|(1,2)--(1,5)--(2,3)--(2,4)--(2,5)-(3,4)--(4,5)-
 cost     |   8     11     7     10     6      6     8
 capacity |  25     40    35     50    40     25    50

    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