A sharp drop in 'BestBd'

Dear Developers,

I am an academic license user of Gurobi, using it within a Python environment to solve mathematical programming problems in the field of engineering. My model is a MIQCP (Mixed-Integer Quadratically Constrained Programming) model, which involves integer variables and products of variables—this is necessary due to the ore grade calculations involved, and I believe such formulations are unavoidable in Gurobi.

Currently, I’m facing an issue during the solving process where the BestBd value suddenly drops sharply. This drop results in a solution that is clearly suboptimal. Based on my manual calculations, I know that if the solver had continued from the BestBd value before the drop, it would have been able to find a much better solution within the preset gap and time limit.

I’ve attached part of the log below, and this sharp drop occurs between nodes 1106 and 1189. I’ve tried outputting all constraints and comparing the changes between these nodes to identify what might have caused this behavior. However, due to the large number of constraints, I haven’t been able to pinpoint the issue.

I would greatly appreciate your help with the following:

Could you please explain why such a sharp drop in BestBd might occur? A deep explanation would be very helpful—I believe I can understand the technical details.
Is there a more efficient and accurate method to identify which specific constraint changes might have led to this drop?

Thank you again for your support.

Optimize a model with 25630 rows, 7490 columns and 325097 nonzeros
Model fingerprint: 0x8c08d9e0
Model has 470 quadratic constraints
Model has 9600 simple general constraints
9600 INDICATOR
Variable types: 5880 continuous, 1610 integer (1610 binary)
Coefficient statistics:
Matrix range [1e-01, 4e+04]
QMatrix range [3e-01, 3e+01]
QLMatrix range [1e+00, 5e+01]
Objective range [4e-01, 9e-01]
Bounds range [1e+00, 9e+10]
RHS range [2e+00, 4e+04]
GenCon coe range [1e+00, 1e+00]
Warning: Model contains large bounds
Presolve removed 20798 rows and 1264 columns
Presolve time: 0.67s
Presolved: 6590 rows, 6398 columns, 30445 nonzeros
Presolved model has 3888 SOS constraint(s)
Presolved model has 399 bilinear constraint(s)

Solving non-convex MIQCP

Variable types: 5038 continuous, 1360 integer (1360 binary)
Root relaxation presolved: 5565 rows, 5818 columns, 28243 nonzeros

Root relaxation: objective 2.125741e+08, 10677 iterations, 2.68 seconds (1.38 work units)

0 0 2.1257e+08 0 637 - 2.1257e+08 - - 3s
0 2 2.1257e+08 0 632 - 2.1257e+08 - - 5s
63 62 2.0810e+08 11 799 - 2.1173e+08 - 145 10s
200 180 2.0805e+08 25 760 - 2.1173e+08 - 138 15s
428 374 2.0398e+08 55 531 - 2.1167e+08 - 115 20s
667 565 1.9985e+08 88 452 - 2.1167e+08 - 106 25s
747 647 1.9788e+08 99 265 - 2.1167e+08 - 110 31s
H 778 647 1.119309e+08 2.1167e+08 89.1% 111 31s
H 781 647 1.123818e+08 2.1167e+08 88.4% 110 31s
H 810 677 1.123818e+08 2.1167e+08 88.4% 108 33s
H 846 729 1.164484e+08 2.1167e+08 81.8% 106 34s
H 849 729 1.166902e+08 2.1167e+08 81.4% 106 34s
883 789 1.9530e+08 131 136 1.1669e+08 2.1167e+08 81.4% 105 35s
H 979 856 1.166902e+08 2.1167e+08 81.4% 99.0 37s
1106 1010 1.2148e+08 176 119 1.1669e+08 2.1167e+08 81.4% 95.8 40s
1189 707 1.4004e+08 56 32 1.1669e+08 1.4004e+08 20.0% 92.2 46s
1193 497 1.4004e+08 24 32 1.1669e+08 1.4004e+08 20.0% 101 59s

H 0 0 46569.539671 66639.6464 43.1% - 0s 0 2 66639.6464 0 41 46569.5397 66639.6464 43.1% - 0s H 31 49 46569.539671 57054.7777 22.5% 12.3 0s H 112 101 48002.680167 57054.7777 18.9% 6.1 0s

H 247 221 49162.398813 57041.2572 16.0% 7.9 0s H 398 361 50034.265316 57041.2572 14.0% 6.1 0s H 400 405 50206.350489 57041.2572 13.6% 6.0 0s H 1268 194 50206.350489 50416.4502 0.42% 4.1 1s

Jaromił Najman

Gurobi Staff

2025年07月07日 15:14

Hi Junlin Qu,

Could you please explain why such a sharp drop in BestBd might occur? A deep explanation would be very helpful—I believe I can understand the technical details.

It is possible that a global cut could be computed which leads to prunning a whole subtree. It is also possible that the new incumbent information could have been used to perform some dual argument and again prune a whole subtree leading to a sharp drop in the dual bound.

Are you able to generate a feasible point for your model which would lead to a solution with an objective value which is better than the reported dual bound? If yes, could you please try generating such feasible point and providing it to Gurobi as a MIPStart, see How do I use MIP start? If the dual bound you show in your post strictly cuts off the newly generated feasible point, then please share the model such that we can investigate what is going wrong.

Is there a more efficient and accurate method to identify which specific constraint changes might have led to this drop?

Unfortunately not. Such drops are not unusual but finding the exact reason for them would require to have a closer look at the code during the solution process which is not possible.

Best regards,
Jaromił

2025年07月10日 06:29

Thank you for sharing the code, Junlin.

You said that the sudden drop in the best bd is unexpected, because there should be a solution which is better than the one reported by Gurobi. Are you able to generate one such solution?

Regarding the output here are possible explanations for the sudden drop in BestBd

Here, the solver just stopped its work in the root node. You can see this by the increase in the number of unexplored nodes (2nd column). For nonconvex models, branching can very quickly improve the BestBd which seems to be the case here. You can see that in the 3 line the solver explored 31 nodes very quickly. Each such node exploration consists of branching, bound propagation, and other presolve routines which can quickly improve the BestBd. This is especially true if the variable bounds are very wide in the original model and the solver can prune big parts of the original domain.

The second drop most likely happens, because a new feasible solution has been found. Feasible solutions can be used to perform OBBT and other dual reductions which can significantly move the Best Bd. These reductions usually try to perform the following reduction: Try to cut off as much of the feasible space as possible without cutting off the current best feasible point and any point possibly better than it.

I hope this helps.

A sharp drop in 'BestBd'

コメント

お探しのものを見つけられませんでしたか？