Skip to main content

Tell Gurobi about optimal variable value depending on a set of other variables

Ongoing

Comments

5 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Lukas Barth
    Gurobi-versary
    First Question
    Conversationalist

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Lukas Barth
    Gurobi-versary
    First Question
    Conversationalist

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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

Please sign in to leave a comment.