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:

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.

- The LP relaxation model and data files are available online. Solve the LP relaxation
of the problem, so each x
_{e}satisfies 0 ≤ x_{e}≤ 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.

- Improve the LP relaxation by adding in the subtour elimination constraints
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.

- 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

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

- 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

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.

- 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 p

_{j}hours to complete. Given job weights w_{j}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(n

^{3}) constraints.- Quadratic assignment problem
Let

Then job i is finished at time t

_{i}, with job i the kth completed job:So total weighted completion time is

The complete formulation is

- Mixed integer linear program
Let t

_{i}be the time at which job i is finished.Let

We need

Let T = ∑

_{i=1}^{n}p_{ i}, the time the last job finishes. We then have the formulation - Linear ordering formulation
Let

Then the time to finish job j is

This gives the formulation

Note that the triangle constraints x

_{ij}+ x_{jk}+ x_{ki}≤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:

- Reorder jobs so that
- 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.

- Quadratic assignment problem
- Let x ∈ IB
^{n}, where IB^{n}:= {x ∈ IR^{n}: x_{ i}= 0 or 1∀i}. What, if anything, is implied by the following?- x
_{i}+ x_{j}≥ 1 and x_{i}≤ x_{j}. - x
_{i}≤ x_{j}and x_{i}+ x_{j}+ x_{k}≤ 1.

Solution:

- Note that if x
_{j}= 0 then we must have x_{i}= 0 from the second constraint, which violates the first constraint. So we must have x_{j}= 1. Note that either choice of x_{i}is feasible with x_{j}= 1. - Note that if x
_{i}= 1 then x_{j}= 1 from the first constraint, but we then violate the second constraint. So we must have x_{i}= 0. The second constraint then becomes x_{j}+ x_{k}≤ 1.

- x

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 |