MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming
Homework 1.

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.
  2. Improve the LP relaxation by adding in the subtour elimination constraints
      ∑
      xe ≤ |U | - 1
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.

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

  6. Let x IBn, where IBn := {x IRn : x i = 0 or 1 i}. What, if anything, is implied by the following?
    1. xi + xj 1 and xi xj.
    2. xi xj and xi + 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