Opportunity for lazy cut
Ongoing
Hi,
I believe I've read the answer to this question before, but I don't remember where or what it was, my apologies.
Assume we have a problem with 3 variables, x,y,z, and constraints x<=y<=z. Lets pretend it is a good idea to add the constraints lazily, just for the sake of this question.
So we create the 3 variables, we register a callback, and then call solve. Say the first time our callback function is called, the current solution is:
x=3, y=2, z=1
We would now add the two cuts lazily:
x<=y, and y<=z
and the solver would be done.
My question is, if we must add both cuts, or if we could instead just add one, say
x<=y
and then wait for the next callback call to add the other one?
From my experiences it looks like we need to add both, because gurobi might not give us another opportunity to add the remaining cut (i.e. it might not call us again). I'm not sure why this is so, because gurobi could call always call us until it notices no further cuts were added. In my use case, it might be interesting to add just a subset of cuts.
Anyway, would just like to confirm this, and to ask if there is some flag or something that could allow me to be *really* lazy in this sense :)
Thanks!
Marco
-
Hi Marco,
There is a fundamental difference between (user) cuts and lazy constraints. This is explained here: What is the difference between user cuts and lazy constraints? Essentially, user cuts must never cut off feasible solutions, so there is no such thing as a "lazy cut".
That being said, I believe that it's OK not to add all lazy constraints, but it may happen that Gurobi will falsely claim optimality in that case. You need to check all solutions in the MIPSOL callback to avoid missing any violated lazy constraints that were not added before. Generally, I do not think this approach will help performance because Gurobi cannot make use of important information as early as when adding all violated lazy constraints immediately.
Cheers,
Matthias0 -
Hi Matthias,
Thanks for the clarification, indeed I am talking about lazy constraints here.
I am not sure I understood what you mean. If gurobi never gives me the chance to add the missing lazy constraint, how can it even declare feasibility (let alone optimality)?
0 -
Hi Matthias,
Not sure if you don't have anything else to add, or if this thread was forgotten. I don't think I understand how this works yet (see post above). Thanks
0
Please sign in to leave a comment.
Comments
3 comments