Consider a road network $($N$,$ A$)$ that allows for travel between two locations s and t$,$ where s$,$t $$ N$.$ The lengths Cy $>0$ of road segments $($i$,$j$)$ A between two locations i$,$ j $$ N are given to us as data. We wish to find the shortest route between s and t$.$ However, there are three locations W$1,$ W$2,$ W$3$ E N$\backslash \{$s$,$t$\}$ that are very expensive to keep open.

$($a$)$ We must choose exactly one of them to keep open, while the other two must be shut down. Shutting down a location means that no path can pass through it$.$

Formulate a mixed integer program to decide which two locations to shut down in order to make the route between s and t on the remaining network as short as possible.

Hint: shutting down a node i is equivalent to ensuring that no flow goes through any of the incoming or outgoing arcs.

$($b$)$ Suppose that the locations w$1,2,$ W$3$ have fixed costs fi$,$ f$2,$ f$3$ to open.

Suppose now that there is a budget B $<$ fi $+$ f$2+$ f and that the total fixed cost of all open locations cannot exceed B$.$ Describe how to modify the model above to decide which locations to open.

$($c$)$ Suppose you solve the shortest s$-$t path problem while keeping all three expensive locations open. How can you use the solution to determine whether you have to formulate and solve the integer program at all?