MATP6620 / ISYE6760
Combinatorial Optimization and Integer Programming

Homework 6.
Solutions

Due: Thursday, April 29, 2021.
Penalty for late homeworks: 10% for each day or part of a day.

  1. Solve the Held-Karp 1-tree Lagrangian dual problem for the graph with edge costs given below:
       |  1   2   3   4   5   6
---|------------------------
 1 | -   10   9  14   5  14
 2 |10   -   11  10   7  10
 3 |  9  11  -    8   9  14
 4 |14   10   8  -    9  13
   |
 5 |  5   7   9   9  -    8
 6 |14   10  14  13   8  -

    (Hint: The optimal Lagrangian multipliers are integral.)

    Solution:

    We initialize with all Lagrangian multipliers equal to zero, giving a solution:

    Following equation (3.14) on page 484 of the text, we set up the Lagrangian relaxation as

                               (                       )
           ∑               {  ∑                    }
z1T(λ ) = 2    λi +  min           (cij - λi - λj)xij .
           i∈V      x is1-tree( (i,j)∈E                )
    (1)

    We adjust λ according to the degrees of the vertices in the initial 1-tree, leading to the choice

    λ = (0,1, 0,0,- 2,1).

    The modified cost matrix and an optimal 1-tree are then:

       |
---|-1----2---3---4---5---6-
 1 | -    9   9  14   7  13
 2 | 9   -   10   9   8   8
   |
 3 | 9  10   -    8  11  13
 4 |14    9   8  -   11  12
 5 | 7    8  11  11  -    9
 6 |13    8  13  12   9  -

    We adjust λ according to the degrees of the vertices in the current 1-tree, leading to the choice

    λ = (0,0, 0,0,- 2,2).

    The modified cost matrix and an optimal 1-tree are then:

       |
   | 1    2   3   4   5   6
-1-|----10----9--14---7--12-
   |
 2 |10   -   11  10   9   8
 3 | 9  11   -    8  11  12
 4 |14  10    8  -   11  11
 5 | 7    9  11  11  -    8
 6 |12    8  12  11   8  -
   |

    Since this is a tour, it is optimal, with value 50.

  2. The graph G = (V,E) is as follows:

    One unit of commodity A must be shipped from a to k and one unit of commodity B must be shipped from h to f. The flows must be integral. The cost of shipping one unit of flow along an arc is one for each commodity, and the total capacity of each arc is also one. The capacity is the sum of the flow in both directions. A Lagrangian relaxation for the integer multicommodity flow problem could be constructed by placing the upper bound constraints on the arcs in the objective function. If the Lagrangian multipliers are set equal to zero, what is the value of the Lagrangian relaxation? Find a choice of Lagrangian multipliers for which the optimal solution to the Lagrangian relaxation gives the optimal solution to the multicommodity flow problem. How does the optimal value of the Lagrangian relaxation compare to the optimal value of the LP relaxation?

    Solution:

    Let E denote the set of edges and V the set of vertices. Let xeq denote the flow of commodity q on edge e E. We denote the two commodities as q = ak and q = hf. Let s(q) and t(q) denote the start and end vertices for commodity q. Let δ+(v) denote the edges leaving node v, and δ-(v) the set of edges entering node v.

    The Lagrangian relaxation is

                ∑   ∑          ∑       ( ∑         )
minx                  xqe +       λe     xqe - 1
            ∑ q   e∈E   q   ∑e∈E       qq
subject to  ∑ e∈δ+(s(q))xe - ∑ e∈δ-(s(q))xe  =  1  for q = ak,hf
               e∈ δ- (t(q))xqe -    e∈δ+(t(q))xqe  =  1  for q = ak,hf
                ∑         q   ∑         q
                  e∈δ+(v)xe -   e∈δ-(v)xe  =  0  for v ⁄= s(q),t(q),for q = ak,hf
                                       xqe  ≥  0  for e ∈ E, q = ak,hf

    When λe = 0 for all e E, the optimal value of the Lagrangian relaxation is 6, achieved by the path h - j - k - f for commodity hf, and by the path a - b - j - k for commodity ak.

    Both paths use the edge e = (j,k), so try λjk = 1. One optimal solution to the Lagrangian relaxation is then to use the paths a - b - j - k and h - g - p - l - f, with value 7. Since this solution is feasible in the multicommodity problem, it is optimal.

    The constraint matrix for the Lagrangian Relaxation is TU, so the value of the LP relaxation is equal to the value of the Lagrangian Dual. One fractional solution to LP relaxation with value 7: flows of 0.5 along the 4 paths a - b - j - k, a - b - p - l - k, h - j - k - f, h - g - p - l - f. This is the average of 2 optimal integral solutions to the LP relaxation.

  3. Consider the mixed integer programming problem (MIP):
    max   8x1   +9x2  +5x3   +6x4   - 15y1  - 10y2
s.t.   x1           +x3                         ≤   1
       x1                  +x4                  ≤   1
              x     +x                          ≤   1
                2      3
              x2           +x4                  ≤   1
                                   - y1    - y2 ≤   - 1
       x1                          - y1         ≤   0
              x2                   - y1         ≤   0
                     x                     - y  ≤   0
                       3                     2
                            x4             - y2 ≤   0
                                            xj  ≥   0
                                             yi     binary

    Solve this problem using Bender’s decomposition. (Take the problem

    max   z  - 15y1  - 10y2
s.t    z                  ≤  28

                     yi     binary

    as the initial relaxation (RMP).)

    Solution:

    Solution to (RMP) is z = 28, y = (0, 0). Objective function for the subproblem is (b - HT y)T u = bT u since y = 0. Subproblem is:

    minu        u1  +   u2  +   u3  +  u4  -   u5
subject to  u1  +   u2                         +   u6                         ≥   8
                            u   +  u                   +   u                  ≥   9      (SP )
                             3       4                      7
            u1          +   u3                                 +  u8          ≥   5
                    u2          +  u4                                 +   u9  ≥   6
                                                                           u  ≥   0

    Solution is unbounded, with a ray r1 = (0, 0, 0, 0, 1, 0, 0, 0, 0)T . Add constraint (r1)T Hy bT r1 to (RMP):

    max   z  -   15y1  -  10y2
s.t    z                      ≤  28

         -     y1  -     y2  ≤  - 1
                         yi     binary

    Solution is y = (0, 1), z = 28, with value 18. Updated subproblem with objective (b - HT y)T u is:

    minu        u1  +   u2  +   u3  +  u4                      +  u8  +   u9
subject to  u   +   u                      +   u                          ≥   8
             1       2                          6
                            u3  +  u4              +   u7                 ≥   9      (SP )
            u1          +   u3                             +  u8          ≥   5
                    u2          +  u4                             +   u9  ≥   6
                                                                       u  ≥   0

    Optimal value is 11 < z. One solution is u1 = (0, 0, 0, 0, 0, 8, 9, 5, 6)T . Add constraint z + (u1)T Hy bT u1 to (RMP):

    max   z  -   15y1  -  10y2

s.t    z                      ≤  28
         -     y1  -     y2  ≤  - 1
      z  -   17y1  -  11y2   ≤  0
                         yi     binary

    Solution is y = (1, 1), z = 28, with value 3. Updated subproblem with objective (b-HT y)T u is:

    minu        u1  +   u2  +   u3  +  u4  +   u5  +   u6  +  u7   +  u8  +   u9
subject to  u1  +   u2                         +   u6                         ≥   8
                            u3  +  u4                  +  u7                  ≥   9      (SP )
            u           +   u                                  +  u           ≥   5
             1               3                                     8
                    u2          +  u4                                 +   u9  ≥   6
                                                                           u  ≥   0

    Optimal value is 17 < z. One solution is u2 = (8, 0, 0, 9, 0, 0, 0, 0, 0)T . Add constraint z + (u2)T Hy bT u2 to (RMP):

    max   z  -   15y1  -  10y2
s.t    z                      ≤  28
         -     y   -     y   ≤  - 1
                1         2
      z  -   17y1  -  11y2   ≤  0
      z                      ≤  17
                         yi     binary

    Solution is y = (1, 0), z = 17, with value 2. Updated subproblem with objective (b-HT y)T u is:

    minu        u1  +   u2  +   u3  +  u4      +   u6  +   u7
subject to  u1  +   u2                     +   u6                         ≥   8
                            u3  +  u4              +   u7                 ≥   9      (SP )
            u1          +   u3                             +  u8          ≥   5

                    u2          +  u4                             +   u9  ≥   6
                                                                       u  ≥   0

    Optimal value is 17 = z. The point u2 is still optimal to the subproblem. So we have the optimal solution to the master problem, namely y = (1, 0) with z = 17. Fixing this choice of y in the original (MIP) gives the solution x = (8, 9, 0, 0), which is the x portion of the optimal solution. The optimal value is indeed 2.

  4. We are going to consider a column generation approach to solving clustering problems. We have n objects we wish to cluster, with each cluster containing at least 4 objects. Let djk be the cost of clustering object j with object k (the cost djk may be negative). The cost of a cluster C is
            1 ∑   ∑
w(C ) = --       djk.
        2 j∈C k∈C

    We define a binary variable

         {
xi =    1  if cluster Ci is chosen in the clustering
        0  otherwise

    Let C denote the set of all valid clusters. We can then define the clustering problem as

                ∑
minx           Ci∈C w(Ci )xi
subject to      ∑       xi  =   1  for j = 1, ...,n
                  Ci:j∈Ci
                         x      binary

    In the LP relaxation, the binary restriction on x is replaced by the requirement that x 0. The dual to the LP relaxation is

                 ∑n
maxy ∈ℝn    ∑  j=1yj
subject to    j∈Ci yj ≤   w(Ci ) for all Ci ∈ C

    In a column generation approach, we work with a subset of C. Solving the LP relaxation and its dual for this subset gives a vector y of dual multipliers. We have then solved the LP relaxation for the full set C if y is feasible in the full dual problem.

    Construct a quadratic binary program to determine whether y is feasible for the full set C. Reformulate the quadratic binary program as an equivalent integer linear program.

    Solution:

    We have a violated dual constraint if there exists a valid cluster C with

            ∑                                 ∑
w(C ) <     Żyj,  or equivalently   w (C ) -     Żyj < 0.
        j∈C                               j∈C

    Define binary variables

          {
zj =    1  if j ∈ C
        0  otherwise

    We can then set up the quadratic integer program

                1∑     ∑               ∑n
minz∈ℝn    ∑2   j∈C   k∈C djkzjzk -    j=1 Żyjzj
subject to     nj=1zj  ≥   4

                  z      binary

    The solution y is optimal if the optimal value of this IQP is nonnegative.

    We can use the McCormick inequalties to turn this into an equivalent integer linear program. We define the variable ϕjk, which we want to equal the product zjzk. The ILP is then

    min    n    1∑     ∑     d  ϕ   -  ∑n   Ży z
    z∈ℝ     2∑n  j∈C    k∈C  jk  jk      j=1 j j
subject to    j=1zj  ≥   4
                ϕ    ≤   z           for j,k = 1,...,n
                  jk       j
                ϕjk  ≤   zk          for j,k = 1,...,n
                ϕjk  ≥   zj + zk - 1 for j,k = 1,...,n
                z,ϕ      binary

  5. In the following picture,

    PIC

    it is desired to place each of the numbers 1,…,9 into exactly one of the nine empty positions so that the equation is correct. Note that the colon symbol is used to denote division, and the standard arithmetic rules apply so division and multiplication are performed before addition and subtraction.

    1. Formulate the problem as a mixed integer nonlinear feasibility program.
    2. Use the McCormick inequalities to express it as an equivalent mixed integer linear feasibility program, and hence solve it.

    Solution:

    1. We index the nine positions from the start of the snake to the end. We define binary variables
            {
         1  if number  i is placed in position j
xij =    0  otherwise

      We also define binary variables yik = xi2xk3 to represent the division at the end of the first column, and zikl = xi7xk8xl9 to represent the choice for the last three slots. We can then set up the feasibility problem

      Fi∑nd  x, y, z satis∑fying∑           ∑              ∑           ∑
    9i=1 ixi1 + 13  9i=1   9k=1-iyik +    9i=1 ixi4 + 12   9i=1ixi5 -   9i=1ixi6 - 11
              ∑9   ∑9    ∑9k
           +    i=1   k=1   l=1 ikl zikl - 10 = 66
 ∑9
    j=1xij = 1 for i = 1,...,9
 ∑9    xij = 1 for j = 1,...,9
    i=1
 yik = xi2xk3 for i = 1,...,9,k = 1,...,9
 zikl = xi7xk8xl9 for i = 1,...,9,k = 1, ...,9,l = 1, ...,9
 ∑9           ∑9
    i=1 ixi1 ≥   k=1 kxk4 + 1
 ∑9           ∑9
    i=1 ixi7 ≥   k=1 kxk8 + 1
 xij binary  for i = 1,...,9,j = 1,...,9.

      The inequality constraints are for symmetry-busting. Note that the constraints imply each yik and zikl are binary, and that yii = 0i, ziil = zili = zlii = 0i,l.

    2. We can express the problem as the following equivalent mixed integer linear program by using the McCormick inequalities:
      Fi∑nd  x, y, z, w s∑atisfy∑ing        ∑              ∑           ∑
    9i=1 ixi1 + 13  9i=1   9k=1-iyik +    9i=1 ixi4 + 12   9i=1ixi5 -   9i=1ixi6 - 11
              ∑9   ∑9    ∑9k
           +    i=1   k=1   l=1 ikl zikl - 10 = 66
 ∑9
    j=1xij = 1 for i = 1,...,9
 ∑9    xij = 1 for j = 1,...,9
    i=1
 yik ≤ xi2 for i = 1,...,9,k = 1,...,9
 yik ≤ xk3 for i = 1,...,9,k = 1,...,9
 yik ≥ xi2 + xk3 - 1 for i = 1, ...,9,k = 1,...,9

 wik ≤  xi7 for i = 1,...,9, k = 1,...,9
 wik ≤  xk8 for i = 1,...,9,k = 1,...,9
 wik ≥  xi7 + xk8 - 1 for i = 1,...,9,k =  1,...,9
 zikl ≤ wik for i = 1,...,9,k = 1,...,9
 z   ≤  x  for i = 1,...,9,k = 1,...,9
  ikl    l9
 zikl ≥ wik + xl9 - 1 for i = 1,...,9,k = 1, ...,9
 ∑9    ixi1 ≥ ∑9    kxk4 + 1
 ∑9 i=1        ∑9k=1
    i=1 ixi7 ≥   k=1 kxk8 + 1

 xij binary  for i = 1,...,9,j = 1,...,9
 yik binary  for i = 1,...,9,k = 1,...,9
 wik binary  for i = 1,...,9, k = 1,...,9
 zikl binary for i = 1,...,9,k = 1,...,9,l = 1,...,9

      Note we’ve represented zikl = wikxl9 and wik = xi7xk8.

    One solution returned by AMPL is:

    x13 = x25 = x32 = x49 = x56 = x64 = x77 = x88 = x91 = 1.

    Apparently, there are multiple solutions to this problem, see this article.

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.
    webex: https://rensselaer.webex.com/meet/mitchj