Adding lazy constraints in "where == gp.GRB.Callback.MIPNODE".
Answered
Hi,
I am currently trying to solve a routing problem formulated as a MIQP using a callback function to add valid inequalities representing something like subtour elimination.
In my understanding, subtour elimination constraints are required for the validity of a solution, so I should use "cbLazy", not "cbCut".
Also, they should be added to improve the LP relaxation obtained at each node of the branch-and-bound tree. So, I'd like to add lazy constraints not only if "where == gp.GRB.Callback.MIPSOL" but also "where == gp.GRB.Callback.MIPNODE".
Based on this consideration, I defined the callback function below:
def valid_ineqs(model: gp.Model, where):
if where == gp.GRB.Callback.MIPNODE:
status = model.cbGet(gp.GRB.Callback.MIPNODE_STATUS)
if status == gp.GRB.OPTIMAL:
xR = model.cbGetNodeRel(model._vars)
for u in U_plus:
# Here, solve the max-flow problem and obtain a set S.
if min_cut < 1:
model.cbLazy(gp.quicksum(model._vars[i * 2 * n + j] for j in S for i in S) <= len(S) - (n_d + 1))
if where == gp.GRB.Callback.MIPSOL:
xR = model.cbGetSolution(model._vars).tolist()
for u in U_plus:
# Here, solve the max-flow problem and obtain a set S.
if min_cut < 1:
model.cbLazy(gp.quicksum(model._vars[i * 2 * n + j] for j in S for i in S) <= len(S) - (n_d + 1))
When I solve the problem using this function with an initial solution x0 as MIP.Start, the solver finally outputs x0 as the optimal solution with 0.0000% optimality gap as follows:
Academic license - for non-commercial use only - expires 2025-04-04
Warning for adding constraints: zero or small (< 1e-13) coefficients, ignored
Set parameter LazyConstraints to value 1
Set parameter Presolve to value 2
Set parameter MIPFocus to value 1
Set parameter PreCrush to value 1
Set parameter PreSparsify to value 2
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[x86] - Darwin 24.3.0 24D70)
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 23964 rows, 7920 columns and 83571 nonzeros
Model fingerprint: 0x3ea0fbf8
Model has 11187786 quadratic objective terms
Variable types: 176 continuous, 7744 integer (7744 binary)
Coefficient statistics:
Matrix range [2e-05, 3e+02]
Objective range [1e-23, 4e+01]
QObjective range [1e-13, 2e+00]
Bounds range [1e+00, 3e+02]
RHS range [2e-15, 3e+02]
Warning: Model contains large quadratic objective coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 39s
User MIP start produced solution with objective 1881.61 (39.21s)
Loaded user MIP start with objective 1881.61
Processed MIP start in 39.37 seconds (62.03 work units)
Presolve removed 3101 rows and 464 columns (presolve time = 5s) ...
Presolve removed 3101 rows and 3410 columns (presolve time = 27s) ...
Sparsify removed 137091 nonzeros (70%)
Presolve removed 15980 rows and 9461 columns (presolve time = 66s) ...
Presolve removed 15980 rows and 3063 columns
Presolve time: 66.15s
Presolved: 7984 rows, 4857 columns, 58037 nonzeros
Presolved model has 3668139 quadratic objective terms
Variable types: 336 continuous, 4521 integer (4447 binary)
Root relaxation presolved: 7983 rows, 4857 columns, 58018 nonzeros
Root relaxation presolved model has 3668139 quadratic objective terms
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.3485011e+03 0.000000e+00 0.000000e+00 123s
28210 1.5132101e+03 0.000000e+00 0.000000e+00 125s
28210 1.5132101e+03 0.000000e+00 0.000000e+00 125s
Root relaxation: objective 1.513210e+03, 28210 iterations, 4.09 seconds (3.57 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1513.21008 0 257 1881.60585 1513.21008 19.6% - 124s
0 0 1513.21008 0 257 1881.60585 1513.21008 19.6% - 125s
0 0 1513.28892 0 224 1881.60585 1513.28892 19.6% - 136s
0 0 1543.76393 0 369 1881.60585 1543.76393 18.0% - 152s
0 0 1543.77688 0 341 1881.60585 1543.77688 18.0% - 190s
0 0 1543.77688 0 324 1881.60585 1543.77688 18.0% - 220s
0 0 infeasible 0 1881.60585 1881.60585 0.00% - 259s
Cutting planes:
Gomory: 2
Implied bound: 4
Clique: 2
MIR: 93
Zero half: 9
RLT: 2
Relax-and-lift: 3
Lazy constraints: 156
Explored 1 nodes (164132 simplex iterations) in 259.25 seconds (211.19 work units)
Thread count was 12 (of 12 available processors)
Solution count 1: 1881.61
Optimal solution found (tolerance 1.00e-04)
Best objective 1.881605847380e+03, best bound 1.881605847380e+03, gap 0.0000%
User-callback calls 2888, time in user-callback 93.02 sec
However, when I provide another solution x1, which is better than x0, as a variable hint, the same program returns x1 as the optimal solution with 0.0000% gap as follows (I illustrate only the different part from the above log).
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1513.21008 0 257 1881.60585 1513.21008 19.6% - 124s
0 0 1513.21008 0 257 1881.60585 1513.21008 19.6% - 125s
H 0 0 1875.4731257 1513.21008 19.3% - 125s
0 0 1513.28892 0 198 1875.47313 1513.28892 19.3% - 137s
0 0 1543.76393 0 335 1875.47313 1543.76393 17.7% - 145s
0 0 1543.76393 0 327 1875.47313 1543.76393 17.7% - 170s
0 0 1546.31318 0 343 1875.47313 1546.31318 17.6% - 218s
0 0 1546.35680 0 342 1875.47313 1546.35680 17.5% - 264s
0 0 1546.35680 0 328 1875.47313 1546.35680 17.5% - 303s
0 0 1550.05664 0 364 1875.47313 1550.05664 17.4% - 361s
0 0 1550.05664 0 395 1875.47313 1550.05664 17.4% - 408s
0 0 1550.78013 0 407 1875.47313 1550.78013 17.3% - 462s
0 2 1550.78013 0 367 1875.47313 1550.78013 17.3% - 586s
1 4 1558.20861 1 390 1875.47313 1550.78013 17.3% 35141 626s
3 8 1566.53989 2 411 1875.47313 1558.79908 16.9% 33153 772s
6 8 1580.40851 2 373 1875.47313 1566.53989 16.5% 37321 897s
7 2 infeasible 3 1875.47313 1567.20903 16.4% 34653 911s
13 0 infeasible 3 1875.47313 1581.44442 15.7% 26421 916s
Cutting planes:
Gomory: 3
Implied bound: 11
Clique: 5
MIR: 130
Zero half: 3
RLT: 5
Relax-and-lift: 4
Lazy constraints: 509
Explored 15 nodes (533805 simplex iterations) in 917.02 seconds (368.52 work units)
Thread count was 12 (of 12 available processors)
Solution count 2: 1875.47 1881.61
Optimal solution found (tolerance 1.00e-04)
Best objective 1.875473125741e+03, best bound 1.875473125741e+03, gap 0.0000%
User-callback calls 30747, time in user-callback 622.89 sec
This behaviour is confusing because the first log means that there are no better feasible solutions than x0 but the second log means that x1 is a better feasible solution than x0 for the same problem.
I found the previous Q&A implying that MIPNODE is primarily for adding "cuts" rather than "lazy constraints". Based on this, I attempted to change "cbLazy" to "cbCut" in "if where == gp.GRB.Callback.MIPNODE", but the result was almost the same.
Also, when I remove the entire MIPNODE-related section, it worked well. But the computation time was much longer than I expected. Therefore, I'd like to remain the MIPNODE part if the above error is due to my mistakes in coding or my misunderstanding for the callback function.
I would greatly appreciate it if you could point out which part of my code might be wrong and how to improve it.
Thank you
Thank you
Mats
1
-
-
Gurobi Staff
Hi Sorachi,
The type of result you're seeing tends to occur when the model is causing numerical issues for the solver.
The logfile is explicitly warning you of this and suggesting actions to take:
Warning: Model contains large quadratic objective coefficient range Consider reformulating model or setting NumericFocus parameter to avoid numerical issues.
We have a section of our reference manual which will be beneficial: Guidelines for numerical issues.
In particular, you may need to appeal to Advanced user scaling
We also have a webinar recording which covers these topics: Mastering numerical challenges
- Riley
0 -
Please sign in to leave a comment.
Comments
1 comment