1
$\begingroup$

I want to know if dynamic programming can generally find globaly optimal solutions for scheduling problems? I think this might be difficult as dynamic makes one at a time decisions without calculating a schedule for the whole timespan. For that you need something like a linear/non-linear program as far as I see it.

Let's look at one example from the field of energy. Suppose we have an electric vehicle and a time-variable electricity tarif. Now the goal is to charge the electric vehicle such that the overall charging costs for the next day are minimized while having the battery state of charge at a certain minimum value. Tranditionally, this is optimally solved by defining a MILP problem and solving using a solver (with some MIP gap). The output is a schedule which specifies for each hour of the day the charging power (of course we'd need some information about the availability of the electric vehicle)

Now if you apply dynamic programming to this problem, you make sequential decisions at every hour as far as I understand. This can't normally be globally optimal as you don't consider all timeslots and future values (e.g. availability) together to make your decisions.

So can dynamic programming still in fact find the globally optimal solution for such a time constrained scheduling problem.

Improve this question
$\endgroup$
2
  • $\begingroup$ Dynamic programming is an optimization method that consists in solving a problem by recursively decomposing it into multiple subproblems, while storing the results of these subproblems to avoid solving them multiple times $\endgroup$
    – fontanf
    Commented Oct 11, 2023 at 12:52
  • $\begingroup$ @PeterBe, In the scheduling literature, there exist dynamic programming in the fully polynomial time approximation class which can solve some specific Np-hard problem optimality. $\endgroup$
    – A.Omidi
    Commented Oct 11, 2023 at 14:09

1 Answer 1

Reset to default
4
$\begingroup$

Assuming your state space is discrete (for instance, there are finitely many possible charge levels for the vehicle), and assuming that how much you pay for charging depends on the amount of charging you do but not your past history (for instance, you are not accruing credits toward some sort of discount), then yes, you can solve your problem using DP ... in theory. Since you need to break the problem into stages (every hour, every day, ...) and define a state space for each stage, the primary practical question is how large the overall number of states gets.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – PeterBe
    Commented Oct 12, 2023 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Oct 12, 2023 at 15:15
  • $\begingroup$ 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? $\endgroup$
    – PeterBe
    Commented Oct 16, 2023 at 7:51
  • $\begingroup$ Any comment to my last comment? I'll highly appreciate any further comment from you Prubin about this issue. $\endgroup$
    – PeterBe
    Commented Oct 19, 2023 at 8:05
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Oct 20, 2023 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.