Setting an upper bound constraint to maximization objective (MIP)
AnsweredDear all,
I am working on a MIP-encoded maximization problem that takes a significant amount of time to solve. I have prior knowledge that the objective value is smaller than a certain upper bound "u".
To leverage this information, I added the constraint objective <= u
, expecting it to reduce the solving time. However, I observed that in some cases, this constraint actually increases the solving time. Interestingly, when I set the constraint to objective <= u + 10
, it does save time in some of the scenarios where objective <= u
added time, but it doesn't consistently reduce the solving time across all scenarios.
How I can set my original constraint (objective <= u
) in a way that consistently saves time?
-
Hi Neta,
It's almost certainly a bad idea. See the discussion here:
https://or.stackexchange.com/questions/419/feeding-known-lower-bounds-to-solvers- Riley
0 -
thank you for thw quick response.
Could you suggest another way I can leverage this prior knowledge?
0 -
Hi Neta,
If you have a known dual bound which is better than Gurobi's current dual bound then you can calculate a MIP gap yourself, which will be smaller, and it may enable you to terminate your solve earlier. You would do this with a callback. In Python:
YOUR_DUAL_BOUND = ...
def callback(model, where):
if where == GRB.Callback.MIPSOL:
objbst = model.cbGet(GRB.Callback.MIPSOL_OBJBST)
gap = abs(objbst - YOUR_DUAL_BOUND) / abs(objbst)
if gap < model.params.MIPGap:
model.terminate()
model = gp.Model()
# define model
model.optimize(callback)This won't improve the search in any way but it could help you save some time if you're termination criteria is based on the MIP Gap.
- Riley
0
Please sign in to leave a comment.
Comments
3 comments