Tell Gurobi about optimal variable value depending on a set of other variables
Ongoing
I'm modelling a scheduling problem (see below for a concrete example). In this problem, I have a set of (integral) variables modelling the start times assigned to jobs. I have a second set of binary "order" variables modelling the property "job A finishes before job B starts". The latter variables are used to model the amount of resources in use by jobs at each point in time. Given a fixed assignment of start times, setting one of the "order" variables to 1 can only improve the objective, since that means that less resource is in use at some point in time.
Thus, I have this property: Given a fixed assignment of start times, all order variables that can feasibly be set to 1 should be set to 1. Is there any way of telling Gurobi this in the model? I know about the variable hints, but I'm not sure if this is the right tool. I also know that I could work with callbacks, modifying each found solution programmatically - however, I wonder if there is a more elegant solution.
Concrete Example
There are \(n\) jobs \(1\dots n\). Let \(s_i\) be the (integral) start time of job \(i\). Then, the binary "order" variable \(o_{i,j}\) for jobs \(i\) and \(j\) is constrained to:
\[o_{i,j} \leq 1 - (s_i - s_j)/M\]
for some appropriate M. This way, \(o_{i,j}\) can become 1 only if \(s_j \geq s_i\), thus indicating an order of the starts of \(i\) and \(j\). Building the amount of resource in use from these order variables is a bit more involved - however, an order-variable being set to 1 (instead of 0, all other variables not changing their values) can always only improve the objective value.
Thanks in advance for any help.
Lukas
-
Official comment
This post is more than three 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 why not try our AI Gurobot?. -
Hi Lukas,
I am not sure if I fully understand your question.
You say that you have a fixed assignment. Does this mean that you have some fixed data which you can use to alter your model before you start the optimization? If this is the case, then it is always best to do this before the optimization starts, e.g., by directly altering your model or adding some fixing constraint of the kind \(x=2\) before calling the Model.optimize() function.
If this fixed assignment is only a guess, then providing it as a starting solution to Gurobi would most likely provide the most benefit.However, if you mean that you are able to deduce some additional information from each found feasible solution point, then I would recommend to either use callbacks or directly try to model the property you are using. For your ordering, you could maybe use a constraint of the form
\[o_{i,j} \leq o_{k,j}\]
with \(k>i\) in your ordering scheme. The suggested inequality is very vague as I don't fully comprehend your model.
Best regards,
Jaromił1 -
Hi Jaromił,
Thanks for your reply. I'm sorry, I think I did not describe my situation correctly. I do not know any variable assignments before optimization (otherwise I could just make them constants…?), and also I do not have any educated guesses, so I can't just supply a start solution (actually I have that and I do supply a start solution, but that doesn't fix my problem).
But, given any feasible solution (which I do not know before optimization), while fixing the values in this solution for a set of variables (let's call them $F$ for "fixed"), I can trivially compute the optimal variable assignment (under the fixed assignment on $F$) for a second set (call it $D$ for "dependent") of variables. Basically, there is some trivial "hill climbing".
This stems from the fact that $F$ are the "actual decision variables" of my model, determining in my scheduling problem the start times of jobs, and $D$ is just some indicator variables which should always be $1$ if that is permissible by $F$.
The problem is that in large models, which do not finish by the time limit set by me, Gurobi often returns a solution in which $D$ is not assigned optimally - i.e., some indicator variables are $0$ when they should be $1$ (which would directly improve the objective).
I know I could register a callback that checks the values for $D$ after every found solution, doing the hill-climbing, and providing a potentially better solution back to Gurobi. I just wonder if something similar is possible with less effort.
Thanks for your help!
0 -
Hi Lukas,
Thank you for the clarification.
To me, this sounds like a very good application for a callback.
An alternative which might work would be to model the relationship "$D$ is just some indicator variables which should always be $1$ if that is permissible by $F$" directly via the addition of auxiliary binaries and indicator constraints stating that
if some variable in F has value x, then variable in D has to be one.Please note that even if it is possible to model the above relationship directly, it is not possible to tell whether it will improve or decrease the performance in the end, since one would have to add additional model structure. When using callbacks, the performance will very likely improve.
Best regards,
Jaromił0 -
Thanks Jaromił.
The main reason I was hoping to get around coding a callback is the issue referenced here: https://support.gurobi.com/hc/en-us/community/posts/360067079431-Callback-Setsolution-from-a-MIP-solution-node
I would have to compute my improved solution in a MIPSOL callback, however setting new solutions seems only to be supported in MIPNODE callbacks - at least that's what the documentation states.
Thanks a lot,
Lukas
0 -
Hi Lukas,
It is currently the only way to perform the changes you require. Just as you said, you can get and compute your solution in a MIPSOL callback and provide it in a MIPNODE callback to Gurobi.
The alternative way of formulating additional constraints is not an option in your case?
Best regards,
Jaromił0
Post is closed for comments.
Comments
6 comments