Unable to find sub-optimal solution

Answered

Mohit Kumar

• August 31, 2021 07:11

I am trying to run Gurobi with a cutoff time and would like to see the best solution found so far. To do this I set the following parameters:

model.Params.timeLimit = cutoff
model.Params.MIPFocus = 1
model.optimize()
print(model.SolCount)

But I get 0 solutions even after 1 hour, is that normal, or am I doing something normal.

1

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:26

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Silke Horn

  Gurobi Staff

  • August 31, 2021 08:29

  Sometimes models are so hard that Gurobi cannot find any solution within 1 hour.

  How big is the model and where is Gurobi stuck? Could you post your log here?

  0
• 

  Mohit Kumar

  • August 31, 2021 08:51

  

  

  

  Thanks for the quick reply. Here is the log from a run with a 10 minutes cutoff:

  Changed value of parameter timeLimit to 600.0
  Prev: inf Min: 0.0 Max: inf Default: inf
  Changed value of parameter MIPFocus to 1
  Prev: 0 Min: 0 Max: 3 Default: 0
  Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
  Thread count: 12 physical cores, 24 logical processors, using up to 24 threads
  Optimize a model with 233840 rows, 62627 columns and 523280 nonzeros
  Model fingerprint: 0x50986aa2
  Variable types: 9679 continuous, 52948 integer (52948 binary)
  Coefficient statistics:
  Matrix range [1e+00, 4e+01]
  Objective range [1e+00, 1e+00]
  Bounds range [1e+00, 2e+01]
  RHS range [1e-02, 4e+01]
  Presolve removed 100600 rows and 41688 columns (presolve time = 5s) ...
  Presolve removed 100603 rows and 41688 columns
  Presolve time: 6.34s
  Presolved: 133237 rows, 20939 columns, 397904 nonzeros
  Variable types: 8099 continuous, 12840 integer (12840 binary)
  
  Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
  Showing first log only...

  Presolve removed 40 rows and 20 columns
  Presolved: 133197 rows, 20919 columns, 397824 nonzeros

  
  Root simplex log...

  Iteration Objective Primal Inf. Dual Inf. Time
  0 -0.0000000e+00 1.513000e+03 1.484300e+10 8s
  14087 2.6518328e-01 0.000000e+00 3.272363e+04 10s
  17250 3.8408577e-01 0.000000e+00 5.930891e+04 15s
  19320 4.6563990e-01 0.000000e+00 9.876198e+03 20s
  Concurrent spin time: 4.23s

  Solved with dual simplex (dual model)

  Root relaxation: objective 1.580000e+03, 61090 iterations, 17.65 seconds

  Nodes | Current Node | Objective Bounds | Work
  Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

  0 0 1580.00000 0 247 - 1580.00000 - - 29s
  0 0 1580.00000 0 343 - 1580.00000 - - 34s
  0 0 1580.00000 0 294 - 1580.00000 - - 37s
  0 0 1580.00000 0 268 - 1580.00000 - - 42s
  0 0 1580.00000 0 221 - 1580.00000 - - 45s
  0 0 1580.00000 0 293 - 1580.00000 - - 47s
  0 0 1580.00000 0 295 - 1580.00000 - - 51s
  0 0 1580.00000 0 249 - 1580.00000 - - 61s
  0 0 1580.00000 0 281 - 1580.00000 - - 66s
  0 0 1580.00000 0 318 - 1580.00000 - - 73s
  0 2 1580.00000 0 318 - 1580.00000 - - 228s
  1 4 1580.00000 1 310 - 1580.00000 - 5769 230s
  27 40 1580.00000 5 307 - 1580.00000 - 765 235s
  87 101 1579.00000 9 286 - 1580.00000 - 539 251s
  100 149 1575.00000 10 912 - 1580.00000 - 1029 265s
  148 279 1578.00000 10 333 - 1580.00000 - 824 416s
  278 734 1577.00000 12 357 - 1580.00000 - 972 485s
  733 1620 1577.00000 34 401 - 1580.00000 - 671 593s
  1659 1691 1569.43808 58 483 - 1580.00000 - 698 600s

  Cutting planes:
  Cover: 1
  Implied bound: 82
  Clique: 39
  MIR: 11
  Flow cover: 331
  GUB cover: 1
  Zero half: 24
  RLT: 44
  Relax-and-lift: 3

  Explored 1730 nodes (1295080 simplex iterations) in 600.10 seconds
  Thread count was 24 (of 24 available processors)

  Solution count 0

  Time limit reached
  Best objective -, best bound 1.580000000000e+03, gap -
  0 9

  0
• 

  Silke Horn

  Gurobi Staff

  • September 03, 2021 06:58

  Hi,

  Thanks for posting your log.

  The model is not extremely big and the numerics seems all right. From the log, you can see that presolve and the root relaxation are quite fast, but then Gurobi struggles to find feasible solutions. In fact, the dashes (-) in the Incumbent (position 6) and Gap (position 8) columns of the tree search log indicate that no feasible solution has been found yet. Looking at the bound (BestBd, position 7), you can see that the bound doesn't make progress either. So the model really seems to be quite hard.

  Do you happen to know any feasible solution that you can pass as a MIP start?

  You could try different parameter settings. Sometimes the zero objective, the minimum relaxation, the feasibility pump, or the no relaxation heuristics can help find an initial feasible solution. So you may experiment with setting/increasing the parameters I linked.

  You could also try Gurobi's parameter tuning tool to find better parameter settings.

  0

Post is closed for comments.