A book salesperson who lives in Basin must call once a month on four customers located in Wald, Bon, Mena, and Kiln before returning home to Basin. The following table gives the distances in miles among the different cities.

Miles between cities Basin Wald Bon Mena Kiln Basin 0 125 225 155 215 Wald 125 0 85 115 135 Bon 225 85 0 165 190 Mena 155 115 165 0 195 Kiln 215 135 190 195 0 The objective is to minimize the total distance traveled by the salesperson.

(a) Write down the LP for computing a lower-bound estimate on the optimum tour length.

(b) Compare the lower bounds on the optimum tour length using both the assignment model and linear programming. Is the assignment model solution optimum for the TSP?