Constrained Dynamic Programming with Gurobi in R
AnsweredHi,
I hope this message finds you well. I am currently working on a project that involves solving a constrained dynamic program using the Gurobi package in R. Specifically, I am optimizing a decision at N time stages, and at each time stage \(t\), I need to solve the following problem:
\(\min c^{T}x + Q(x) \text{ subject to } A^{T}x=b \text{ and } x>=0\)
Here, \(x\) is the decision vector, \(c\) is the cost vector, \(A^{T}x=b\) represents the constraints, and \(Q(x)\) is a convex function of \(x\) for which I don't have an analytic expression. However, I do know its value for each possible decision vector \(x\), and I can confirm that \(Q(x)\) is convex based on the problem's properties.
I have reviewed the example provided in the Gurobi documentation [https://www.gurobi.com/documentation/current/examples/piecewise_r.html], which demonstrates how to handle cases where \(Q\) can be expressed as the sum of functions for each component of the decision vector. However, this approach does not directly address my scenario where \(Q\) is a convex function without an explicit expression, but its values are known for each \(x\).
I would greatly appreciate any guidance or examples that can help me adapt the Gurobi framework to handle this specific case. If there are relevant resources or examples that I may have missed, please point me in the right direction.
Thank you in advance for your time and assistance.
-
Official comment
-
Gurobi Staff
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi George,
This might be a good use case for gurobi-machinelearning where you approximate Q with surrogate modelling. If you know the value of Q for each x, and the domain of x is not prohibitively large, then you can train a machine learning model (and you may as well overfit) on a dataset containing all possible values of x (and Q(x)), and then embed this in your model.
- Riley
0 -
-
Hi Riley,
Thanks for your answer. I am using Gurobi in R and below I try to rephrase my question with a little more context.
Suppose I have a current solution x_k and I let f_k(x)=a_0+a^{T}(x-x_k) with a, x, and x_k being 3-dimensional and b 1-dimensional. I solve min{c^{T}x + Q_k(x) : Ax = b, x > 0} to obtain the next value x_{k+1} and finally I update Q_{k+1}(x)=max{Q_{k}(x), f_k(x)}.
My point is that Q_k(x) is the max of a sequence of supporting hyperplanes that approximates the true function Q(x). Is there a way to put this approximation Q_k in the objective function of R gurobi so that I can solve this convex optimization problem min{c^{T}x + Q_k(x) : Ax = b, x > 0}?
Thank you in advance for your help.
- George0 -
-
-
Hi George,
Sorry about that, at some point after thinking about the problem the fact you were using R got forgotten. What does Q_0 look like? I'm thinking you can probably formulate the problem:
min{c^{T}x + y : Ax = b, y >= f_k(x) \forall k, y >= Q_0, x > 0}so you would just keep adding y>= f_k(x) iteratively.
- Riley
0 -
Post is closed for comments.
Comments
4 comments