1. A city is planning to develop a road system linking City 1 to City 9, depicted in the below figure (the numbers next to each arc indicate distance in miles). Two proposals are under consideration: A series of six-lane super-streets linking all 9 cities shown in the figure. Super- streets are estimated to cost $600,000 per mile to build. A ten-lane freeway extension connecting City 1 with City 9 (which does not nec- essarily pass through all nine cities.) Each mile of the freeway will cost $800,000.

1. What type of optimization problem can be used to model the first proposal? Write this formulation, including descriptions of the constraints.

2. Solve this problem using any exact method, and provide the total cost of the proposal.

7 10 5 11 13 5 4 3 4 5 5 8 7 8 8 9 6 7 10 5 11 13 5 4 3 4 5 5 8 7 8 8 9 6