MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming
Homework 1.
Solutions

Due: Thursday, February 4, 2021, by end of day.
Penalty for late homeworks: 10% for each day or part of a day.

This homework is concerned with a symmetric traveling salesman problem on eleven vertices (indexed from 0 to 10), with the costs given in the following table:

   |
---|-0---1---2---3---4--5---6---7---8---9--10--
  0| 0  63  64  62  35 64  61  60  92  93  63
  1|63   0  62  65  62 63  63  60  13  92  91
  2|64  62   0  63  64 61  62  60  93  15  92
  3|62  65  63   0  63 64  62  60  96  93  14
  4|35  62  64  63   0  2   3  64  93  95  93
  5|64  63  61  64   2  0   3  62  94  93  92
  6|61  63  62  62   3  3   0  43  95  95  91
  7|60  60  60  60  64 62  43   0  94  93  93
  8|92  13  93  96  93 94  95  94   0  62  62
  9|93  92  15  93  95 93  95  93  62   0  63
 10 63  91  92  14  93 92  91  93  62  63  0

You will solve this problem using AMPL and CPLEX. The packages are available on LMS and Box. More on these packages can be found at http://www.rpi.edu/~mitchj/ampldetails.html and also on LMS and in Box.

  1. The LP relaxation model and data files are available online. Solve the LP relaxation of the problem, so each xe satisfies 0 xe 1. Show that this does not give an optimal solution to the TSP.

    Solution:

    Optimal solution to the relaxation is fractional, so it clearly is not a solution to the TSP, which has binary variables.

    PIC

  2. Improve the LP relaxation by adding in the subtour elimination constraints
     ∑    x  ≤ |U | - 1
       e
e∈E(U)

    for all subsets U V of cardinality 3 or 4, where E(U) is the set of edges with both endpoints in U. Show that this still does not give an optimal solution to the TSP.

    Solution:

    We add the subtour constraints to the model using the lines

    subject to subtour3 {i in 0..p, j in i+1..p, k in j+1..p}:  
      x[i,j] + x[i,k] + x[j,k] <= 2;  
     
    subject to subtour4 {i in 0..p, j in i+1..p, k in j+1..p, l in k+1..p}:  
      x[i,j] + x[i,k] + x[j,k] + x[i,l] + x[j,l] + x[k,l] <= 3;

    Optimal solution to the relaxation is still fractional, so it clearly is not a solution to the TSP, which has binary variables.

    PIC

  3. Now require that the solution be binary, in addition to satisfying just the degree constraints. Show that this does not give an optimal solution to the TSP. (Note: The default solver in AMPL is minos, which is a continuous solver. To solve an integer program you have to tell AMPL to use an appropriate solver such as CPLEX or gurobi, using the command option solver cplex;)

    Solution:

    AMPL output is

    PIC

    This is binary, but not a tour. The solution consists of 3 subtours:

    0 - 7 - 3 - 10 - 0,  1 - 2 - 9 - 8 - 1,  4 - 5 - 6 - 4.

  4. Show that an optimal solution to the TSP can be found by adding two particular subtour elimination constraints to the formulation in Question 3, one with |U| = 3 and one with |U| = 4.

    Solution:

    We add subtour elimination constraints for U = {4, 5, 6} and U = {1, 2, 8, 9} using the lines

    subject to subtour4564:  
      x[4,5] + x[4,6] + x[5,6] <= 2;  
     
    subject to subtour12981:  
      x[1,2] + x[1,8] + x[1,9] + x[2,8] + x[2,9] + x[8,9] <= 3;

    The solution is then

    PIC

    The solution to the relaxation is a tour, so it solves the TSP. Optimal solution is the tour 0 - 4 - 5 - 6 - 7 - 1 - 8 - 9 - 2 - 3 - 10 - 0 with length 373.

  5. Model the following scheduling problem as a mixed integer programming problem:

    A set of n jobs must be carried out on a single machine that can only do one job at a time. Each job j takes pj hours to complete. Given job weights wj for j = 1,,n, in what order should the jobs be carried out in order to minimize the weighted sum of their completion times?

    Solution:

    We give 3 different formulations. The first one is quadratic, the second one involves both binary and continuous variables, and the third one requires O(n3) constraints.

    1. Quadratic assignment problem

      Let

            {
x  =     1  if job i is the kth job completed
 ik      0  otherwise

      Then job i is finished at time ti, with job i the kth completed job:

      t  =   p +  ∑n        ∑k - 1p x
 i      i      j = 1    l=1  j jl
               j ⁄= i

      So total weighted completion time is

                  (            (                  ) )

     ∑ n    ||      ∑n    ||   ∑n    k∑- 1     || ||
T  =     wi || pi +    xik||             pjxjl|| ||
      i=1    |      k=1   |          l=1      | |
            (            (  j = 1           ) )
                             j ⁄= i

      The complete formulation is

            ∑n           ∑n   ∑n         ∑n         ∑k -1
min     i=1wipi +    i=1   k=1 wixik    j = 1    l=1 pjxjl
                                       j ⁄= i
      ∑n
s.t.  ∑ i=1xik = 1   for k = 1,...,n
        nk=1 xik = 1  for i = 1,...,n

      xikbinary for i,k = 1,...,n

    2. Mixed integer linear program

      Let ti be the time at which job i is finished.

      Let

            {
x  =     1  if job i is scheduled before job j
 ij      0  otherwise

      We need

      {  t ≥ t +  p  if x  = 0
    i   j    i     ij
   ti ≥ pi     otherwise

      Let T = i=1np i, the time the last job finishes. We then have the formulation

      min     ∑n   w t
    x,t    i=1  ii
s.t.     ti ≥ pi + tj - T xij,  i = 1, ...,n
        ti ≥ pi,  i = 1,...,n
        xij + xji = 1, i,j = 1,...,n,i ⁄= j
        xijbinary for i,j = 1,...,n,i ⁄= j

    3. Linear ordering formulation

      Let

            {
x  =     1  if job i is scheduled before job j
 ij      0  otherwise

      Then the time to finish job j is

                  ∑n
tj = pj +        pixij

           i = 1
           i ⁄= j

      This gives the formulation

                     (               )

      ∑n       | ∑n            |
minx     j=1wj |(    i = 1  pixij|)
                    i ⁄= j

s.t.   xij + xji = 1    i,j = 1,...,n,i ⁄= j
      xij + xjk + xki ≤ 2    i,j,k = 1,...,n,i ⁄= j,i ⁄= k,j ⁄= k
      x   binary

      Note that the triangle constraints xij + xjk + xki 2 are necessary to prevent solutions where i is before j, and j is before k, and k is before i. This formulation is a linear ordering problem.

    Note that the problem can be solved very simply using Smith’s algorithm:

    1. Reorder jobs so that
      w     w        w
--1 ≥ --2 ≥ ...--n
 p1    p2       pn

    2. Perform jobs in the reorder: 1, 2,,n.

    The more complicated formulations come in to play when there are side constraints, for example precedence constraints.

  6. Let x IBn, where IBn := {x IRn : x i = 0 or 1i}. What, if anything, is implied by the following?
    1. xi + xj 1 and xi xj.
    2. xi xj and xi + xj + xk 1.

    Solution:

    1. Note that if xj = 0 then we must have xi = 0 from the second constraint, which violates the first constraint. So we must have xj = 1. Note that either choice of xi is feasible with xj = 1.
    2. Note that if xi = 1 then xj = 1 from the first constraint, but we then violate the second constraint. So we must have xi = 0. The second constraint then becomes xj + xk 1.
    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