MATP6620 / ISYE6760
Combinatorial Optimization and Integer Programming

Homework 6.

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

  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?

  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
                     y      binary

    as the initial relaxation (RMP).)

  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 ) = 2        djk.
          j∈C k∈C

    We define a binary variable

          { 1  if cluster C is chosen in the clustering
xi =                  i
        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        Ci:j∈Ci xi =   1  for j = 1, ...,n
                         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

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

    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.

  5. In the following picture,


    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.
    John Mitchell
    Amos Eaton 325
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.