Constrained Dynamic Programming with Gurobi in R

Answered

George Vassos

January 09, 2024 09:58

• 
• 
• 

Hi,

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.

Related to

• R

0

• 

  Riley Clement

  • Gurobi Staff

  January 10, 2024 04:30

  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
• 

  George Vassos

  January 12, 2024 07:34

  • 
  • 
  • 

  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.
  
  - George

  0
• 

  Riley Clement

  • Gurobi Staff

  January 12, 2024 07:56 Edited

  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

Please sign in to leave a comment.