Extra variables being generate during solution process and IntInf has way higher value than the number of integer constraints I have in the model.
Answered
I have a MIQP model with 1074 continuous and 1072 binary variables. I had already successfully tested the model with 43 continuous and 40 binary variables before. But now in the scaled up model, I am having a lot of issues. Not a single feasible solution is found even after running for 2 days non-stop. Surprisingly, when I set the Obj to 0, I get a solution within 40 seconds but with the non-convex quadratic obj function, the model just can not be solved. I see that a lot of extra variables are added. 1074 continuous variables become 142k+ continuous variables and IntInf log starts with 65k+ even though total number of binary variables are just 1072. 
-
The number of Integer Infeasibilities also reflects the number of violated bilinear terms in the associated linear relaxation. You have 706 binary variables + 139904 bilinear constraints (= 139904 bilinear terms).
Best regards,
Jaromił0 -
Hello Jaromil,
Thanks for your reply!
Actually that is not completely true. I do not have any bilinear constraints. I do have some bilinear terms in the objective function but even when I remove those terms IntInf still stays 65k+. Can there be any other reason?
However, these do vanish if I set Obj = 0. But I still have some extra variables i.e., 1074 + 1072 = 2146 expected. 1667 + 707 = 2374 seen after presolve. See image:
1 -
Hi Gaurav,
In your first screenshot you can see the line
Presolved model has 139904 bilinear constraints.
So Gurobi's presolve generated 139904 from your original model. These can all be violated in a linear relaxation and ultimately count into the IntInf number.
In the new screenshot I do not see any larger IntInf than 78. Could you please clarify?
Best regards,
Jaromił0 -
That's exactly what's baffling me. The only difference between the two screenshots is that in the second screenshot case, my Obj = 0*Obj_original.
0 -
That's exactly what's baffling me. The only difference between the two screenshots is that in the second screenshot case, my Obj = 0*Obj_original.
In your first screenshot, you can see
Model has 140976 quadratic objective terms
Because your objective is determined to be non-convex, Gurobi's presolve turns it into 1072 quadratic constraints and 139904 bilinear constraints.
Best regards,
Jaromił0 -
Thanks Jaromil!
That makes perfect sense. Does this mean that such a model in practically unsolvable because of this extremely high number of auxiliary constraints and variables? Or is there still a hope?
For a small subset of the cases, my obj can be convex but it will remain non-convex due to bilinear terms for most cases. Is there a way to formulate it better?P.S. I have set NonConvex parameter to 2 and DualReductions to 0. It helped in cases with 43+40 variables in the past.
0 -
Does this mean that such a model in practically unsolvable because of this extremely high number of auxiliary constraints and variables? Or is there still a hope?
For a small subset of the cases, my obj can be convex but it will remain non-convex due to bilinear terms for most cases. Is there a way to formulate it better?I don't think you have to give up yet. You could first try to improve the coefficient ranges of your model.
You can see that the coefficient ranges of your model are
Matrix range [8e-06, 1e+04]
Objective range [1e-04, 3e-01]
QObjective range [4e-08, 1e-01]
Bounds range [1e-04, 1e+01]
RHS range [1e-05, 1e+04]So there is a more than 6 orders of magnitude difference between the smallest and the biggest coefficient. Maybe re-scaling your model might already give it a needed performance boost, see our Guidelines for Numerical Issues for more information.
The objective function is very dense. If possible, you could try to use some model knowledge and remove some bilinear terms from the objective, e.g., if you know that some product \(x \cdot y \) does not have any impact on the optimal solution point.
You could experiment with the NoRelHeurTime parameter to run the No Relaxation heuristic which will try to find a feasible solution point before solving the root node relaxation.
Best regards,
Jaromił0 -
Thanks Jaromil!
For the coefficient ranges, I did try to re-scale the model to have all the ranges between 1e-4 and 1e+4 e.g., I needed to multiply my objective function (was already in 500k Euros scale) by 10 but such things only increased the computation time. E.g., the computation time with Obj=0 increased from 40 seconds to 450 seconds.
Another important question about objective formulation. Does Gurobi with (NonConvex parameter = 2) consider the following terms also as bilinear terms:- variable1*variable1
- 0*variable1*variable2
- 0*variable1*MLinExpr[1]
I have many terms with a 0 multiplier in the objective function. Do you think that using a for loop with an if coefficient>0 condition to form objective element wise would reduce these bilinear terms/constraints as compared to doing [Coeff. vector]*MVars*MLinkExpr?
Additionally, is there a way to check/confirm the convexity of an objective function within Gurobi by using a function or attribute?
Regards
Gaurav
0 -
Hi Gaurav,
For the coefficient ranges, I did try to re-scale the model to have all the ranges between 1e-4 and 1e+4 e.g., I needed to multiply my objective function (was already in 500k Euros scale) by 10 but such things only increased the computation time. E.g., the computation time with Obj=0 increased from 40 seconds to 450 seconds.
Did you also check the quality of the solution point. It may be that the badly scaled model converges faster, but that it also returns a qualitatively worse solution, e.g., larger constraint violations.
Does Gurobi with (NonConvex parameter = 2) consider the following terms also as bilinear terms:
- variable1*variable1
- 0*variable1*variable2
- 0*variable1*MLinExpr[1]
- Yes
- Yes, but it will be automatically removed
- Yes, but it will be automatically removed
In general, if you know that a coefficient is 0 then I would not add such a term to the model.
Do you think that using a for loop with an if coefficient>0 condition to form objective element wise would reduce these bilinear terms/constraints as compared to doing [Coeff.vector]*MVars*MLinkExpr?
It should make no difference because the terms with a 0 coefficient will be removed anyway. However, you might consider removing all terms with, e.g., a coefficient with ABS(coef) <= 1e-7.
Additionally, is there a way to check/confirm the convexity of an objective function within Gurobi by using a function or attribute?
If you set the parameter NonConvex=1 then Gurobi will only solve your model if it is able to reformulate is into a convex model in presolve. Otherwise, it will throw an error. If you set the parameter NonConvex=0 then Gurobi will only solve your model if the original model, i.e., the un-presolved model, is determined to be convex. Otherwise, an error is thrown.
Please note that it is possible that your model is indeed convex but Gurobi is not able to detect it.
Best regards,
Jaromił0 -
"However, you might consider removing all terms with, e.g., a coefficient with ABS(coef) <= 1e-7"
Thanks. This is a good suggestion. Is there a straightforward way to do this for a non-convex quadratic obj function?
RegardsGaurav
0 -
Is there a straightforward way to do this for a non-convex quadratic obj function?
After you have constructed your objective, you first call the update method to push all changes into the model.
You then retrieve the objective via the getObjective method. This should give you a QuadExpr object. Because your model is quadratic, you will have to rebuild it. This means that you have to go over all entries in your objective and construct a new one. This can be done as follows
obj = m.getObjective() # objective is quadratic so you will get a QuadExpr object
linobjpart = obj.getLinExpr() # retrieve linear part of quadratic objective
newobj = gp.QuadExpr(0)
# manage linear part first
for i in range(linobjpart.size()):
coef = linobjpart.getCoef(i)
var = linobjpart.getVar(i)
if abs(coef) > 1e-7:
newobj.add(coef * var)
# manage quadratic part second
for i in range(obj.size()):
coef = obj.getCoef(i)
var1 = obj.getVar1(i)
var2 = obj.getVar2(i)
if abs(coef) > 1e-7:
newobj.add(coef * var1 * var2)
m.setObjective(newobj)Please note that I did not test the code.
Best regards,
Jaromił0 -
Hi Jaromil!
Thanks for this suggestion. I actually used the limit of 1e-3 and this way I could reduce the size of my Obj from 280k to 12k. This of course has implications for the optimality. I am currently accessing the solutions (if obtainable) with this workaround.In the meantime, another way to reduce the size of the Objective function is by adding extra variables. This is sort of cheating but just wanted to know if it makes any difference? e.g.,
add variable X1add variable X2
F = X1+X2optimise F
Obj has a size of 2 in this case whereas if
add variable X1
add variable X2
add variable F
add constraint F-X1+X2>=1e-5
add constraint F-X1+X2<=1e-5
optimise F
Here the Obj will have a size of 1 but of course we have extra constraints.
Do you think the latter can have positive effects in terms of the solution process? In this way I can reduce Obj size from 280K to 5k but will need to add about 5k extra linear constraints as well.
RegardsGaurav
0 -
Hi Gaurav,
Do you think the latter can have positive effects in terms of the solution process? In this way I can reduce Obj size from 280K to 5k but will need to add about 5k extra linear constraints as well.
This should normally have no effect on the performance, because you just move the nonzeros from the objective to constraints. However, it may be worth a try, especially if you can provide some tight bounds for auxiliary variables, which you might obtain through some application knowledge.
Best regards,
Jaromił0 -
Hello Jaromil,
Indeed, it did not make an appreciable difference.
I have been able to solve feasibility problem with Obj = 0 within 40-60 seconds, the problem with an irrelevant linear obj function e.g., Obj = X.sum() within 1000-1200 seconds. However, the problem with my desired Objective function which is non-convex quadratic remains unsolved even after running for more than 24 hours (even after filtering for terms with coefficient>1e-3).
Can you kindly suggest certain reformulation tips to make the problem solve within appreciable time?
Do you think that it is normal that it the solution time scales like that? Is it just the supposed computation time or is it running into numerical issues? I am willing to wait out if it can be expected to converge after a certain amount of time but at the moment it just seems like it will never be solved.
The following is the log file before I stopped the solver manuallyGurobi 10.0.0 (win64) logging started Sat Nov 11 14:02:12 2023
Set parameter LogFile to value "gurobi_cs3.log"
Discarded solution information
Gurobi 10.0.0 (win64) logging started Sat Nov 11 14:02:35 2023
Set parameter LogFile to value "gurobi_cs3.log"
Discarded solution information
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64)
CPU model: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 6324 rows, 2998 columns and 47220 nonzeros
Model fingerprint: 0xd633f72c
Model has 2628 quadratic objective terms
Variable types: 1926 continuous, 1072 integer (1072 binary)
Coefficient statistics:
Matrix range [9e-06, 1e+04]
Objective range [2e-03, 3e+02]
QObjective range [4e-02, 1e+02]
Bounds range [1e-04, 1e+01]
RHS range [1e-03, 1e+04]
Presolve removed 2457 rows and 738 columns
Presolve time: 0.24s
Presolved: 6980 rows, 4893 columns, 44456 nonzeros
Presolved model has 1072 quadratic constraint(s)
Presolved model has 1556 bilinear constraint(s)
Variable types: 4357 continuous, 536 integer (536 binary)
Starting NoRel heuristic
Found phase-1 solution: relaxation 4.07079e+07
Found phase-1 solution: relaxation 3.56754e+07
Found phase-1 solution: relaxation 2.84033e+07
Found phase-1 solution: relaxation 2.80211e+07
Found phase-1 solution: relaxation 2.66263e+07
Found phase-1 solution: relaxation 2.38315e+07
Found phase-1 solution: relaxation 2.09587e+07
Found phase-1 solution: relaxation 2.00396e+07
Found phase-1 solution: relaxation 1.17767e+07
Found phase-1 solution: relaxation 1.14465e+07
Found phase-1 solution: relaxation 1.14434e+07
Found phase-1 solution: relaxation 1.02798e+07
Elapsed time for NoRel heuristic: 5s (best bound -721945)
Found phase-1 solution: relaxation 1.02787e+07
Found phase-1 solution: relaxation 1.01797e+07
Found phase-1 solution: relaxation 9.82707e+06
Found phase-1 solution: relaxation 9.51547e+06
Found phase-1 solution: relaxation 8.39308e+06
Found phase-1 solution: relaxation 8.39202e+06
Found phase-1 solution: relaxation 8.031e+06
Found phase-1 solution: relaxation 7.88233e+06
Found phase-1 solution: relaxation 7.74096e+06
Found phase-1 solution: relaxation 7.66319e+06
Found phase-1 solution: relaxation 7.07854e+06
Found phase-1 solution: relaxation 6.47003e+06
Found phase-1 solution: relaxation 5.61754e+06
Elapsed time for NoRel heuristic: 10s (best bound -721945)
Found phase-1 solution: relaxation 4.36451e+06
Found phase-1 solution: relaxation 4.10951e+06
Found phase-1 solution: relaxation 3.32296e+06
Elapsed time for NoRel heuristic: 17s (best bound -721945)
Found phase-1 solution: relaxation 2.97953e+06
Found phase-1 solution: relaxation 2.18814e+06
Found phase-1 solution: relaxation 2.18814e+06
Found phase-1 solution: relaxation 2.03947e+06
Found phase-1 solution: relaxation 1.76662e+06
Found phase-1 solution: relaxation 1.74283e+06
Elapsed time for NoRel heuristic: 22s (best bound -721945)
Found phase-1 solution: relaxation 1.61456e+06
Found phase-1 solution: relaxation 1.60965e+06
Found phase-1 solution: relaxation 1.6095e+06
Found phase-1 solution: relaxation 1.42623e+06
Found phase-1 solution: relaxation 1.42426e+06
Elapsed time for NoRel heuristic: 28s (best bound -721945)
Found phase-1 solution: relaxation 1.41686e+06
Found phase-1 solution: relaxation 1.41667e+06
Found phase-1 solution: relaxation 690927
Elapsed time for NoRel heuristic: 33s (best bound -721945)
Found phase-1 solution: relaxation 661143
Found phase-1 solution: relaxation 656666
Found phase-1 solution: relaxation 655889
Found phase-1 solution: relaxation 655090
Found phase-1 solution: relaxation 655017
Found phase-1 solution: relaxation 624054
Elapsed time for NoRel heuristic: 38s (best bound -721945)
Found phase-1 solution: relaxation 387158
Found phase-1 solution: relaxation 4819.57
Found phase-1 solution: relaxation 4776.55
Found phase-1 solution: relaxation 4760.52
Elapsed time for NoRel heuristic: 44s (best bound -721945)
Found phase-1 solution: relaxation 4163.94
Found phase-1 solution: relaxation 4163.94
Found phase-1 solution: relaxation 4159.76
Elapsed time for NoRel heuristic: 52s (best bound -721945)
Found phase-1 solution: relaxation 2939.08
Found phase-1 solution: relaxation 2919.28
Found phase-1 solution: relaxation 2892.49
Elapsed time for NoRel heuristic: 58s (best bound -721945)
Found phase-1 solution: relaxation 2879.1
Found phase-1 solution: relaxation 2875.91
Found phase-1 solution: relaxation 2863.62
Found phase-1 solution: relaxation 2201.91
Elapsed time for NoRel heuristic: 64s (best bound -721945)
Found phase-1 solution: relaxation 2197.4
Found phase-1 solution: relaxation 2188.97
Found phase-1 solution: relaxation 1592.42
Found phase-1 solution: relaxation 1590.7
Found phase-1 solution: relaxation 1590.04
Found phase-1 solution: relaxation 1588.81
Found phase-1 solution: relaxation 1588.07
Elapsed time for NoRel heuristic: 70s (best bound -721945)
Found phase-1 solution: relaxation 1587.66
Found phase-1 solution: relaxation 195.106
Elapsed time for NoRel heuristic: 76s (best bound -721945)
Found phase-1 solution: relaxation 194.571
Found phase-1 solution: relaxation 181.834
Found phase-1 solution: relaxation 181.639
Elapsed time for NoRel heuristic: 83s (best bound -721945)
Found phase-1 solution: relaxation 180.364
Found phase-1 solution: relaxation 151.247
Found phase-1 solution: relaxation 128.011
Found phase-1 solution: relaxation 97.7612
Elapsed time for NoRel heuristic: 91s (best bound -721945)
Found phase-1 solution: relaxation 63.0452
Found phase-1 solution: relaxation 43.6743
Found phase-1 solution: relaxation 43.6632
Found phase-1 solution: relaxation 43.6375
Found phase-1 solution: relaxation 43.3979
Elapsed time for NoRel heuristic: 97s (best bound -721945)
Found phase-1 solution: relaxation 40.3222
Elapsed time for NoRel heuristic: 102s (best bound -721945)
Found phase-1 solution: relaxation 19.2267
Found phase-1 solution: relaxation 19.2009
Found phase-1 solution: relaxation 18.3264
Elapsed time for NoRel heuristic: 108s (best bound -721945)
Found phase-1 solution: relaxation 0.253805
Found phase-1 solution: relaxation 0.253678
Found phase-1 solution: relaxation 0.235663
Elapsed time for NoRel heuristic: 117s (best bound -721945)
Elapsed time for NoRel heuristic: 122s (best bound -721945)
Elapsed time for NoRel heuristic: 128s (best bound -721945)
Found phase-1 solution: relaxation 0
Found heuristic solution: objective -360916.7779
Transition to phase 2
Elapsed time for NoRel heuristic: 143s (best bound -721945)
Found heuristic solution: objective -360916.7781
Found heuristic solution: objective -360916.7798
Elapsed time for NoRel heuristic: 148s (best bound -721945)
Elapsed time for NoRel heuristic: 189s (best bound -721945)
Elapsed time for NoRel heuristic: 197s (best bound -721945)
Warning: Markowitz tolerance tightened to 0.5
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -5.4845137e+16 7.415648e+16 0.000000e+00 198s
6393 -7.2194456e+05 0.000000e+00 0.000000e+00 199s
Root relaxation: objective -7.219446e+05, 6393 iterations, 0.93 seconds (1.20 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -721944.56 0 1172 -360916.78 -721944.56 100% - 198s
0 0 -721934.25 0 1172 -360916.78 -721934.25 100% - 198s
H 0 0 -360916.7798 -721934.25 100% - 198s
H 0 0 -360916.7952 -488154.40 35.3% - 200s
0 0 -488154.40 0 1178 -360916.80 -488154.40 35.3% - 200s
0 0 -486531.81 0 1172 -360916.80 -486531.81 34.8% - 200s
0 0 -457807.83 0 1202 -360916.80 -457807.83 26.8% - 201s
0 0 -457639.23 0 1197 -360916.80 -457639.23 26.8% - 201s
0 0 -415879.51 0 1167 -360916.80 -415879.51 15.2% - 206s
0 0 -415878.11 0 1170 -360916.80 -415878.11 15.2% - 206s
0 0 -412894.97 0 1173 -360916.80 -412894.97 14.4% - 207s
0 0 -385211.31 0 1141 -360916.80 -385211.31 6.73% - 211s
0 0 -384748.92 0 1145 -360916.80 -384748.92 6.60% - 211s
0 0 -383920.18 0 1141 -360916.80 -383920.18 6.37% - 212s
0 0 -383041.59 0 1132 -360916.80 -383041.59 6.13% - 212s
0 0 -378659.52 0 1133 -360916.80 -378659.52 4.92% - 214s
0 0 -378086.88 0 1133 -360916.80 -378086.88 4.76% - 215s
0 0 -374733.03 0 1096 -360916.80 -374733.03 3.83% - 216s
0 0 -374510.93 0 1089 -360916.80 -374510.93 3.77% - 217s
0 0 -373093.48 0 1063 -360916.80 -373093.48 3.37% - 218s
0 0 -372987.78 0 1062 -360916.80 -372987.78 3.34% - 218s
0 0 -372968.02 0 1072 -360916.80 -372968.02 3.34% - 218s
0 0 -372956.51 0 1063 -360916.80 -372956.51 3.34% - 218s
0 0 -372951.08 0 1064 -360916.80 -372951.08 3.33% - 218s
0 0 -372948.30 0 1064 -360916.80 -372948.30 3.33% - 219s
0 0 -372948.28 0 1065 -360916.80 -372948.28 3.33% - 219s
0 0 -372948.27 0 1065 -360916.80 -372948.27 3.33% - 219s
0 0 -372946.51 0 1059 -360916.80 -372946.51 3.33% - 222s
0 2 -372946.50 0 1059 -360916.80 -372946.50 3.33% - 223s
7 12 postponed 3 -360916.80 -372087.05 3.09% 7802 268s
13 18 postponed 4 -360916.80 -371898.62 3.04% 11233 296s
19 24 postponed 4 -360916.80 -371898.62 3.04% 9312 308s
25 28 infeasible 5 -360916.80 -371898.62 3.04% 8842 337s
31 34 infeasible 5 -360916.80 -371898.62 3.04% 8829 341s
41 40 infeasible 5 -360916.80 -371379.79 2.90% 7235 349s
51 47 -368274.15 5 1052 -360916.80 -371379.79 2.90% 6606 356s
60 53 -368194.54 7 1049 -360916.80 -371379.79 2.90% 6368 392s
H 71 54 -360916.8140 -371379.79 2.90% 6895 407s
H 81 54 -360916.8158 -371379.79 2.90% 6508 407s
87 64 postponed 11 -360916.82 -371379.79 2.90% 6263 419s
101 69 infeasible 12 -360916.82 -371379.79 2.90% 5723 503s
116 76 infeasible 10 -360916.82 -371379.79 2.90% 6040 534s
128 84 postponed 10 -360916.82 -371379.79 2.90% 6231 550s
143 97 postponed 11 -360916.82 -371379.79 2.90% 6229 557s
158 100 infeasible 12 -360916.82 -371379.79 2.90% 6076 565s
170 110 infeasible 12 -360916.82 -371379.79 2.90% 5956 642s
187 118 -367693.83 12 1038 -360916.82 -371379.79 2.90% 6477 657s
204 126 -366058.11 19 979 -360916.82 -371379.79 2.90% 6395 731s
216 136 -365261.11 26 953 -360916.82 -371379.79 2.90% 6945 747s
230 149 -364178.86 34 865 -360916.82 -371379.79 2.90% 7072 779s
H 239 149 -360916.9479 -371379.79 2.90% 7252 779s
247 163 postponed 36 -360916.95 -371379.79 2.90% 7177 796s
275 183 postponed 37 -360916.95 -371379.79 2.90% 6875 832s
299 199 postponed 38 -360916.95 -371379.79 2.90% 6870 858s
330 232 infeasible 39 -360916.95 -371379.79 2.90% 6535 876s
H 334 232 -360916.9489 -371379.79 2.90% 6457 876s
H 344 232 -360916.9498 -371379.79 2.90% 6365 876s
378 251 -362753.68 42 799 -360916.95 -371379.79 2.90% 5924 898s
409 252 -365779.30 21 305 -360916.95 -371379.79 2.90% 5725 972s
411 253 -371379.79 5 288 -360916.95 -371379.79 2.90% 5697 978s
412 254 -366503.18 19 243 -360916.95 -371379.79 2.90% 5683 980s
437 271 -367642.78 18 225 -360916.95 -371379.79 2.90% 5358 986s
444 278 -371379.79 18 951 -360916.95 -371379.79 2.90% 5304 997s
449 282 -371379.79 19 948 -360916.95 -371379.79 2.90% 5277 1011s
455 286 -371379.79 20 918 -360916.95 -371379.79 2.90% 5289 1019s
461 287 -371379.79 20 933 -360916.95 -371379.79 2.90% 5302 1021s
467 289 infeasible 21 -360916.95 -371379.79 2.90% 5264 1038s
473 293 -371379.79 21 915 -360916.95 -371379.79 2.90% 5280 1043s
481 293 -371379.79 22 912 -360916.95 -371379.79 2.90% 5252 1050s
490 295 postponed 22 -360916.95 -371379.79 2.90% 5253 1057s
498 297 postponed 23 -360916.95 -371379.79 2.90% 5239 1061s
H 501 281 -360916.9525 -371379.79 2.90% 5209 1061s
508 281 infeasible 23 -360916.95 -371379.79 2.90% 5199 1067s
518 277 infeasible 25 -360916.95 -371379.79 2.90% 5198 1070s
H 540 256 -360916.9528 -371379.79 2.90% 5140 1073s
541 263 postponed 26 -360916.95 -371379.79 2.90% 5152 1082s
550 263 infeasible 27 -360916.95 -371379.79 2.90% 5135 1085s
566 266 infeasible 27 -360916.95 -371379.79 2.90% 5050 1091s
576 274 postponed 23 -360916.95 -371379.79 2.90% 5047 1095s
589 276 postponed 23 -360916.95 -371379.79 2.90% 5005 1108s
607 278 postponed 24 -360916.95 -371379.79 2.90% 4941 1111s
H 614 263 -360916.9781 -371379.79 2.90% 4924 1111s
617 270 postponed 24 -360916.98 -371379.79 2.90% 4917 1116s
627 278 postponed 25 -360916.98 -371379.79 2.90% 4910 1122s
639 286 postponed 25 -360916.98 -371379.79 2.90% 4898 1125s
H 651 270 -360916.9783 -371379.79 2.90% 4857 1125s
653 286 postponed 26 -360916.98 -371379.79 2.90% 4862 1131s
669 296 postponed 24 -360916.98 -371379.79 2.90% 4836 1136s
685 303 infeasible 27 -360916.98 -371379.79 2.90% 4781 1142s
695 300 -371379.79 66 648 -360916.98 -371379.79 2.90% 4783 1330s
699 314 postponed 27 -360916.98 -371379.79 2.90% 4775 1336s
715 330 postponed 26 -360916.98 -371379.79 2.90% 4755 1342s
736 344 postponed 28 -360916.98 -371379.79 2.90% 4713 1350s
758 357 postponed 26 -360916.98 -371379.79 2.90% 4673 1358s
782 347 postponed 29 -360916.98 -371379.79 2.90% 4630 1368s
798 347 postponed 28 -360916.98 -371379.79 2.90% 4633 1378s
H 817 330 -360916.9783 -371379.79 2.90% 4639 1378s
820 335 postponed 29 -360916.98 -371379.79 2.90% 4646 1387s
834 328 postponed 29 -360916.98 -371379.79 2.90% 4688 1397s
858 318 postponed 30 -360916.98 -371379.79 2.90% 4711 1425s
876 314 infeasible 31 -360916.98 -371379.79 2.90% 4828 1433s
898 315 postponed 35 -360916.98 -371379.79 2.90% 4853 1442s
910 323 postponed 36 -360916.98 -371379.79 2.90% 4923 1452s
922 323 postponed 37 -360916.98 -371379.79 2.90% 5005 1473s
948 327 postponed 50 -360916.98 -371379.79 2.90% 5075 1484s
961 341 postponed 52 -360916.98 -371379.79 2.90% 5153 1497s
979 352 postponed 55 -360916.98 -371379.79 2.90% 5259 1513s
1000 361 postponed 58 -360916.98 -371379.79 2.90% 5360 1527s
1022 355 infeasible 62 -360916.98 -371379.79 2.90% 5449 1556s
1059 356 postponed 38 -360916.98 -371379.79 2.90% 5506 1575s
1085 370 postponed 41 -360916.98 -371379.79 2.90% 5572 1592s
1115 391 postponed 45 -360916.98 -371379.79 2.90% 5596 1611s
1144 411 postponed 50 -360916.98 -371379.79 2.90% 5697 1632s
1172 424 postponed 55 -360916.98 -371379.79 2.90% 5815 1656s
1221 431 postponed 60 -360916.98 -371379.79 2.90% 5864 1679s
1268 468 postponed 65 -360916.98 -371379.79 2.90% 5931 1706s
1313 436 infeasible 72 -360916.98 -371379.79 2.90% 6035 1761s
1428 461 infeasible 79 -360916.98 -371379.79 2.90% 5914 1789s
1467 466 infeasible 57 -360916.98 -371379.79 2.90% 5989 1815s
1538 494 postponed 57 -360916.98 -371379.79 2.90% 5976 1845s
1582 531 postponed 61 -360916.98 -371379.79 2.90% 6092 1886s
1639 560 postponed 71 -360916.98 -371379.79 2.90% 6229 1936s
1734 556 infeasible 84 -360916.98 -371379.79 2.90% 6281 2017s
1904 560 postponed 102 -360916.98 -371379.79 2.90% 6192 2071s
2060 593 postponed 119 -360916.98 -371379.79 2.90% 6140 2125s
2185 652 infeasible 62 -360916.98 -371379.79 2.90% 6180 2176s
2270 653 postponed 71 -360916.98 -371379.79 2.90% 6272 2238s
2445 713 postponed 41 -360916.98 -371379.79 2.90% 6198 2296s
2547 713 infeasible 57 -360916.98 -371379.79 2.90% 6270 2373s
2723 798 postponed 73 -360916.98 -371379.79 2.90% 6233 2450s
2846 819 postponed 94 -360916.98 -371379.79 2.90% 6338 2540s
3089 857 postponed 54 -360916.98 -371379.79 2.90% 6293 2604s
3223 871 infeasible 75 -360916.98 -371379.79 2.90% 6329 2672s
3401 913 postponed 87 -360916.98 -371379.79 2.90% 6287 2736s
3549 958 postponed 44 -360916.98 -371379.79 2.90% 6306 2798s
3698 1039 postponed 62 -360916.98 -371379.79 2.90% 6321 2866s
3849 1127 postponed 74 -360916.98 -371379.79 2.90% 6341 2933s
3977 1207 postponed 92 -360916.98 -371379.79 2.90% 6398 3003s
4117 1276 postponed 111 -360916.98 -371379.79 2.90% 6444 3073s
4238 1338 postponed 128 -360916.98 -371379.79 2.90% 6499 3148s
4360 1401 postponed 66 -360916.98 -371379.79 2.90% 6558 3224s
4521 1514 postponed 61 -360916.98 -371379.79 2.90% 6581 3303s
4682 1626 infeasible 81 -360916.98 -371379.79 2.90% 6630 3386s
4852 1743 postponed 104 -360916.98 -371379.79 2.90% 6679 3471s
5021 1864 postponed 125 -360916.98 -371379.79 2.90% 6730 3557s
5194 1982 postponed 145 -360916.98 -371379.79 2.90% 6779 3641s
5374 2104 postponed 173 -360916.98 -371379.79 2.90% 6821 3732s
5566 2244 postponed 197 -360916.98 -371379.79 2.90% 6855 3828s
5752 2388 postponed 227 -360916.98 -371379.79 2.90% 6912 3937s
5988 2514 postponed 260 -360916.98 -371379.79 2.90% 6946 4049s
6246 2654 postponed 293 -360916.98 -371379.79 2.90% 6961 4169s
6514 2798 postponed 323 -360916.98 -371379.79 2.90% 6968 4293s
6750 2972 postponed 350 -360916.98 -371379.79 2.90% 7009 4418s
7010 3149 infeasible 385 -360916.98 -371379.79 2.90% 7032 4546s
7293 3290 infeasible 421 -360916.98 -371379.79 2.90% 7054 4677s
7608 3451 infeasible 218 -360916.98 -371379.79 2.90% 7057 4809s
7885 3599 postponed 263 -360916.98 -371379.79 2.90% 7092 4948s
8179 3795 postponed 277 -360916.98 -371379.79 2.90% 7127 5095s
8525 3865 postponed 297 -360916.98 -371379.79 2.90% 7145 5236s
8879 3885 postponed 327 -360916.98 -371379.79 2.90% 7105 5373s
9233 3904 postponed 347 -360916.98 -371379.79 2.90% 7036 5503s
9590 3999 postponed 381 -360916.98 -371379.79 2.90% 6960 5656s
9963 4089 postponed 673 -360916.98 -371379.79 2.90% 6925 5970s
10781 4226 infeasible 345 -360916.98 -371379.79 2.90% 6812 6297s
11526 4275 infeasible 37 -360916.98 -371379.79 2.90% 6748 6642s
12431 4073 infeasible 400 -360916.98 -371379.79 2.90% 6632 6971s
13389 3977 infeasible 480 -360916.98 -371379.79 2.90% 6439 7318s
14245 3941 infeasible 350 -360916.98 -371379.79 2.90% 6315 7681s
15093 3858 infeasible 548 -360916.98 -371379.79 2.90% 6223 8065s
16038 3556 infeasible 419 -360916.98 -371379.79 2.90% 6118 8465s
17176 3466 infeasible 227 -360916.98 -371379.79 2.90% 5956 8849s
18218 3140 infeasible 187 -360916.98 -371379.79 2.90% 5862 9230s
19574 2822 infeasible 336 -360916.98 -371379.79 2.90% 5714 9615s
20830 2439 infeasible 218 -360916.98 -371379.79 2.90% 5606 10008s
22199 1919 infeasible 224 -360916.98 -371379.79 2.90% 5494 10404s
23781 1659 infeasible 176 -360916.98 -371379.79 2.90% 5353 10844s
25311 1616 postponed 89 -360916.98 -371379.79 2.90% 5277 11334s
26960 734 postponed 100 -360916.98 -371379.79 2.90% 5256 11756s
29715 851 postponed 67 -360916.98 -371379.79 2.90% 4941 11879s
29904 969 postponed 59 -360916.98 -371379.79 2.90% 4972 12023s
30142 1066 infeasible 85 -360916.98 -371379.79 2.90% 5006 12201s
30462 1258 postponed 119 -360916.98 -371379.79 2.90% 5040 12407s
30791 1465 postponed 160 -360916.98 -371379.79 2.90% 5088 12680s
31304 1720 infeasible 217 -360916.98 -371379.79 2.90% 5139 13044s
31893 2091 postponed 288 -360916.98 -371379.79 2.90% 5211 13502s
32848 2535 postponed 388 -360916.98 -371379.79 2.90% 5284 14041s
33956 2434 postponed 82 -360916.98 -371379.79 2.90% 5371 14667s
35629 2613 infeasible 252 -360916.98 -371379.79 2.90% 5378 15319s
37278 3031 postponed 85 -360916.98 -371379.79 2.90% 5423 16008s
38836 3422 infeasible 220 -360916.98 -371379.79 2.90% 5498 16750s
40451 4034 postponed 289 -360916.98 -371379.79 2.90% 5575 17568s
42041 4699 postponed 239 -360916.98 -371379.79 2.90% 5671 18417s
43570 5312 postponed 329 -360916.98 -371379.79 2.90% 5774 19366s
45187 6048 postponed 425 -360916.98 -371379.79 2.90% 5878 20382s
47163 6450 postponed 529 -360916.98 -371379.79 2.90% 5965 21394s
49571 7163 postponed 636 -360916.98 -371379.79 2.90% 6004 22430s
51480 7628 postponed 742 -360916.98 -371379.79 2.90% 6086 23464s
53831 8325 infeasible 612 -360916.98 -371379.79 2.90% 6130 24520s
55982 8310 postponed 432 -360916.98 -371379.79 2.90% 6193 25600s
58549 8458 postponed 191 -360916.98 -371379.79 2.90% 6182 26620s
61001 8608 postponed 210 -360916.98 -371379.79 2.90% 6183 27701s
63661 9037 postponed 335 -360916.98 -371379.79 2.90% 6179 28813s
66050 9878 infeasible 513 -360916.98 -371379.79 2.90% 6209 30225s
68989 10842 postponed 603 -360916.98 -371379.79 2.90% 6269 31672s
71849 11661 infeasible 429 -360916.98 -371379.79 2.90% 6334 33092s
74846 12841 postponed 577 -360916.98 -371379.79 2.90% 6382 34541s
77880 13409 postponed 266 -360916.98 -371379.79 2.90% 6445 36153s
82388 13987 postponed 1344 -360916.98 -371379.79 2.90% 6424 37675s
86184 15397 postponed 628 -360916.98 -371379.79 2.90% 6419 39025s
88280 16499 postponed 940 -360916.98 -371379.79 2.90% 6502 40367s
91020 17617 postponed 265 -360916.98 -371379.79 2.90% 6556 41770s
94040 18841 postponed 302 -360916.98 -371379.79 2.90% 6598 43336s0 -
Can you kindly suggest certain reformulation tips to make the problem solve within appreciable time?
For this you would have to share the model. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Do you think that it is normal that it the solution time scales like that?
Yes, definitely. If your model has a lot of nonconvex terms then it is expected to take a possibly (extremely) long time to solve.
Is it just the supposed computation time or is it running into numerical issues?
From the logs, you can see that a lot of nodes have the "postponed" status. This only happens if the LP relaxations run into numerical issues.
You could try using NodeMethod=2, Crossover=0, Method=0. This will lead to Gurobi using the Barrier method to solve each node relaxation. Maybe this performs a bit better.
Anyway, you should try to re-scale your model as discussed in our Guidelines for Numerical Issues. This is the best way to avoid numerical trouble.
Additionally, you could try updating to the latest version and/or wait until version 11 is released in December.
Best regards,
Jaromił0 -
Thanks Jaromił for the reply.
I am using a big M trick in my constraints so scaling differently is a bit tricky. I will try some things and get back to you.About the parameters,
NodeMethod=2, Crossover=0, Method=0.
"Note that barrier is not an option for MIQP node relaxations."
Can I ignore this lines and use if for my nonconvex MIQP?0 -
Can I ignore this lines and use if for my nonconvex MIQP?
Good point. No, unfortunately you cannot (unless you see some difference when you run with the parameters). Then I think the only way out is to re-scale or wait for the new release.
0 -
Hi Jaromił,
Here you can find my python script and an excel dependency.
I would love to get some feedback on some tips on reformulating this model to avoid numerical issues. Thank you very much in advance!
Regards
Gaurav0 -
Hi Gaurav,
I had a look at your model. I cannot think of any reformulation which might help here.
However, you might want to try the following:
For example, you have constraint (I generated the model using the write method to write an LP file)
R848: - 5.208333333333334 C2282 - 5.208333333333334 C2424 - C2566 + C2992 = 0
The value \(5.208333333333334\) is actually \( = \frac{125}{24}\). You could multiply the whole constraint by \(24\) to get a nice integer constraint
R848: - 125 C2282 - 125 C2424 - 24 C2566 + 24 C2992 = 0
From looking at your model, you can apply this idea to (I think) almost all constraint in your model. Note that it may sometimes result in a very big RHS. In these cases it might be better to not apply the idea.
In your objective you could try to factor out variables C3329 and C3328 to reduce the number of nonlinear terms drastically. What I mean is to turn the term
... - 0.016 C119 * C3329 - 0.016 C120 * C3329 - 0.016 C121 * C3329
- 0.016 C122 * C3329 - 0.016 C123 * C3329 - 0.016 C124 * C3329
- 0.016 C125 * C3329 - 0.016 C126 * C3329 - 0.016 C130 * C3329
- 0.016 C131 * C3329 - 0.016 C132 * C3329 - 0.016 C136 * C3329 ...into
... - 0.016 z * C3329 ...
...
aux_con: - z + C119 + C120 + C121 + C122 + C123 + C124 + C125
+ C126 + C130 + C131 + C132 + C136 = 0
...
z freeBest regards,
Jaromił0
Please sign in to leave a comment.
Comments
19 comments