Timeline for Can dynamic programming find globally optimal solutions for scheduling problems
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2023 at 7:26 | comment | added | PeterBe | Thanks for your answers prubin. I appreciate it. | |
| Oct 23, 2023 at 7:26 | vote | accept | PeterBe | ||
| Oct 20, 2023 at 22:35 | comment | added | prubin♦ | Assuming your problem meets the criteria of DP -- the cost going forward (or backward, depending on how you formulate) is a function of the current state but not how you got to it -- I don't see why DP couldn't solve the discrete state space version. I'm not sure how the continuous state version would play out. | |
| Oct 19, 2023 at 8:05 | comment | added | PeterBe | Any comment to my last comment? I'll highly appreciate any further comment from you Prubin about this issue. | |
| Oct 16, 2023 at 7:51 | comment | added | PeterBe | Thanks prubin for your answer. But when the state space is not discrete by nature (it is a state of charge of the battery ranging from 0 to 100 % and it has continious values) can DP still provide the globally optimal solution? What if I discretize the state space (this is something you can always do) let's say in 100 values (thus not allowing decimal numbers like 1.5), can DP then solve this problem optimally? | |
| Oct 12, 2023 at 15:15 | comment | added | prubin♦ | If you are using backward recursion, the decision at stage $n$ takes into account costs at stage $n$ and all future stages. You make the decision $x$ that optimizes $c_n(x) + f_{n+1}(x)$ where $c_n(x)$ is the cost at the current stage and $f_{n+1}(x)$ is the optimal cost of all future stages given the state you are put into at stage $n+1$ by deciding $x$ in the current state. | |
| Oct 12, 2023 at 8:36 | comment | added | PeterBe | Thanks for your answer. Regarding the discrete state space. Actually a battery has a state of charge in %. So it is by nature continious. However, you can of course discretize it, for example having 100 states (one for each percentage). Apart from that, I still have the gut feeling that even when having a discrete state space, DP can't solve it optimally, as it applies a greedy strategy. In every timeslot it decides only about the current action using the state of the current timeslot. It does not consider future values (e.g. about the availability) in the current timeslot. | |
| Oct 11, 2023 at 15:37 | history | answered | prubin♦ | CC BY-SA 4.0 |