Non-convex MINLP
回答済みDear Gurobi Support Team,
I am solving two nonlinear MINLPs using NonConvex = 2 in the Python interface, and I would like clarification on global optimality guarantees.
Model A:
Constraints contain log terms plus fractional expressions of decision variables (e.g., log(a+x/b)+(c+e*x)/(d-f*y), x and y are binary decision variables). Gurobi runs spatial branch-and-bound and returns a solution with a zero gap. Does this certify a true global optimum for this class of nonlinearities?
Model B:
Constraints contain log terms multiplied by fractional expressions (e.g., (log(a+x/b))*(c+e*x)/(d-f*y), x and y are binary decision variables). In this case, Gurobi cannot find an incumbent.
Does this mean the model is outside the class for which Gurobi can guarantee a global optimum, or is this simply numerical difficulty?
More generally, could you please clarify: For which combinations of nonlinear functions does Gurobi provide valid global bounds (and thus a certified global optimum) in nonconvex MINLP?
Thank you very much.
-
-
Gurobi Staff
Hi Ruibing,
Model A:
Constraints contain log terms plus fractional expressions of decision variables (e.g., log(a+x/b)+(c+e*x)/(d-f*y), x and y are binary decision variables). Gurobi runs spatial branch-and-bound and returns a solution with a zero gap. Does this certify a true global optimum for this class of nonlinearities?
Yes.
Model B:
Constraints contain log terms multiplied by fractional expressions (e.g., (log(a+x/b))*(c+e*x)/(d-f*y), x and y are binary decision variables). In this case, Gurobi cannot find an incumbent.
Does this mean the model is outside the class for which Gurobi can guarantee a global optimum, or is this simply numerical difficulty?Gurobi will try to find and prove a globally optimal solution for your model. The difference between models A and B is that model B is even more difficult than model A due to the additional multiplication term. Thus, finding a feasible solution is more difficult for model B than for model A or model B might even be infeasible. Note that proving infeasibility is as difficult as finding a globally optimal solution.
More generally, could you please clarify: For which combinations of nonlinear functions does Gurobi provide valid global bounds (and thus a certified global optimum) in nonconvex MINLP?
For a complete list of available nonlinear functions please refer to the documentation of nonlinear constraints.
For your particular expression, you should make sure that the terms in the denominators \(b\) and \(d - f*y\) do not cross \(0\) to avoid forcing Gurobi into handling the points of singularity.
If not already done, you should upgrade to the latest Gurobi version 13.
If you are using Python and Gurobi version ≥ 12, then you can use the addGenConstrNL method to conveniently add a nonlinear constraints via an NLExpr object. For your particular expression this would look something like
from gurobipy import nlfunc from gurobipy import GRB ... x = model.addVar(...) y = model.addVar(...) resvar = model.addVar(lb=-GRB.INFINITY) # a,b,c,d,e,f are constant parameters # add constraint # resvar = log(a+x/b)+(c+e*x)/(d-f*y) nlconstr = model.addGenConstrNL( resvar, nlfunc.log(a + x/b) + (c + e*x)/(d - f*y), "constraintname" )Best regards,
Jaromił0 -
-
Thank you. I tried Model B with Gurobi by avoiding zero denominators and get a solution from Gurobi. Gurobi output is below. I am writing to ask if the solution is a valid global optimal solution. Thank you very much.
Gurobi 12.0.3: qp:nonconvex = 2mip:focus = 1
lim:time = 10800
mip:heurfrac = 0.10000000000000001
Set parameter LogToConsole to value 1
tech:outlev = 1
AMPL MP initial flat model has 280 variables (0 integer, 210 binary);
Objectives: 1 linear;
Constraints: 740 linear; 75 quadratic;
Algebraic expressions: 45 div; 25 log;
Set parameter InfUnbdInfo to value 1
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (mac64[arm] - Darwin 24.5.0 24F74)
CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Non-default parameters:
TimeLimit 10800
Heuristics 0.1
MIPFocus 1
InfUnbdInfo 1
NonConvex 2
Solving non-convex MINLP
Variable types: 1271 continuous, 360 integer (360 binary)
Root relaxation: objective 3.772828e+00, 811 iterations, 0.02 seconds (0.01 work units)
Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (8.6278e-05) exceeds tolerance
Warning: max general constraint violation (8.6278e-05) exceeds tolerance
Best objective 3.587305102145e+00, best bound 3.587305102145e+00, gap 0.0000%
Gurobi 12.0.3: optimal solution; objective 3.587305102
1.19975e+06 simplex iterations
21590 branching nodes
AMPL param s at solve = 1.0
Final time= 39.023662090301514
0 -
-
Also, after I added a constraint to the model, the objective from Gurobi increases. Does this mean the solution from Gurobi is not global optimal?
0 -
-
-
I tried Model B with Gurobi by avoiding zero denominators and get a solution from Gurobi. Gurobi output is below. I am writing to ask if the solution is a valid global optimal solution. Thank you very much.
The solution found by Gurobi is proven to be a global solution. You can see that the optimal solution has some violations.
Warning: max constraint violation (8.6278e-05) exceeds tolerance
Warning: max general constraint violation (8.6278e-05) exceeds tolerance
I recommend to upgrade to Gurobi v13. If this is not enough. I would recommend to set the FeasibilityTol parameter to a slightly tighter value, maybe 1e-7 or at most 1e-8.
Does this mean the solution from Gurobi is not global optimal?
No, this means that the constraint you added cuts off the previous optimal solution. This means that the previously found globally optimal solution was not feasible for the new constraint you added.
Best regards,
Jaromił0 -
-
Thanks. I still do not fully understand your answer to my second question, so let me clarify what confuses me. My objective is to maximize revenue. After I added an additional constraint to Model B, the objective value reported by Gurobi actually became larger than before. This seems counter-intuitive, because adding a constraint should shrink the feasible region, so the optimal objective value should either stay the same or become smaller, but never increase.
If, as you mentioned, the new constraint cuts off the previously optimal solution, then the new optimal solution should still be feasible when the constraint is removed, which would imply that the previous solution was not truly optimal.
0 -
-
-
I still do not fully understand your answer to my second question, so let me clarify what confuses me. My objective is to maximize revenue. After I added an additional constraint to Model B, the objective value reported by Gurobi actually became larger than before.
Sorry, I did not notice that you are maximizing. This sounds like either a bug or a numerical issue. Could you please try upgrading to v13? If the issue still persists, could you please share the two models such that we can have a closer look? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
When using AMPL, you can let Gurobi write out the MPS file it gets from AMPL via
option solver gurobi; option gurobi_auxfiles rc; option gurobi_options 'timelimit=0 resultfile=myModel.mps'; solve;0 -
-
Thanks. I have upgraded to v13. I compared the solution of Model B with the additional constraint obtained via v12 and v13. For v12 and v13, my solver setting is:
ampl.setOption('solver', 'gurobi')ampl.setOption('show_stats', '1')
gurobi_opts = (
f"nonconvex=2 mipfocus=1 timelim={maxTime} "
"heurfrac=0.1 feastol=1e-8 outlev=1"
)
ampl.setOption('gurobi_options', gurobi_opts)
ampl.setOption('solver_msg', 1)
ampl.setOption('log_file', 'ampl_gurobi.log')
ampl.setOption('presolve', 10)
The result via v12 is:
Optimal solution found (tolerance 1.00e-04)Best objective 3.527523896100e+00, best bound 3.527523896100e+00, gap 0.0000%
Gurobi 12.0.3: optimal solution; objective 3.527523896
1.1568e+06 simplex iterations
18981 branching nodes
Final time= 22.558402061462402
The best set has 3.0 products.
The result via v13 is:
Optimal solution found (tolerance 1.00e-04)Best objective 3.072248647926e+00, best bound 3.072248647926e+00, gap 0.0000%
Gurobi 13.0.0: optimal solution; objective 3.072248648
981895 simplex iterations
5016 branching nodes
Final time= 28.495532989501953
The best set has 6.0 products.
I noticed the objective from v13 is worse than that from v12. Which solution should I trust? Which is trully global optimal? I also tried Model B without the additional constraint by v13. Unfortunately, v13 cannot find an incumbent but v12 gave a solution as I mentioned in our previous communication. So, which should I trust?Many thanks and look forward to your reply.
0 -
-
-
Which solution should I trust? Which is trully global optimal?
It is hard to say without the model at hand. It might be a bug in v13, a bug in v12, or even a bug in AMPL.
Could you please extract the model file and share it as described in my previous comment?
0 -
-
Sure. Here is the model file: conic_model.mps. Thank you again.
0 -
-
-
Hi Ruibing,
Thank you for sharing. This is very helpful. I see something that might be problematic for a nonlinear solver.
You have terms of the form
log(y / (constant + sum a_i x_i ))where \(y\) and \(x_i\) are optimization variables and \(a_i\) are some constants. The issue with this formulation is that with the variable bounds, the constant term, and \(a_i\) you provide, the denominator
(constant + sum a_i x_i )can cross \(0\) in some cases. For some terms the denominator looks like this
(positive constant + (-1 * continuous var) + sum positive_constant_i binary_var_i)Now if all binary variables are \(0\) and the continuous variable is greater than the positive constant, then the above term can be negative, but if some of the binaries are \(1\) then the term can be positive.
This has two bad effects. One is that the division operation has to handle the singularity at \(0\), which is already bad, but should be handled correctly in v13, but could have bad side effects on branching and construction of relaxation. The second one is that the \(\log\) term could theoretically get negative arguments. This again should be handled correctly. Note that at an optimal solution, these issues would not be present. However, for a global solver like Gurobi, it is best (and sometimes) necessary to make sure to avoid singularities. Dealing with singularities may lead to unexpected numerical behavior. We will investigate what is happening on this particular model and will try to improve with upcoming versions.
What you could try in the meantime is the following formulation. Introduce a new continuous variable \(\texttt{new_var}\) and then formulate the logarithm aslog(y / new_var) new_var = constant + sum a_i x_i (= your denominator) new_var >= some small constant, e.g., 1e-4As far as I can tell, in your formulation the \(y\) variable is already \(> 0\) so there is not need to touch it.
Additionally, you might want to tighten the FeasibilityTol parameter to 1e-9. The reason for this is that in your model you have multiple RHS with a value lower than the feasibility tolerance, which may lead to numerical trouble.
Could you please try the reformulation and let me know whether this improved the behavior? Could you then also please share the newly formulated model?
Best regards,
Jaromił0 -
-
Hi Jaromił,
Many thanks for your help! Here is the newly reformulated model conic_model2.mps. I applied your suggestion and reformulated the denominators. Since I upgraded to Gurobi v13, I only have results from v13:Optimal solution found (tolerance 1.00e-04)
Best objective 3.207969608579e+00, best bound 3.207969608579e+00, gap 0.0000%.
Do you still have access to Gurobi v12? If so, could you please run this new model on v12 and share the results with me?
I have two follow-up questions:
1. How can I determine whether a Gurobi solution is truly globally optimal? If the reported gap is 0.0000%, is that sufficient, or should I check additional indicators?2. Are there any recommended parameter settings to speed up Gurobi when solving non-convex MINLPs like mine?
Look forward to your reply and best regards,Ruibing
0 -
-
-
Hi Ruibing,
Thank you for sharing the reformulated model. It behaves way better. However, I am afraid that there is a bug or numerically troublesome behavior showing up on this model. I will need to investigate and I will inform you as soon as I know more.
Do you still have access to Gurobi v12? If so, could you please run this new model on v12 and share the results with me?
Yes, I tried v12 and it behaves the same as v13. Gurobi converges with different globally optimal solution depending on the value of the Seed parameter. This is an indicator of either a bug or a severe numerical issue. For you particular model, I would wait until we understood what is going on and why it behaves so strange.
1. How can I determine whether a Gurobi solution is truly globally optimal? If the reported gap is 0.0000%, is that sufficient, or should I check additional indicators?
Checking the reported MIPGap is sufficient. The only exceptions are numerically troublesome models or models containing singularities and undefined domains as was the case in the first version of your model.
2. Are there any recommended parameter settings to speed up Gurobi when solving non-convex MINLPs like mine?
Right now there are only very few parameters which affect MINLPs.
While we investigate what is going on with the model, I have another recommendation which should improve Gurobi's behavior on this model. Gurobi's nonlinear global algorithm depends on computation of valid and finite variable bounds for all variables participating in nonlinear terms. While Gurobi is most often able to compute good finite bounds for all variables of interest, there are still cases where it is not possible. You could try providing tight finite lower and upper bounds for all variables participating in nonlinear terms. For example, you correctly introduced the new variables for the denominator \(\texttt{Dup[X]____}\) with lower bounds \(0.0001\). You could additionally provide a finite upper bound of let's say \(10\) or \(100\). I am guessing the numbers here, but looking at the model an upper bound of \(10\) should be OK.
Other variables for which providing finite lower and upper bounds would be \(\texttt{regretUpperBound[X]__Y_____ }\) variables as they are part of the numerators in division terms.
One particular example that I found in the model is the division
(regretLowerBound[4]__50_____ / regretLowerBound[4]__52_____) regretLowerBound[4]__50_____ free -53.86211197230557 <= regretLowerBound[4]__52_____ <= 119.6060976470262So here, there is still a possible division by \(0\). Note that Gurobi can handle this situation, but introducing singularities like this can lead to bogus numerical behavior. There are more such divisions in the model, which need to be handled.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Many thanks for pointing out the strange behavior! The model that I sent you yesterday (conic_model2) corresponds to one case – let’s call it the ru case. I I also have another model, conic_modelo.mps, for a different case (the ro case), which should be easier than conic_model2.
Could you please try the second model with both v12 and v13 and let me know whether the results are the same? In addition, could you check whether Gurobi still converges to different globally optimal solutions when you change the Seed parameter?
Thank you again and best regards,Ruibing
0 -
-
-
Hi Ruibing,
The latest model you provided (the ro case) behaves well, both with version 12 and 13 (I would recommend sticking with v13 to profit from latest bug fixes and performance improvements). I don't see any possible numerical issues arising from wrong domain definitions or divisions by 0. I tested both versions over 5 seeds and all runs proved the same global optimum.
If you can formulate your other models in that style, then you shouldn't encounter any issues with numerics.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Many thanks! Unfortunately, I am not able to reformulate the other model in the same way as in the ro case. I therefore re-checked the ru model carefully and revised all potential zero-denominator issues.
Please find the updated model here: conic_modelu.mps. Could you kindly try running it again using Gurobi v12 and v13, and also test different seeds?
Thanks again and best regards,Ruibing
0 -
-
-
Hi Ruibing,
The latest ru model you provided also behaves well, both with version 12 and 13. Again I would recommend sticking with v13. Again, I tested both versions over 5 seeds and all runs proved the same global optimum.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Many thanks! However, when I did a sensitivity analysis under the ru model, I found that for some instances, the “gloabl” optimum is still different for different seeds. Here are the results for three seeds:
- seed=1: conic_modeluru1.mps
- seed=10: conic_modeluru2.mps
- seed=100: conic_modeluru3.mps
For example, if ru=15, the objective is 1.24541813241797 when seed=100 but is 1.31489769138979 when seed=10.
I also tried ro model again and found the optimal objective is different for seed=1 and seed=10. Please see them below:
- seed=1: conic_modelo1.mps
- seed=10: conic_modelo10.mps
Do you know how this problem could be resolved? By the way, is it correct to set seed in this way?
gurobi_opts = ( f"nonconvex=2 mipfocus=2 timelim={maxTime} " "heurfrac=0 feastol=1e-6 seed=10 threads=1 outlev=1 " f"LogFile={gurobi_log_path} " "resultfile=conic_modeluru5.mps" )Thank you again and look forward to your reply.
Best regards,
Ruibing
0 -
-
-
Hi Ruibing,
Jaromił is on leave for a couple of weeks, so you may not hear from him until next year.
Here are the results for three seeds:
- seed=1: conic_modeluru1.mps
- seed=10: conic_modeluru2.mps
- seed=100: conic_modeluru3.mps
Note that model files only contain the model definition, and not parameters, so these files are all the same.
By the way, is it correct to set seed in this way?
This looks correct. You should be able to verify the parameter changes via the log file, in the “Non-default parameters” section. For example in the log for seed 10 you should see
Non-default parameters: ... Seed 10 ...Do you know how this problem could be resolved?
I've attempted to find a resolution through parameters, but my experiments with solver parameters to manage numerical issues have not been able to produce a consistent result, and I expect we are fighting against the limits of floating point arithmetic here.
- Riley
0 -
-
Hi Riley,
Thanks. If the solution quite depends on seeds, does it mean the global optimum is not trustworthy?
Best,
Ruibing
0 -
-
-
Hi Ruibing,
Yes I would not trust the result from a single run. But like many things in life you could build trust through repetition, i.e. solve with many seeds then inspect the quality of solutions to see if there is one with low violations and a good objective value compared to the rest.
- Riley
0 -
-
-
Hi Ruibing,
In addition to what Riley already stated, we are looking at the latest model you provided and trying to understand why Gurobi reports a different global optimum depending on the seed.
I will keep you up to date on this issue. However, please be aware that it may take some time to be resolved.
Best regards,
Jaromił0 -
-
Hi Jaromił,
Thank you very much! I have reformulated the model, which is non-convex MINLP, and it works well in Gurobi. Now, I convexified the model and obtained a convex mixed integer version. Hwever, when I ran it with Gurobi, Gurobi said it is non convex. I asked Chatgpt and Chatgpt said it is because Gurobi thought bilinear terms are non-convex. Is it true? Here is the model: dbg.lp ; dbg.mps .
I also tried another model with bilinear terms. Gurobi did not say it is convex or not. dbg2.mps
Look forward to your reply.Thanks and best regards,
Ruibing
0 -
-
-
Hi Ruibing,
as of version 13, the convexity recognition of Gurobi for nonlinear terms is very weak. Thus, despite that your model is clearly convex, Gurobi reports that it is non-convex. We are working to improve this behavior in upcoming versions.
Best regards,
Jaromił0 -
-
-
Hi Ruibing,
I apologize for not coming back to you for so long.
We figured out that the issue is numerical. Due to feasibility and optimality tolerances, it may happen that some node relaxation may be declared feasible or not. This then may lead to Gurobi cutting off the optimal solution for some seeds.
To avoid this behavior you should set FeasibilityTol=1e-9 and OptimalityTol=1e-9. This should be enough to make sure that node relaxation solves are performed with enough caution to not cut off the globally optimal solution on your conic_modeluru model.
Best regards,
Jaromił0 -
サインインしてコメントを残してください。
コメント
24件のコメント