Optimization Methods II (DS 808) Spring 2022

Assignment #1

Due: Thursday, April 6th @ 5:40pm, on Canvas

Work in groups of two. Both your names should appear on your submission.

Part (a): Shortest Path Formulation (15 pts)

The following diagram shows a network of streets (links) and junctions (nodes) with travel times shown in minutes. Two of the streets are one-way streets, as shown with an arrow. The rest are bidirectional. Formulate a linear program that finds the shortest path from location (1) to location (10). Clearly define your decision variables (in one line, like _ij = ) and then write the objective function and all constraints algebraically.

Important Note: In Optimization Methods 1, you probably learned to write the constraints as Outflow

= 1 for the origin node, Inflow = 1 for the destination node, and Outflow = Inflow (transship) for all the other nodes in between. Since later in this assignment, we want to look at the dual problem and the objective here is Minimize, it is easiest if all the constraints are written as . Therefore, please use an alternative logic that says: Outflow 1 (basically Outflow1) for the origin node, Inflow 1 for the destination node, and Inflow Outflow for all the transship nodes in between.

Hint / Reminder: In all network flow problems, we need 1 decision variable for each arc/link, and 1 constraint for each node. So, you should need 29 variables, and 10 constraints.

Part (b): Solving the Problem (15 pts)

Solve your formulation from part (a) in Excel and Python. All the network links and travel time information is available in PathData.xlsx for your convenience.

Attach your Excel file and Python file with your submission.

In your report: Include a screenshot of your solver result and describe the optimal solution in words (that is, the optimal travel path, and the distance). Include a screenshot of your cvxpy setup and solution.

Report the shadow prices (dual values) of the constraints.

Part (c): Interpreting the Shadow Prices (10 pts)

In profit/revenue maximization problems, usually we have constraints that have to do with limited resources, and the shadow prices will tell us the marginal value of each resource. In cost minimization problems, constraints tend to be in form and have to do with minimum requirements we need to meet, and the shadow prices will tell us the degree to which relaxing/tightening each requirement can decrease/increase our cost.

In the shortest path problem, it is not too obvious what the shadow prices to those transship constraints mean (since the right-hand sides are not really tangible resources or supply and demand). Compare the shadow prices you got in part (b) against the network diagram and see if you can find any pattern and make sense of those numbers. Describe in a short paragraph what the shadow prices are telling us.

Hint: We have a shadow price for each node in the network. Here are some ideas: Pick two adjacent nodes and subtract their shadow prices. Pick two non-adjacent nodes on the shortest path and subtract their shadow prices. Pick a node off the shortest path and try to find the shortest time you can get there from the origin node (1).

Part (d): Dual Problem (10 pts)

Algebraically, write the dual problem to your formulation from part (a). No need to solve.

Hints: The dual of a minimization problem with constraints, is a maximization problem with constraints. You need a variable for each constraint (node), and a constraint for each variable (link). So, the dual problem will have 10 variables (lets call them ₁ through _1$) and 29 constraints. There is a simple pattern to the constraints, so once you figure out a couple of them, then you can write the same thing for each link. In fact, it is enough (and even more professional) to just write one line and say: For each link that connects node to node , we need a constraint . and write the constraint that involves variables _i and _j (and possibly the travel time on the link connecting and ).

Briefly explain whether you see any similarity between this formulation and the one we wrote for the Project Scheduling example in class. Looking at this formulation, your observation in part (c), and possible similarities to class example, what words do you think best describe the meaning of decision variables here?