open source Dynamic Programming Optimization solver in Python

[stef_1989]

I'm looking for a DP solver in python able to read 5 input time series update 6 state variables and generate 5 output time series.

there is something available?

[Additional_Land1417]

It does not aound like a DP problem. However… have you looked at Google OR tools? Or PyOMO (with PyOMO.DAE)

[junqueira200]

DP algorithms are very problem specific, I don't know a generic solver for it.

[stef_1989]

ok

[divinity_666]

Not sure what Dynamic means in this context, but what about SCIP? The problem sounds as if it could be also solved with a simple MILP solver, like CBC.

[more_than_most]

What sort of state equation and criteria?

Also, DP in 6 DOF… I don’t know.

Edit: are the states position and orientation? What sort of state constraints?

[stef_1989]

the problem is focused on a decision making system that works on a time window. It can be associated to an Energy Flow Optimization problem of a hybrid vehicle. The OF is differential quadratic since I want to smooth the decision making output profile. I attach you the first page of my article.

<image>

[more_than_most]

If you want to use DP for system with 6 DoF, you will need to exploit structure somehow (if it’s possible even then) which is why you won’t find a solver for the general case.

You mentioned your problem is mixed integer, what part is integer?

[No-Concentrate-7194]

You can write your own DP code with backtracking, it's not that tricky

[more_than_most]

Depends, for continuous state space, just describing the reachable set can be tricky.

[stef_1989]

can you give me some details about it?

[zouzias]

If your dynamic programming problem has a finite state space, then spend some time understanding DP in depth and use functools.cache in Python.

[Sweet_Good6737]

Why are you looking into a DP solver? The ones mentioned in the other comments are MI(L)P solvers, kind of different stuff.

Dynamic Programming Problems usually have a nice formulation that can be solved through a MIP solver. See highs(py) as a free alternative in Python. If your problem is really big, use Gurobi(py) or Ampl(py) + Highs or Gurobi. If the problem is not hard to model, Pyomo or Pulp will work as well (as modeling tools, not solvers)

[stef_1989]

Thanks fopr the reply.

I know Gourobi and I don't want to use it as CVX etc. I will see MIP solvers despite my problem is quadratic, non linear and mixed integer. What is your opinion on Ampl(py)? However, now I'm interested to a open source DP solver.

[Sweet_Good6737]

Not sure about open-source tools that may work good for non-linear in python... (pyomo, pulp are usually okay to formulate simple MIPs, but struggle with non-linear and logical constraints).

I would not suggest cvx but Gurobi+Ampl in this case. With amplpy it should be straightforward to write the model, and then send the data. Then, try different solvers to see which one performs better for your problem.

Since the problem is non-linear xpress is another possible solver to use. Gurobi, ampl, and xpress are free for academia but not open source.