MILP stops with OPTIMAL status but a suboptimal solution
Awaiting user inputHi,
I'm experiencing an issue of solving a MILP problem in Gurobi: the solver stops with an OPTIMAL status, but the found solution is definitely not optimal for the given problem. For example, the Gurobi solver gives an optimal objective of 0.71, but the opensource BONMIN solver can give an optimal solution of 0.48.
My Gurobi solution log is attached as below:
Academic license  for noncommercial use only  expires 20230723
Warning for adding constraints: zero or small (< 1e13) coefficients, ignored
Set parameter Username
Academic license  for noncommercial use only  expires 20230723
Set parameter Username
Academic license  for noncommercial use only  expires 20230723
Warning for adding constraints: zero or small (< 1e13) coefficients, ignored
Set parameter Presolve to value 2
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (linux64)
Thread count: 4 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 1452 rows, 2580 columns and 8118 nonzeros
Model fingerprint: 0x992ab60c
Variable types: 1344 continuous, 1236 integer (1236 binary)
Coefficient statistics:
Matrix range [3e04, 1e+02]
Objective range [7e06, 9e+00]
Bounds range [2e01, 1e+02]
RHS range [1e01, 1e+02]
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R3 by 2.000000000
Presolve removed 691 rows and 1390 columns
Presolve time: 0.04s
Presolved: 761 rows, 1190 columns, 3911 nonzeros
Variable types: 641 continuous, 549 integer (549 binary)
Root relaxation presolved: 761 rows, 1190 columns, 3911 nonzeros
Root relaxation: objective 6.975875e01, 634 iterations, 0.01 seconds (0.01 work units)
Another try with MIP start
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
H 0 0 0.8652477 0.69759 19.4%  0s
0 0 0.69759 0 18 0.86525 0.69759 19.4%  0s
H 0 0 0.7416665 0.69759 5.94%  0s
H 0 0 0.7117628 0.69759 1.99%  0s
Cutting planes:
Gomory: 4
Implied bound: 17
MIR: 13
Flow cover: 24
Relaxandlift: 16
Explored 1 nodes (694 simplex iterations) in 0.13 seconds (0.12 work units)
Thread count was 4 (of 4 available processors)
Solution count 3: 0.711763 0.741666 0.865248
Optimal solution found (tolerance 1.00e04)
Best objective 7.117627819289e01, best bound 7.117627819289e01, gap 0.0000%
Can anyone help answer my following questions?
 Gurobi seems stopped at node 0 without doing further branchandcut search. For my problem, will exploring more nodes be helpful? how can I enforce Gurobi solver to explore more nodes?
 What parameters do you suggest to tune for this situation? Currently I'm using default parameters settings, and did some tuning based on the Parameter Guideline. But my manual tuning seems not working. I've changed MIPGap, MIPFocus, DualReductions, Presolve, Cuts etc.
All the best,
Yangyang

Hi Yangyang,
For example, the Gurobi solver gives an optimal objective of 0.71, but the opensource BONMIN solver can give an optimal solution of 0.48.
Please note that Gurobi sets too small coefficients to 0 as noted in the Warning
Warning for adding constraints: zero or small (< 1e13) coefficients, ignored
If those coefficients indeed are significant for the optimal solution point and BONMIN does not ignore these coefficients then it is indeed possible that BONMIN can find a better (and different) solution than Gurobi. Did you check whether the solution point is the same for the two solvers?
Gurobi seems stopped at node 0 without doing further branchandcut search. For my problem, will exploring more nodes be helpful? how can I enforce Gurobi solver to explore more nodes?
Exploring further nodes won't help and is indeed not necessary, because Gurobi already proves global optimality in the root node (the MIPGap is 0).
What parameters do you suggest to tune for this situation? Currently I'm using default parameters settings, and did some tuning based on the Parameter Guideline. But my manual tuning seems not working. I've changed MIPGap, MIPFocus, DualReductions, Presolve, Cuts etc.
I don't think that you need to improve performance in this situation as the model is already solved very quickly. Things that you should check right now for further investigation would be:
 Is Gurobi's solution point the same as BONMIN's?
 Does BONMIN ignore small coefficients (cf. my comment regarding the Warning) and are those coefficients relevant for the objective value?
 Does BONMIN's solution point have any constraint violations? What are the feasibility tolerances of BONMIN? Are they the same as Gurobi's? (cf. FeasibilityTol, IntFeasTol)
You can also see the output
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R3 by 2.000000000Is this the BONMIN solution? If yes, then it either violates the original constraint R3 or the small coefficients were removed from constraint R3 and indeed play a significant role for the model.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment