Question: BIP/Assignment Problem (20 pts)

a. Consider the following diagram of 4 cities, A, B, C, and D.

A salesman is planning to visit the 4 cities in order to pitch a new product in a marketing campaign. He is required to travel to each city only once. The distances (in miles) between cities are given in the diagram or in the following table.

The salesman’s objective is to minimize the total distance that he has to travel while visiting each city only once. The exception is that he has to return to the starting city.

[Note: When he is in a city, his next stop cannot be to the same city. For example, if his current location is A, his next stop can only B, C, or D. Also, if he has visited a city earlier, he cannot go back to that city again (other than returning at the end of the trip). For example, in terms of paths, if path BA is taken, then path AB cannot be taken. It does not matter where or in what city the salesman starts his trip].

a. Formulate algebraically as an assignment problem, together with the decision variables, objective function and the constraints. The constraints should take into account the usual assignment constraints, and the comments under the Note above.

b. Formulate in Excel and solve using Solver.