PROJECT: TRAVELING SALESMAN ASSIGNMENT INSTRUCTIONS OVERVIEW Two 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 is primarily focused on using Excel to work through a very prominent optimization strategy. In each case, this is done within the context of a well-known and historically signification problem (in the case of the Traveling Salesman Problem, its likely the most famous problem of them all). Besides introducing you to two important problems, the projects require you to implement a strategy for finding good solutions to these problems. In each case, the strategy is somewhat tailored to the specific problem but also serves to represent a broadly applicable approach (a meta-heuristic, so to speak) of great value. Each project assignment utilizes Excel to perform computations that would be too cumbersome to do by hand. By using Excel strategically, you will work to find good solutions to difficult problems. INSTRUCTIONS Perhaps the most famous problem in Operations Research is the Traveling Salesman Problem (TSP): so easy to explain, so hard to solve. The idea is pretty straight-forward: we try to construct the minimum cost (or mileage) route that begins and ends at the same place and visits each required location. Many networks problems can be solved by creating linear programming (LP) formulations. TSP cannot, but there are LPs that can provide a helpful tool. One formulation that might at first appear to be sufficient is given below: Let x_(i,j)={(1 if the route includes the arc from city i to city j@0,otherwise) Our LP relaxation is as follows Min Z=_(j=i+1)^n_(i=1)^(n-1)c_(i,j) x_(i,j) s.t. _jx_(i,j)=2 for all city i^' s all x_(i,j)0 Essentially, the constraint ensures that we must take an arc into each city and out of each city so that our path visits each city. The problem with this formulation is what are called subtours. Theres nothing in the constraints that would prohibit multiple separate paths. For example, we might have one path that connects 4 cities and another that connects the remaining 9. Lets say that the arcs involved are x_(1,2),x_2,3,x_3,4 and x_1,4. We can eliminate this particular subtour and improve our formulation by adding the constraint: x_(1,2)+x_2,3+ x_3,4+x_1,43. Note that since the right-hand side value is 1 less than the number of arcs, this ensures we dont get this particular subtour. The problem is that there are a combinatorial number of subtours. Fortunately, most of them are not practical and thus only a small fraction of these subtours need to be explicitly eliminated by adding constraints. 1. Youve been provided with spreadsheet that allows you to solve this LP relaxation for a 13-city TSP (make sure you use the Simplex Method and NOT the GRG algorithm!). a) Add constraints to set the city constraints (cells G2 through G14) = 2 and to make all the variables integers. You can make all of the variables integers all at once: when you choose to add a constraint, Excel brings up the Add Constraint window. In the Cell Reference block, just drag your mouse over all the decision variables (cells D2 through D79) and then select to make them integers. You can also type D2:D79 in the Cell Reference box. Do not make them binary, as one of your later tasks will be to use inequalities constraints to prevent any cell from exceeding 1. One you have added these constraints, you can use the Solver to find a solution to this LP (call it LP1). Give the optimal objective function value of LP1: (10 points). 2. The first problem youll find is that several arcs equal 2. (This wont happen if you made all your variables binary, so if you added this constraint, go back and remove it. 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. (8 points) 3. Add constraints to your LP to give an upper bound of 1 to the arcs identified in question 2. Solve the improved LP relaxation (LP2) and give the new objective function value. (8 points). 4. The solution of LP2 should have subtour. (If instead you get a solution with other arcs with values greater than 1, then add constraints to eliminate these.) However, LP2s solution should have a subtour. Use the arcs whose values are equal to 1 to identify the paths in your solution. Find the smallest subtour and add a constraint to eliminate it For example: if cells D2, D3 and D14 all equal 1, this would give a subtour from Atlanta to Baltimore to Birmingham and back to Atlanta. You would eliminate this by adding the constraint =D2+D3+D14 2. Give the smallest subtour that you found. (8 points). 5. Create a constraint to eliminate the subtour identified in the previous question and re-solve the LP relaxation. Give the optimal objective function of the new LP (LP3). (8 points) 6. Both LP3 and LP4 should have subtour that are similar to the first ones that you encountered. Add the subtour associated with these LPs and record the optimal objective function values for LP4 and LP5. (8 points). 7. Considering the similarities of the subtours that weve eliminated one at a time, could you come up with a better constraint that would have eliminated all of these subtours at once? (3 points) 8. See if you can find the optimal solution to the 13-city TSP by continuing to eliminate subtours (including bounding any arcs with values greater than 1). On my 8th LP relaxation, Solver found a single tour that I believe is the optimal solution to this TSP. See what you can come up with as your best tour, either by continuing to add subtour constraints or by building one yourself using what you have learned from the LP solutions. Provide the tour (e.g Atlanta to Birmingham to ), along with the associated costs. (7 points).