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

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

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