How to use MILP in Gurobi when objective function is not a direct function of design variable
Hi, I am new to Gurobi and am trying to figure out a way to solve a problem where my objective function is a linear combination of some variables (N_i(x)), and my design variable is x. My constraint is a function of x.
-
Hi Pranav,
Are the \( N_i(x) \) functions of \( x \), and your objective function is (e.g.) \( \sum_{i} a_i N_i(x) \)? If so, one way to model this is as follows:
- Introduce variables \( y_i \) for all \( i \)
- Add constraints \( y_i = N_i(x) \) for all \( i \)
- Set the objective function to \( \sum_{i} a_i y_i \)
Note that Gurobi 8.1 supports linear and convex quadratic constraints. Gurobi 9.0, to be released in a few weeks, additionally supports nonconvex quadratic constraints. Thus, the ability to model \( y_i = N_i(x) \) ultimately depends on what kind of functions the \( N_i(x) \) are.
Thanks!
Eli
1 -
I'm having a similar problem (also new to Gurobi), though instead of ∑a_i*N_i(x_i),
my objective is ∑x_i*N_i(x_i),
where N_i is a linear function of x_i: N_i(x_i) = slope*x_i + base. I'm trying to minimize total cost for a blending model given quantities x_i and unit prices N_i(x_i), since unit price is a function of the quantity purchased.
I added the constraints and set up the objective function as stated above, but for any non-zero slope I get the following error:
GurobiError: Objective Q not PSD (diagonal adjustment of 1.0e+00 would be required)I assume this is due to using quadratic objective functions, given it solves when unit cost is independent of quantity. Is this problem something I should just wait for Gurobi 9.0 to try and solve, or are there alternatives? I've tried approximating the quadratic objective functions using McCormick envelopes, but although the model runs, the results are nonsensical. Sorry for the weird formatting, I can't seem to figure out what is wrong, and thanks for any help or advice!
0 -
Thanks a lot Eli. I have another question. How do I calculate values of N_i(x) for each iteration in the Gurobi solution process. I checked online and it was mentioned using attributes. I am using MATLAB and nowhere is it mentioned how to access x for each iteration using MATLAB.
0 -
Pranav, you can solve the problem in MATLAB using a command like:
result = gurobi(model, params);
After this is done, you can access the x field of the returned struct to find the optimal solution values:
for i=1:length(result.x)
fprintf('%d\n', result.x(i));
endIn the MATLAB API, building a model is matrix-based. Thus, you have to keep track of which indices (columns) correspond to the \( y_i \) variables. You can find more information about accessing information like solution values and objective function values here.
John, that error is returned because your quadratic objective function is nonconvex. Gurobi 8.x does not support nonconvex quadratic objectives or constraints. To deal with this, you could:
- Construct a piecewise linear approximation of each \( x_i N_i(x) \) objective term. I'm not sure which API you're using; in Python, this can easily be done with the Model.setPWLObj() method.
- Wait for Gurobi 9.0, scheduled for release in a few weeks. This version supports nonconvex quadratic objectives and constraints.
I hope this helps!
Eli
0 -
Thanks for the response, Eli (and Pranav, sorry for slightly stealing your thread, but also thank you for asking this question!). I do have a few questions about the Model.setPWLObj() method, since I am working in Python. I'm curious whether I am implementing this correctly: Since Model.setPWLObj() requires a Var, I've tried defining a set of variables q_i, then for each i setting the piecewise approximation using Model.setPWLObj(q_i, array of potential values for x_i*N_i(x_i), array of potential values of x_i). I may be misunderstanding what setting the piecewise objective does, and perhaps this is starting to be better suited to starting a separate thread, but I am unsure as to how I can get the piecewise objective to influence x_i.
With the y_i == N_i(x_i) constraint still in place, setting the constraint that q_i == x_i*y_i leads to the same error as above (Q matrix is not positive semi-definite). If I leave the q_i == x_i*y_i constraint out, the model solves but gives results that shouldn't be possible, e.g. it doesn't stop using a material once it becomes more expensive than another of equal composition.
0 -
Hi John,
With the piecewise approximation approach, it should work to define the piecewise linear objective for each \( x_i \) variable. This doesn't require any additional variables. Also note that in the arguments for Model.setPWLObj(), the list of \( x \)-values is second and the list of \( y \)-values is third.
Below is a small example of using a piecewise approximation to model \( \min \{ x N(x) : x \in [-2, 2] \} \), where \( N(x) = 2x - 1 \). We discretize \( x N(x) \) using 41 points spaced equally over the interval \( [-2,2] \):
from gurobipy import *
m = Model()
xs = [0.1 * i for i in range(-20, 21)]
ys = [i * (2*i-1) for i in xs]
x = m.addVar(lb=-2, ub=2, name="x")
m.setPWLObj(x, xs, ys)
m.optimize()In this example, \( x \) is allowed to take on any value over the interval \( [-2, 2] \). The corresponding objective penalty is our piecewise approximation of \( 2x^2 - x \).
Does that help give you an idea of how to structure the piecewise approximations for your problem? If not, we can continue the discussion in another thread. Thanks!
Eli
0 -
Hi Eli,
That was extraordinarily helpful, thank you so much! I appreciate the help!
John
0 -
Hi Eli,
Thank you for your suggestion. I tried doing what you said, but I always get the solution as the lower bound which I have set.
Here is my problem,
Max f(x) = sum(a_i*N_i(x))
subject to sum(x_i) <= K
x_i >= 0
N_i's(x) are not a linear function of x and depend on random variables, but as x increase N_i(x) will increase for sure. I have a function running in MATLAB which will calculate N_i's(x) for every value of x. Even after doing what you asked me to do, I am still getting the optimal solution as [0,0,0,...], which is clearly not right. Can you suggest what can be done?
0 -
Hi Pranav,
By default, Gurobi will try to minimize the objective function. Did you change the objective sense to maximize? I.e., using
model.modelsense = 'max';
If that isn't the problem, do you have a (hopefully small and self-contained) code example that replicates the behavior? Thanks!
Eli
0 -
Hi Eli,
Yes I have changed the modelsense to max.
If I am using another algorithm, I am able to solve the problem. The value of N_i(x) will change everytime x changes, thus objective function should change with change in x.
0 -
Hi Pranav,
This depends on the structure of \( N_i(x) \). You will have to provide Gurobi with an explicit expression for \( N_i(x) \) (or an approximation thereof) rather than relying on an external MATLAB function to evaluate \( N_i(x) \).
Do you have a small, self-contained code example that reproduces the behavior and shows what you are trying to do with \( N_i(x) \)?
Thanks!
Eli
0
Please sign in to leave a comment.
Comments
11 comments