MILP stops with OPTIMAL status but a suboptimal solution

Awaiting user input

Yangyang Fu

• August 16, 2022 20:05
• Edited

Hi,

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 open-source BONMIN solver can give an optimal solution of 0.48. 

My Gurobi solution log is attached as below:

Academic license - for non-commercial use only - expires 2023-07-23
Warning for adding constraints: zero or small (< 1e-13) coefficients, ignored
Set parameter Username
Academic license - for non-commercial use only - expires 2023-07-23
Set parameter Username
Academic license - for non-commercial use only - expires 2023-07-23
Warning for adding constraints: zero or small (< 1e-13) 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     [3e-04, 1e+02]
  Objective range  [7e-06, 9e+00]
  Bounds range     [2e-01, 1e+02]
  RHS range        [1e-01, 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.975875e-01, 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
  Relax-and-lift: 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.00e-04)
Best objective 7.117627819289e-01, best bound 7.117627819289e-01, gap 0.0000%

Can anyone help answer my following questions?

1. Gurobi seems stopped at node 0 without doing further branch-and-cut search. For my problem, will exploring more nodes be helpful? how can I enforce Gurobi solver to explore more nodes? 
2. 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

1

• 

  Jaromił Najman

  Gurobi Staff

  • August 17, 2022 07:34
  • Edited

  Hi Yangyang,

  For example, the Gurobi solver gives an optimal objective of 0.71, but the open-source 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 (< 1e-13) 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 branch-and-cut 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.000000000

  Is 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.