Lack of progress in Best Bound past a certain point and no termination for MINLP
Answered
Hello Gurobi Team,
We have noticed in several MINLP instances that Gurobi is initially making good progress in terms of Best Bounds before settling at a value and stopping to improve. When this happens, the number of Unexplored Nodes is playing yoyo, but doesn't keep growing. This can happen in instances where an incumbent has been found or not, and we have good reasons to believe that the Best Bound isn't the optimal solution value.
I attach part of an output log and am happy to share the corresponding lp file. We would greatly appreciate if someone could point us in the right direction.
Best regards,
Benoit
Gurobi Interactive Shell (linux64), Version 11.0.1
Copyright (c) 2024, Gurobi Optimization, LLC
Type "help()" for help
gurobi> m=read("canon.lp")
Read LP format model from file canon.lp
Reading time = 0.01 seconds
: 1177 rows, 1533 columns, 8849 nonzeros
gurobi> m.optimize()
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (linux64 - "Ubuntu 22.04.4 LTS")
CPU model: 12th Gen Intel(R) Core(TM) i7-1260P, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 1177 rows, 1533 columns and 8849 nonzeros
Model fingerprint: 0x94b30730
Model has 38 quadratic constraints
Model has 10 general constraints
Variable types: 1323 continuous, 210 integer (182 binary)
Coefficient statistics:
Matrix range [6e-09, 3e+02]
QMatrix range [2e-01, 2e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e-07, 1e+03]
RHS range [1e-03, 2e+02]
QRHS range [1e+00, 8e+00]
Presolve removed 391 rows and 893 columns
Presolve time: 0.03s
Presolved: 1205 rows, 712 columns, 8497 nonzeros
Presolved model has 75 bilinear constraint(s)
Presolved model has 10 nonlinear constraint(s)
Solving non-convex MINLP
Variable types: 536 continuous, 176 integer (174 binary)
Root relaxation: objective 9.800000e-01, 525 iterations, 0.01 seconds (0.02 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.98000 0 47 - 0.98000 - - 0s
0 0 0.98000 0 39 - 0.98000 - - 0s
0 0 0.98000 0 37 - 0.98000 - - 0s
0 0 0.98000 0 51 - 0.98000 - - 0s
0 2 0.98000 0 51 - 0.98000 - - 0s
3730 2042 0.59842 34 4 - 0.98000 - 47.4 5s
6188 2724 0.98000 44 39 - 0.98000 - 53.4 10s
13589 3841 0.93282 42 60 - 0.98000 - 52.2 15s
18706 4961 0.72036 50 66 - 0.96507 - 51.5 21s
21866 5711 infeasible 57 - 0.94975 - 51.8 25s
28062 6796 infeasible 54 - 0.92686 - 50.5 30s
34743 8167 0.79313 55 82 - 0.90467 - 48.9 35s
37927 8652 infeasible 49 - 0.89276 - 48.7 40s
41736 9107 0.78411 43 54 - 0.88227 - 48.2 46s
43510 9233 infeasible 58 - 0.87934 - 47.9 50s
46225 9401 infeasible 50 - 0.86425 - 48.0 55s
50912 9690 0.79714 47 57 - 0.85520 - 47.4 62s
54575 10249 0.62096 75 74 - 0.83733 - 47.1 66s
58166 10711 0.55089 62 63 - 0.82992 - 46.7 70s
62528 11159 0.72568 49 69 - 0.82056 - 46.9 76s
63602 11273 infeasible 73 - 0.82056 - 47.0 82s
...
3081097 12617 0.34558 72 43 - 0.34565 - 43.1 3770s
3083984 12514 0.34504 72 69 - 0.34546 - 43.1 3775s
3089477 12597 0.34522 106 9 - 0.34528 - 43.1 3782s
3091767 12606 infeasible 84 - 0.34527 - 43.1 3786s
3094940 12784 infeasible 64 - 0.34511 - 43.2 3791s
3098226 13720 infeasible 133 - 0.34511 - 43.2 3796s
3100958 14258 0.34499 102 15 - 0.34511 - 43.2 3800s
3106960 15841 0.34511 205 4 - 0.34511 - 43.2 3806s
3113707 17811 infeasible 133 - 0.34511 - 43.2 3811s
3120546 19698 infeasible 307 - 0.34511 - 43.1 3816s
...
5847850 14479 infeasible 85168 - 0.34511 - 38.9 7082s
5849781 14949 infeasible 132 - 0.34511 - 38.9 7086s
5854091 15797 0.34511 121 2 - 0.34511 - 38.9 7090s
5858778 16461 infeasible 85168 - 0.34511 - 38.9 7095s
5867792 18074 infeasible 134 - 0.34511 - 38.9 7103s
5872009 18786 infeasible 145 - 0.34511 - 38.9 7107s
5875995 18969 infeasible 85270 - 0.34511 - 38.8 7112s
5878718 19678 infeasible 85772 - 0.34511 - 38.8 7116s
5882751 20348 infeasible 85722 - 0.34511 - 38.8 7120s
-
Hi Benoit,
I see you have already set the FuncNonlinear parameter to 1 to address nonlinear constraints using the dynamic outer-approximation approach.
The common parameters used to speed up the progress of the best bound include:
The log you attached indicates that the model might be infeasible. Proving infeasibility can be as hard as proving optimality.
- It wouldn't hurt if you look at solving the piecewise linear approximation of your model using the default value of the FuncNonlinear parameter (0). The solution quality might be acceptable to you.
- Another general recommendation when solving nonlinear problems is to define the tightest possible lower and upper bounds for the variables participating in nonlinear constraints.
- The model numerics does not look great. The linear constraints' coefficients span a range as wide as 11 orders of magnitude. Setting the ScaleFlag parameter to 2 is another idea that you can try.
Best regards,
Maliheh
0 -
Maliheh,
Many thanks for sharing your thoughts, much appreciated.
In response to your comments/suggestions:
- We did also look at solving our models with piecewise linear approximations of the nonlinear terms (FuncNonlinear=0) and the same behaviour is observed (no termination)
- It is true that a handful of constraints have coefficients that are very small in magnitude (1e-9), these are physical parameters in our models so hard to change. Increasing the NumericFocus value doesn't change the behaviour though.
- We can also confirm that this model is feasible - we can obtain feasible solutions by running a local solver prior to calling Gurobi (which Gurobi accept as incumbent when we pass them as guess). But the same behaviour remains for the Best Bound progress regardless.
Best regards,
Benoit0 -
Hi Benoit,
The MINLP feature is very fresh so there is still a lot of space for improvement.
Could you please share the model? Hopefully, we can find something to improve. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
If you cannot share the file in a public way, please open a ticket to share if this is acceptable.
Best regards,
Jaromił0 -
Hi Jarek,
Thanks for this. Here's a Dropbox link to the model (lp file): https://www.dropbox.com/scl/fi/k65es1agx04q2oqskeari/canon.lp?rlkey=4cggw637motn4f03l29hp7unh&dl=0
We can also confirm that this model is feasible, with an incumbent at 0.33403 (which we also believe to be the optimal solution value).
Best regards,
Benoit
0 -
Thank you for sharing Benoit.
The current version cannot find any feasible point to this issue. We are working on improving this for MINLPs in the next release. The dual bound is then another story, but without a feasible point, improving the dual bound (quickly) is difficult. I don't think that there is any parameter or workaround that would help in this case with v11. Maybe a combination of an external local solver for feasible points + Gurobi for the dual bound might work. Otherwise, I am afraid that the only way for now is to either wait for v12 or try a different solver.
If that's OK you could also share the feasible point you found. This should give a hint to what can be improved on the dual bound side.
Best regards,
Jaromił0 -
Hello again Jarek,
Many thanks for the heads-up. Here is a link to the MIP start file: https://www.dropbox.com/scl/fi/8rh21g2zqaqbt4zbjp8es/canon.mst?rlkey=3dpicay6mmyahfoulg49upzy2&dl=0
Please don't hesitate to be in touch with us.
Best,
Benoit0
Please sign in to leave a comment.
Comments
6 comments