MATP6640/ISYE6770 Linear Programming, Homework 4.
Solutions

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 ]
            1  1                             s.t.  y           +  S   =              (SDD  )
s.t.         1  0   ∙X   =   2    (SDP )              1  0                 0  1
                    X   ≽   0                                    S   ≽  0

    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

    minX11,X12,X22     X11 + X22
subject to        X11 + 2X12  =   2
               X11X22 - X212 ≥   0
                    X  ,X    ≥   0
                     11   22

    The equality constraint implies X12 = 12(2 - X11), Making this substitution gives the equivalent problem

    minX11,X22      X11 + X222
subject to  X22 - (2-4XX11)-  ≥  0
                 X11, 11X22  ≥  0

    At optimality, we must have X22 = (2- X  )2
--4X1111-, so we get the equivalent single variables problem

                               (2-X  )2
minX11     f(X11) := X11 +  -4X1111--
subject to        0 ≤ X11 ≤ 2

    We have

     df     5    1
dX---=  4-- --2-
   11       X 11

    and the function is strictly convex for 0 < X11. Thus the optimal primal solution is to take X11 = √2-
 5, with

             [         √ --   ]
X * = √1-  √ -2      5-√1-
       5     5- 1  3 -  5

    with value zP * = √--
 5 - 1.

    The dual slack matrix is

        [ 1 - y  - y ]
S =    - y    1

    so we require

    y ≤ 1,  1- y ≥ y2.

    The roots of the quadratic q(y) = y2 + y - 1 are

           1   √5--
y =  - -- ---
       2    2

    so the largest feasible value of y is

         √ --
y* = --5--1-
        2

    and so the optimal dual value is zD* = √--
 5 - 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 IR2×2.

  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
                      x    +   x             -  x               =  0
                        13       23                34
                                        x24  +  x34  -     x41  =  0
                                        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.

    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

    yj - yi + zij - wij = cij ∀ (i,j) ∈ E.

    Complementary slackness requires:

    ∙xij basic: zij = wij = 0
∙xij = 0, nonbasic: wij = 0
∙xij = uij, nonbasic: zij = 0

    Dual feasibility also requires wij,zij 0(i,j) E.

    Calculate dual variables from complementary slackness on basic edges. Take y1 = 0, solve yj - yi = cij for basic edges.

    We need yj - yi + zij - wij = cij for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:

    (2,3) : xij = uij so zij = 0 : w23 = - c23 + y3 - y2 = 1 - 2- 0 = - 1
(2,4) : xij = 0 so wij = 0 : z24 = c24 - y4 + y2 = - 2- 10 + 0 = - 12
(3,4) : xij = uij so zij = 0 : w34 = - c34 + y4 - y3 = 0 - 10- 2 = 12

    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 y1 = 0, solve yj - yi = cij for basic edges.

    We need yj - yi + zij - wij = cij for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:

    (1,2) : xij = uij so zij = 0 : w12 = - c12 + y2 - y1 = 0 + 12+ 0 = 12
(2,3) : xij = uij so zij = 0 : w23 = - c23 + y3 - y2 = 1 - 2- 12 = - 13
(3,4) : xij = uij so zij = 0 : w34 = - c34 + y4 - y3 = 0 + 10+ 2 = 12

    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 y1 = 0, solve yj - yi = cij for basic edges.

    We need yj - yi + zij - wij = cij for each edge (i,j) for dual feasibility. Calculate z,w values for nonbasic edges:

    (1,2) : x  = u   so z  = 0 : w  = - c  + y - y  = 0 + 12+ 0 = 12
         ij    ij    ij       12      12    2   1
(2,3) : xij = 0 so wij = 0 : z23 = c23 - y3 + y2 = - 1+ 2 + 12 = 13
(3,4) : xij = uij so zij = 0 : w34 = - c34 + y4 - y3 = 0 + 10+ 2 = 12

    Since wij,zij 0(i,j) E, we are optimal. Optimal value is cT x = -24 = -uT w.

  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.)

    Solution:

    It is given that the cost of pushing xij units of flow along arc (i,j) is given by a piecewise linear function of the form

              (   1                                     1
          |||  cijxij                      if 0 ≤ xij ≤ aij
          |||{  c2ij(xij - a1ij)+ fij(a1ij)     if a1ij ≤ xij ≤ a2ij
             c3ij(xij - a2ij)+ fij(a2ij)     if a2ij ≤ xij ≤ a3ij
fij(xij) = ||      ..                          ..
          ||||      .                          .
          (  ckijij+1(xij - akiijj ) + fij(akijij) if akijij ≤ xij ≤ uij

    where the function consists of kij + 1 line segments and where cij1 < cij2 < < cijkij+1. We can represent the problem as a problem with linear costs by introducing an extra 2kij edges and kij vertices for each original edge. Edge (i,j) is replaced by the complex below:

  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.)

    Solution:

    Assume xv0v1 is fractional. Since all the capacities and demands are integral, there must be another edge (v1,v2) with xv1v2 fractional. Since bv2 is integral, can find another (v2,v3) with xv2v3 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 xe 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.

  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?

    Solution:

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

    f123 : 15, f1543 : 25, f523 : 13, f451 : 19.

    The LP is

    minf       15f123  +   25f1543  +   13f523  +   19f451
subject to    f123  +     f1543                        =   25
                                    f523             =   20
                                               f451  =   20
             f123                                    ≤   25
                        f                +     f    ≤   40
                         1543                    451
             f123              +     f523             ≤   35
                                                 0  ≤   50
                                    f523             ≤   40
                        f1543                        ≤   25
                        f1543             +     f451  ≤   50
                                                 f  ≥   0

    Optimal solution is

    f123 = 15,f1543 = 10,f523 = 20,f451 = 20, total cost 1115.

    Dual problem is

    msauxbyje,πct to 25σσA  +20σB   +20σC  - 25-ww1122  -40w15 - 35-ww2233  -50w24  -40w25  -25w34  -50w45 ≤   15
           σAA                        - w15                         -w34    -w45 ≤   25
                 σB                          -w23           -w25                ≤   13
                        σC           - w15                                 -w45 ≤   19
                      y free,                                                   π ≥   0

    From complementary slackness, dual solution is

    σA = 25,  σB = 23,  σC  = 19

    with

    w12 = w15 = w24 = w25 = w34 = w45 = 0,  w23 = 10.

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

    Shortest paths with the modified costs:

    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 c45 + c34 = 14. The updated primal LP is

    minf       15f123  +  25f1543  +  13f523  +  14f543  +  19f451
subject to   f123  +    f1543                                   =  25
                                    f523  +    f543             =  20
                                                          f451  =  20
             f123                                               ≤  25
                        f                            +    f     ≤  40
                         1543                              451
             f123              +    f523                        ≤  35
                                                             0  ≤  50
                                    f523                        ≤  40
                        f1543             +    f543             ≤  25
                        f1543             +    f543  +    f451  ≤  50
                                                             f  ≥  0

    Optimal solution is

    f123 = 25,f1543 = 0,f523 = 10,f543 = 10,f451 = 20, total cost 1025.

    Updated dual problem is

    msauxbyje,πct to 25σσA  +20σB   +20σC  - 25-ww12  -40w15 - 35-ww23  -50w24  -40w25  -25w34  -50w45 ≤   15
           σAA                   12   - w15     23                  -w34    -w45 ≤   25
                 σB                          -w23           -w25                ≤   13
                 σB                                                -w34    -w45 ≤   14
                      y σfrCee,          - w15                                 -w45π ≤≥   190

    From complementary slackness, one dual solution is

    σA = 17,  σB = 14,  σC  = 19

    with

    w12 = 1,  w15 = w24 = w25 = w34 = w45 = 0,  w23 = 1.

    (There are multiple dual optimal solutions, with 25 σA = 16 + w12, w12 0.)

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

    Shortest paths with the modified costs:

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

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj