Unable to find sub-optimal solution

Answered

Comments

3 comments

  • Silke Horn

    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
    Comment actions Permalink
  • Mohit Kumar

    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
    Comment actions Permalink
  • Silke Horn

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk