User cuts for relxation
AnsweredHi,
I’m currently using Gurobi to solve a LP and have implemented several strong forcing constraints (valid inequalities). These constraints significantly improve the lower bound, especially at the root node, but I’ve noticed they can interfere with finding good incumbents.
Ideally, I’d like to apply these constraints only at the relaxations to tighten the bound, but not enforce them throughout the full incumbent search. I’ve attempted to implement this using user cuts, but my current approach doesn’t seem to have the desired effect.
Could somebody advise me on how best to proceed or point out pitfalls in my implementation?Thank you very much for your support.
Best regards,
Konstantin
-------
My implementation:
model.setParam("PreCrush", 1)
model.optimize(callback)
def callback(model, where):
if where == GRB.Callback.MIPNODE:
status = model.cbGet(GRB.Callback.MIPNODE_STATUS)
if status == GRB.OPTIMAL:
x = model.cbGetNodeRel(model._x_vars)
y = model.cbGetNodeRel(model._y_vars)
s = model.cbGetNodeRel(model._s_vars)
z = model.cbGetNodeRel(model._z_vars)
violated_cuts = get_violated_user_cuts(model, x, y, s, z)
for lhs, rhs in violated_cuts:
model.cbCut(lhs >= rhs)
def get_violated_user_cuts(model, x, y, s, z):
"""
Check for violations of strong forcing constraints in the LP relaxation solution
and return user cuts that can be added via cbCut().
"""
violated = []
eps = 1e-5 # small tolerance to avoid numerical noise
this = model._this # access to model data/structure
# 1. Freight capacity constraint: x[i,j,r] ≤ y[i,j] for r in R_f
for r in this.R_f:
for (i, j) in this.A_pt_v_r[r]:
x_val = x[i, j, r]
y_val = y[i, j]
if x_val - y_val > eps:
expr = model._x_vars[i, j, r] - model._y_vars[i, j]
violated.append((expr, 0))
return violated
-
-
Gurobi Staff
Hi Konstantin,
It might be that the PreCrush parameter is the cause, not the cuts. It would be interesting to hear how it runs if you set PreCrush=1 but not attempt to add cuts.
It could be worth trying to run two instances of Gurobi in parallel, the first using your cuts and the second not, and have the second one store solutions (either using SolFiles parameter or writing them in a callback) so that the first can read them and use cbSetSolution within a callback (such as MIP callback).
- Riley
0 -
-
Hi Riley,
Thank you for your response!
I followed your suggestion: I set PreCrush = 1 and didn’t add cuts. The results remained the same. Just to clarify: the valid inequalities are not modeled as explicit constraints, but instead detected and added dynamically within my get_violated_user_cuts function during the MIPNODE callback. Is this the intended behavior?
Furthermore, your suggestion on using multiprocessing might be promising. Based on the documentation, would you agree that the following parameters are a reasonable starting point to focus on improving LBs in the first Gurobi instance (I would model all valid inequalities explicitly in the model)?
model.setParam("Cuts", 2) # Use aggressive cuts
model.setParam("Presolve", 2) # Aggressive presolve to tighten the model
model.setParam("Heuristics", 0) # Turn off heuristics
model.setParam("MIPFocus", 3) # Focus on improving the bound
model.setParam("NodeLimit", 1) # Only solve the root node (no branching)Thanks again and best regards,
Konstantin0 -
-
-
Hi Konstantin,
Without experimental evidence to back up the choice of parameter setting (see How can I make accurate comparisons?) I'd set MIPFocus=3, maybe Presolve=2.
Cuts are already aggressive with MIPFocus=3, so no need to touch that. Heuristics=0 is extreme. We tend to only suggest this for models that can be solved in a few tenths of seconds by branching. I would also leave it at it's default (plus improvement heuristics will be able to act on your heuristic solutions to possibly find improvements).
Note that NodeLimit=1 will not prolong activity at the node. It only causes the solve to terminate when it would otherwise branch (I'm not sure if this is what you wanted).
- Riley
0 -
-
Hi Riley,
thank you for your advice. The gurobi logtools also look very useful.
I'll try and work with that.Best regards,
Konstantin0 -
-
-
You're welcome. Gurobi-logtools will have a new major release soon. In the meantime it is probably worth installing directly from the repository to get the numerous updates since the last release:
pip install git+https://github.com/Gurobi/gurobi-logtools0 -
-
Hi Riley,
Thank you again for your helpful advice.
I just wanted to share a quick update regarding my original query on user cuts. In the end, I didn’t implement a callback. Instead, I used the constraint attribute Lazy = -1 directly in the model formulation. This approach gave me the desired behavior.
I hope this helps other Gurobi users in the future.
Best regards,
Konstantin0 -
Please sign in to leave a comment.
Comments
6 comments