Consider the following network: 5 8 -10 2 3 (a) What is the shortest path from...

 

Transcribed Image Text:

Consider the following network: 5 8 -10 2 3 (a) What is the shortest path from s to t? (b) What happens when you run the label-correcting algorithm? (c) Write the dual of the LP that formulates the shortest path problem on this network. (d) Show that this dual is infeasible. Hint: consider the cycle a, b, c. Each arc of this cycle corresponds to a constraint of the dual. Write these constraints and argue that they cannot be simultaneously satisfied. Using Gurobi, check that the dual LP is indeed infeasible. Consider the following network: 5 8 -10 2 3 (a) What is the shortest path from s to t? (b) What happens when you run the label-correcting algorithm? (c) Write the dual of the LP that formulates the shortest path problem on this network. (d) Show that this dual is infeasible. Hint: consider the cycle a, b, c. Each arc of this cycle corresponds to a constraint of the dual. Write these constraints and argue that they cannot be simultaneously satisfied. Using Gurobi, check that the dual LP is indeed infeasible.