In 1862, during the second year of the Civil War, General Thomas J. “Stonewall” Jackson fought a military campaign in the Shenandoah Valley in Virginia. One of his victories was at the Battle of McDowell.

(a) Determine the shortest route from Winchester (node 1) to McDowell (node 14) by solving the problem by hand (show the work: the permanent set at all the iterations, and the list of available branches at the first two and last two iterations).
(b) How many days will the army take to get to the destination, McDowell based on the solution in (a)?
(c) Formulate an integer programming model for this problem.
(d) Find the optimal path in (c) by using the computer, and compare it with the path in (a).
(e) What is the new optimal path to McDowell if the path from Winchester to Moorefield were blocked due to a landslide?
(f) What is the new optimal path to McDowell if his army couldn’t approach to Franklin because of epidemics in the village?
 

Romney 2 2 Winchester 1 Moorefield 3 Strasburg Mount Jackson 2 7 1 Front Royal Franklin 6 11 Woodstock New Market McDowel 8 Luray 14 10 Harrisonburg 12 13 Port Republic Staunton 2.