Consider the following special type of shortest path problem where the nodes are in columns and the only paths considered always move forward one column at a time. The numbers along the links represent distances (in miles), and the objective is to find the shortest path from the origin to the destination. This problem also can be formulated as a BIP model involving both mutually exclusive alternatives and contingent decisions. (a). Formulate an algebraic BIP model for this problem, and identify the constraints for (1) mutually exclusive alternatives and (2) contingent decisions.

(b). Formulate and solve this BIP model on a spreadsheet.

Excel solution with screenshots of sheet and also formulas used in cells as well as solver solution.