Gurobi worsen the coefficient ranges while it handles non-convex quadratic constraints and cause numerical issue
OngoingHi,
I'm having trouble to solve my model due to numerical issue, so I'm wandering any method mitigate this numerical issue.
1) My model contains some non-convex bi-linear constraints and general function - min[x] - constraints.
2) It is known that this model is feasible and I confirmed that Gurobi accepts heuristic solutions I provided (which is apparently not global optimal). But the problem is that Gurobi keeps claiming that this solution is global optimal as it finds that the root relaxation node is infeasible or all MIP nodes are infeasible.
3) So, I look into the coefficient statistics: Here is the code I run:
print("\nOriginal")
m.printStats()
p = m.presolve()
print("\nDefault Presolve")
p.printStats()
m.reset()
m.Params.Aggregate = 0
p = m.presolve()
print("\nAggregate = 0")
p.printStats()
m.reset()
m.Params.Presolve = 0
p = m.presolve()
print("\nPresolve = 0")
p.printStats()
r = m.relax()
p = m.presolve()
pr = p.relax()
m.reset()
m.Params.Aggregate = 0
p = m.presolve()
pra = p.relax()
print("\nRelax")
r.printStats()
print("\nRelax & Presolve")
pr.printStats()
print("\nRelax & Aggregate = 0")
pra.printStats()
Then the console output is as follows:
Original
Statistics for Model:
Linear constraint matrix : 16170 Constrs, 18985 Vars, 50004 NZs
Quadratic constraints : 540 Constrs, 16740 NZs
General constraints : 540 Constrs
Matrix coefficient range : [ 0.001, 10000 ]
Objective coefficient range : [ 70, 74688.7 ]
Variable bound range : [ 116.498, 7403.51 ]
RHS coefficient range : [ 0.0798828, 89.3027 ]
Presolve removed 12441 rows and 14731 columns
Presolve time: 0.13s
Default Presolve
Statistics for Model_pre:
Linear constraint matrix : 58179 Constrs, 17754 Vars, 149886 NZs
Variable types : 17442 Continuous,
312 Integer (312 Binary)
Quadratic constraints : 13500 Constrs, 27000 NZs
Matrix coefficient range : [ 5.30436e-05, 1.65212e+09 ]
Objective coefficient range : [ 7.64313, 7.05901e+06 ]
Variable bound range : [ 3.56964e-13, 2.50361e+10 ]
RHS coefficient range : [ 1.09855e-13, 2.50361e+10 ]
Discarded solution information
Set parameter Aggregate to value 0
Presolve removed 3771 rows and 6040 columns
Presolve time: 0.26s
Aggregate = 0
Statistics for Model_pre:
Linear constraint matrix : 71491 Constrs, 27581 Vars, 184501 NZs
Variable types : 27267 Continuous,
314 Integer (314 Binary)
Quadratic constraints : 14636 Constrs, 29272 NZs
Matrix coefficient range : [ 0.001, 1.65212e+07 ]
Objective coefficient range : [ 70, 1.1272e+07 ]
Variable bound range : [ 0.00167153, 2.50503e+10 ]
RHS coefficient range : [ 0.0332472, 2.50503e+10 ]
Discarded solution information
Set parameter Presolve to value 0
Presolve = 0
Statistics for Model_pre:
Linear constraint matrix : 83130 Constrs, 37345 Vars, 200664 NZs
Variable types : 36265 Continuous,
1080 Integer (1080 Binary)
SOS constraints : 1080
Quadratic constraints : 16200 Constrs, 32400 NZs
Matrix coefficient range : [ 0.001, 1.65212e+07 ]
Objective coefficient range : [ 70, 74688.7 ]
Variable bound range : [ 1, 2.81542e+10 ]
RHS coefficient range : [ 0.0798828, 2.81542e+10 ]
Discarded solution information
Relax
Statistics for Model_copy:
Linear constraint matrix : 16170 Constrs, 18985 Vars, 50004 NZs
Quadratic constraints : 540 Constrs, 16740 NZs
Matrix coefficient range : [ 0.001, 10000 ]
Objective coefficient range : [ 70, 74688.7 ]
Variable bound range : [ 116.498, 7403.51 ]
RHS coefficient range : [ 0.0798828, 89.3027 ]
Relax & Presolve
Statistics for Model_pre_copy:
Linear constraint matrix : 83130 Constrs, 37345 Vars, 200664 NZs
Quadratic constraints : 16200 Constrs, 32400 NZs
Matrix coefficient range : [ 0.001, 1.65212e+07 ]
Objective coefficient range : [ 70, 74688.7 ]
Variable bound range : [ 1, 2.81542e+10 ]
RHS coefficient range : [ 0.0798828, 2.81542e+10 ]
Relax & Aggregate = 0
Statistics for Model_pre_copy:
Linear constraint matrix : 83130 Constrs, 37345 Vars, 200664 NZs
Quadratic constraints : 16200 Constrs, 32400 NZs
Matrix coefficient range : [ 0.001, 1.65212e+07 ]
Objective coefficient range : [ 70, 74688.7 ]
Variable bound range : [ 1, 2.81542e+10 ]
RHS coefficient range : [ 0.0798828, 2.81542e+10 ]
Therefore, I realized that coefficient range become worse during the presolve process and i confirmed that it is solely for the non-convex quadratic constraints. (I checked the coefficient ranges the model without 1) quadratic constraints and 2) general function constraints, separately)
4) So I tried to solve the model with Presolve=0, NumericFocus=3, and an initial feasible solution (using var.Start). Although the root simplex log showed "Warning: 1 variable deleted from basis" (a bad sign for numerical problems), Gurobi was able to move on to the MIP node step. However, the problem was that Gurobi kept "postponing" solving the MIP node after certain degree of improvement has been made. From this point on, the best bounds did not improve. Even if I managed the coefficient range by adjusting the scale of variables, the results was the same.
5) I'm currently using Gurobi 10.0.2. I also tried the current latest build (11.0.1), but the current build doesn't seem to be performant enough to handle this issue (sometimes it is worse than the previous version).
Any suggestions and comments will be highly appreciated.
EK
-
Hi EK,
Could you please share the model 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.
Best regards,
Jaromił0 -
Hi Jaromił,
I think I could share the model with you privately. Is there any method I can send an link to you directly?
Appreciated,
EK0
Please sign in to leave a comment.
Comments
2 comments