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 requiredbYou've been provided with a spreadsheet that allows you to solve this LP relaxation for a $13-$

city TSP$.$ The objective function is in cell D$1,$ and this is a minimization problem. The decision

variables are in cells D$2$ through D$79($in Excel this would be denoted as D$2$:D$79).$ Make sure

you use the Simplex Method and NOT the GRG algorithm to solve the LP$.$

Add constraints in Solver to enforce the requirement that a tour both enters and leaves each city

and that all variables must be integers. You can do this with just two constraints:

Cells G$2$ through G$14$ sum the tour edges connected to each of our $13$ respective cities.

In Solver, choosing to "Add" a constraint brings up an Add Constraint window that allows

you to drag your mouse over all the cells from G$2$ to G$14$ and then set all cells from G$2$:G$14$

equal to $2.$

Similarly, you use the Add Constraint window to constrain all of the variables to be

integers with just one constraint. In the Cell Reference block, drag your mouse over all the

variable cells from D$2-$ D$79($or type D$2$:D$79$ in the box$)$ and choose to make them all

integers. Do not make them binary, as the next question asks you to add inequality

constraints to prevent any variable cell from exceeding $1.$ Once you have added these

constraints, you can use the Solver to find a solution to this LP $($call it LP$1).$ Give the

optimal objective function value of LP$1$: $(12$ points$).$

The first problem you should find is that several arcs equal $2.($This won't happen if you made

all your variables binary, so if you added this constraint, go back and replace it with a constraint

that all variables are integers.$)$ This corresponds to the smallest possible subtour: e$.$g$.$ from

Memphis to Jackson and back again! Identify which arcs are equal to $2$ in the initial LP

relaxation. $(10$ points$)$

Add constraints to your LP to ensure that each of the arcs identified in question two are $1.$

Solve the improved LP relaxation $($LP$2)$ and give the new objective function value. At this

point, you have eliminated the somewhat trivial subtours of LP$1.$ Though your LP$2$ solution

should include more complex subtours, that's a subject for another project. $(8$ points$).$ Cities Objective $0$ City Constraints

Atlanta Atl$-$Balt $0682$ Atlanta $0$

Baltimore Atl$-$Birm $0146$ Baltimore $0$

Birmingham Atl$-$CharWV $0502$ Birmingham $0$

Charleston WV Atl$-$Green $0332$ Charleston WV $0$

Greensboro Atl$-$JackMS $0380$ Greensboro $0$

Jackson MS Atl$-$Jville $0346$ Jackson MS $0$

Jacksonville Atl$-$Mem $0379$ Jacksonville $0$

Memphis Atl$-$Myrtle $0362$ Memphis $0$

Myrtle Beach Atl$-$Nash $0248$ Myrtle Beach $0$

Nashville Atl$-$Norf $0558$ Nashville $0$

Norfolk Atl$-$Phil $0780$ Norfolk $0$

Philadelphia Atl$-$Wash $0637$ Philadelphia $0$

Washington DC Balt$-$Birm $0780$ Washington DC $0$

Balt$-$CharWV $0361$

Balt$-$Green $0355$

Balt$-$JackMS $01017$

Balt$-$Jville $0744$

Balt$-$Mem $0914$

Balt$-$Myrtle $0477$

Balt$-$Nash $0703$

Balt$-$Norf $0248$

Balt$-$Phil $098$

Balt$-$Wash $039$

Birm$-$CharWV $0564$

Birm$-$Green $0478$

Birm$-$JackMS $0237$

Birm$-$Jville $0434$

Birm$-$Mem $0234$

Birm$-$Myrtle $0508$

Birm$-$Nash $0192$

Birm$-$Norf $0715$

Birm$-$Phil $0880$

Birm$-$Wash $0744$

CharWV$-$Green $0245$

CharWV$-$JackMS $0801$

CharWV$-$Jville $0642$

CharWV$-$Mem $0597$

CharWV$-$Myrtle $0429$

CharWV$-$Nash $0388$

CharWV$-$Norf $0403$

CharWV$-$Phil $0466$

CharWV$-$Wash $0362$

Green$-$JackMS $0713$

Green$-$Jville $0456$

Green$-$Mem $0675$

Green$-$Mrytle $0214$

Green$-$Nash $0464$

Green$-$Norf $0236$

Green$-$Phil $0431$

Green$-$Wash $0309$

JackMS$-$Jville $0590$

JackMS$-$Mem $0209$

JackMS$-$Myrtle $0743$

JackMS$-$Nash $0414$

JackMS$-$Norf $0948$

JackMS$-$Phil $01115$

JackMS$-$Wash $0980$

Jville$-$Mem $0677$

Jville$-$Myrtle $0358$

Jville$-$Nash $0596$

Jville$-$Norf $0613$

Jville$-$Phil $0844$

Jville$-$Wash $0706$

Mem$-$Mrytle $0752$

Mem$-$Nash $0212$

Mem$-$Norf $0898$

Mem$-$Phil $01014$

Mem$-$Wash $0879$

Mrytle$-$Nash $0589$

Mrytle$-$Norf $0339$

Mrytle$-$Phil $0571$

Mrytle$-$Wash $0432$

Nash$-$Norf $0688$

Nash$-$Phil $0802$

Nash$-$Wash $0666$

Norf$-$Phil $0290$

Norf$-$Wash $0209$

Phil$-$Wash $0137$