: THE TRAVELING SALESMAN ASSIGNMENT INSTRUCTIONS

OVERVIEW

Half of the Modules include projects that are the only part of the course outside of WebAssign.

The project assignments are designed to explore important areas within the field of Management

Science$/$Operations Research that lend themselves more naturally to a more extended exercise

than to weekly homework assignments.

Each project assignment uses Excel to work through a prominent optimization strategy. In each

case, this is done within the context of a well$-$known and historically significant problem.

Besides introducing important problems, the projects require you to implement a strategy for

solving them. While each strategy is tailored to the specific problem, it also represents a broadly

applicable and valuable approach $($i$.$e$.$ a meta$-$heuristic$).$ You will do this by using Excel for

computations that would be too cumbersome to do by hand.

INSTRUCTIONS

The most famous problem in Operations Research is probably the Traveling Salesman Problem

$($TSP$).$ We are given several cities and the distances between them, and our goal is to construct

the minimum distance $($or cost$)$ route $($or tour$)$ that begins and ends at the same place and visits

each required city along the way.

Many network problems can be solved by creating linear programming $($LP$)$ formulations. TSP

cannot, but there are LPs that provide helpful relaxations. One formulation that might at first

appear to be sufficient is given below:

Let $,=\{1,$

$0,$

Our LP relaxation is as follows

Min $=$

$=+11$

$=1,,$

s$.$t$.1$

$=1,+$

$=+1,=2$ for all city $$

all $,>=0$

Essentially, the constraint ensures that we must take an arc into each city and out of each city so

that our tour both visits and leaves each city.

The problem with this formulation is what are called subtours. While a solution must consist of

a single tour that connects every city, these constraints allow $$solutions$$ that consist of multiple

separate subtours. For example, if we are given a problem with $13$ cities, our solution might

create one subtour that connects $4$ cities and another that connects the remaining $9.$ Let$$s say

that shorter subtour goes from city $1$ to city $2$ to city $3$ to city $4$ and then returns to city $1,$ making

the arcs involved in this subtour $1,2,2,3,3,4$ and $1,4.$ We can eliminate this particular subtour

and thus improve the LP by adding the constraint $1,2+2,3+3,4+1,4<=3.$ The right$-$hand

side value is one less than the number of arcs in this subtour, so this constraint will eliminate it in

all future LP solutions. Most of the combinatorial number of subtours are impractical, so only a

tiny fraction of these subtours need to be explicitly eliminated by adding constraints.