IOE 512: Dynamic Programming - Homework 1: Dijkstra’s algorithm
Instructions
IOE 512: Dynamic Programming Homework 1
FA2022
Save your homework file in the following format:
FirstName LastName 512 HW1.pdf
Make sure to include your name and the names of anyone you collaborate with on the front page of your homework. You will need to submit the PDF file for your homework solutions and also data instances and code files for the coding questions.
Questions
The following questions are related to the shortest path and machine/equipment replacement problem.
1. (25 pts) Michael is late for IOE 512 and would like to take the shortest path from his apartment to 2153 GGBL. Figure 1 illustrates the network of roads (and hallways) that connect Michael’s apartment and 2153 GGBL on campus, where the edges that represent roads (and hallways) are labeled with travel time, in minutes. Use dynamic programming to determine the route that Michael should take to reach the classroom the fastest.
Clearly define all stages, states, actions, reward functions, and provide details (including value function) for all algorithm iterations to gain full points. Clearly state the final solution (i.e., the shortest path from Node A to Node H and its travel time).
2. (25 pts) Find the shortest path from Michael’s apartment (i.e., Node A) to the front door ̄
3. (25 pts) Implement both the DP algorithm in Question 1 and the Dijkstra’s algorithm in Question 2 using a programming language of your choice. (You can verify whether your code is correct by testing them on the data in Questions 1 and 2 and see whether you obtain the same optimal solutions.)
Then, change the input data file for the Dijkstra’s algorithm by using the network in Figure 2 and test your code to find the shortest path from Node J to Node I. (Please make sure you submit both your DP and Dijkstra codes and also clearly state the final solution for
(i.e., Node D) in Figure 1 using Dijkstra’s algorithm. Clearly state the nodes in set S, S, each node’s distance label, their predecessor in each iteration. Clearly state the final solution and optimal objective (i.e., the shortest path from A to D and its travel time).
Figure 1: Figure for Questions 1, 2, and 3
Figure 2: Figure for Question 3
the shortest path from J to I. For this question, you do not need to state the step-by-step Dijkstra as I can output those from your code.)
- Make sure that your code is written in a general way rather than only for the previous figure so that you only need to change the input data file which is associated with a specific network.
- If you submit one specific Dijkstra code for Figure 1 and another Dijkstra code for Figure 2, you will be deducted points.
- You do not need to test the DP for the network in Figure 2 since it has directed cycles.
4. (25 pts) A car manufacturer can purchase a new tool for $1 million. The annual operating costs and resale values are provided in the following table. If the manufacturer has a new tool right now, determine a replacement policy that minimizes total cost of owning and operating the tool over the next 7 years. Clearly define all stages, states, actions, reward functions, and provide details (including value function) for all algorithm iterations to gain full points.
Age of the Tool (Years) | Resale Value ($ millions) | Operating Cost ($ millions) |
0 | 0.6 | 0.20 |
1 | 0.45 | 0.25 |
2 | 0.35 | 0.35 |
3 | 0.25 | 0.50 |
4 | 0.15 | 0.65 |
5 | 0.1 | 0.75 |
6 | 0.05 | 0.80 |
7 | 0 | - |
Table 1: Parameters for Question 4.
