Skip to main content

How to speed up MILP model to find the solution?

Answered

Comments

6 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Suyue,

    There are multiple things to consider here.

    You can see the warning

    Warning for adding variables: zero or small (< 1e-13) coefficients, ignored

    Gurobi sets very small coefficients to \(0\). If these coefficients play a significant role for the solution of your model then you might want to re-scale and/or reformulate your model. For re-scaling, please have a look at our Guidelines for Numerical Issues and for improving model formulation please have a look at our Tech Talk about strong MIP formulations.

    From the log, it is not clear whether it is the best objective that should be improved or the best bound. Do you have an idea about the optimal objective value for your model?

    You should update to the latest version 10.0.1 if possible.

    Could you construct a smaller version of the model? This would make it way easier for you to analyze what actually makes the model so hard (and possibly finding suiting parameters). I would guess that reducing the size of the model by a factor of 10 should already be good enough to make it "analyzable by hand".

    Best regards, 
    Jaromił

    0
  • Suyue Xu
    Curious
    Gurobi-versary
    Conversationalist

    Thank you for your comment!

    It seems that the model has numerical issues, as the binary variables could oscilate during the branch-and-bound.Here is the possible problem syntax(written in MATLAB with yalmip):

    Pw_q==Pw+zetaw_pos.*(repmat(Pw_max,1,T)-Pw)-zetaw_neg.*Pw;

    This syntax aims to introduce a box uncertainty set of wind turbine power to indicate whether the output power touches the upper boundary or the lower boundary.I think the problem lies in the boundary set:when the upper boundary and lower boundary remain same(say both are 0), the binary variable(zetaw_pos and zetaw_neg) can either be 0 or 1.And that may lead to the slow descent of the gap.

    And after I revised the boundary to avoid this problem,the efficient do promote a lot,as gurobi is able to get a solution in about 60s.But the solving process is somekind weird as the solution is concluedd when the gap is very big:

    Removed 217 duplicated or redundant inequalities
    Transfered 2476 inequalities to equalities
    Set parameter Username
    Set parameter MIPGap to value 0.03
    Set parameter CrossoverBasis to value 0
    Set parameter MIPFocus to value 3
    Set parameter NodefileDir to value ""
    Set parameter NoRelHeurTime to value 5
    Set parameter PreSOS2BigM to value 0
    Set parameter TuneTrials to value 3
    Academic license - for non-commercial use only - expires 2023-12-04
    Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
    Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)
    Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
    Optimize a model with 29167 rows, 14644 columns and 409035 nonzeros
    Model fingerprint: 0x51c1326d
    Variable types: 8817 continuous, 5827 integer (5827 binary)
    Coefficient statistics:
      Matrix range     [1e-03, 1e+04]
      Objective range  [1e+01, 1e+03]
      Bounds range     [1e+00, 1e+00]
      RHS range        [3e-14, 1e+04]
    Presolve removed 25656 rows and 10950 columns
    Presolve time: 0.11s
    Presolved: 3511 rows, 3694 columns, 13776 nonzeros
    Variable types: 1889 continuous, 1805 integer (1803 binary)
    Found heuristic solution: objective -2581.451134
    Starting NoRel heuristic
    Found heuristic solution: objective -2581.452201
    Found heuristic solution: objective -2581.452342
    Elapsed time for NoRel heuristic: 6s (best bound -5.8162e+06)
    Root relaxation presolve removed 936 rows and 936 columns
    Root relaxation presolved: 2575 rows, 2758 columns, 11904 nonzeros


    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0   -1.4283703e+07   1.533155e+04   0.000000e+00      6s
        1292   -5.8162046e+06   0.000000e+00   0.000000e+00      6s
        1300   -5.8162046e+06   0.000000e+00   0.000000e+00      6s
    Extra simplex iterations after uncrush: 8

    Root relaxation: objective -5.816205e+06, 1300 iterations, 0.03 seconds (0.06 work units)

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

         0     0 -5816204.6    0  396 -2581.4523 -5816204.6      -     -    6s
         0     0 -4667065.4    0  407 -2581.4523 -4667065.4      -     -    6s
         0     0 -4667065.4    0  396 -2581.4523 -4667065.4      -     -    7s
         0     0 -4644213.9    0  407 -2581.4523 -4644213.9      -     -    7s
         0     0 -4435929.5    0  420 -2581.4523 -4435929.5      -     -    7s
         0     0 -4434038.3    0  422 -2581.4523 -4434038.3      -     -    7s
         0     0 -4433861.8    0  421 -2581.4523 -4433861.8      -     -    7s
         0     0 -3869708.8    0  476 -2581.4523 -3869708.8      -     -    8s
         0     0 -3834164.1    0  484 -2581.4523 -3834164.1      -     -    8s
         0     0 -3584812.6    0  483 -2581.4523 -3584812.6      -     -    8s
         0     0 -3584812.6    0  494 -2581.4523 -3584812.6      -     -    8s
         0     0 -3584812.6    0  498 -2581.4523 -3584812.6      -     -    8s
         0     0 -3565604.2    0  458 -2581.4523 -3565604.2      -     -   10s
         0     0 -3426214.4    0  466 -2581.4523 -3426214.4      -     -   10s
         0     0 -3426214.4    0  466 -2581.4523 -3426214.4      -     -   10s
         0     0 -3388726.0    0  464 -2581.4523 -3388726.0      -     -   12s
         0     0 -3387450.6    0  480 -2581.4523 -3387450.6      -     -   12s
         0     0 -3387450.6    0  480 -2581.4523 -3387450.6      -     -   12s
         0     0 -3387450.6    0  498 -2581.4523 -3387450.6      -     -   12s
         0     0 -3291074.8    0  480 -2581.4523 -3291074.8      -     -   13s
         0     0 -3280952.8    0  468 -2581.4523 -3280952.8      -     -   13s
         0     0 -3280952.8    0  474 -2581.4523 -3280952.8      -     -   13s
         0     0 -3224916.2    0  460 -2581.4523 -3224916.2      -     -   15s
         0     0 -3219546.1    0  476 -2581.4523 -3219546.1      -     -   15s
         0     0 -3219546.1    0  480 -2581.4523 -3219546.1      -     -   15s
         0     0 -3189232.9    0  482 -2581.4523 -3189232.9      -     -   17s
         0     0 -3142551.3    0  500 -2581.4523 -3142551.3      -     -   17s
         0     0 -3116673.0    0  498 -2581.4523 -3116673.0      -     -   17s
         0     0 -3116673.0    0  504 -2581.4523 -3116673.0      -     -   17s
         0     0 -3116673.0    0  512 -2581.4523 -3116673.0      -     -   17s
         0     0 -3104159.6    0  513 -2581.4523 -3104159.6      -     -   18s
         0     0 -2972930.7    0  442 -2581.4523 -2972930.7      -     -   19s
         0     2 -2972930.7    0  437 -2581.4523 -2972930.7      -     -   19s
         3     8 -2671571.3    2  429 -2581.4523 -2879395.7      -   290   20s
    H  211   125                    -2581.543570 -2167624.8      -   248   24s
       310   181 -2121977.3   12  354 -2581.5436 -2131973.4      -   221   25s
      1145   859 infeasible   19      -2581.5436 -1974983.3      -   173   30s
      1467  1051 -1697276.1   18  313 -2581.5436 -1702983.2      -   165   36s
      1476  1057 -1322251.6   13  322 -2581.5436 -1322251.6      -   164   41s
      1484  1062 -1191543.2   12  328 -2581.5436 -1191543.2      -   163   45s
      1503  1076 -1083075.8    8  323 -2581.5436 -1083075.8      -   169   50s
      1517  1085 -723153.77   18  337 -2581.5436 -723153.77      -   168   55s
      1530  1094 -88330.910   21  279 -2581.5436 -88330.910  3322%   166   60s
      1538  1097 -28053.295   29  218 -2581.5436 -28053.295   987%   175   65s

    Cutting planes:
      Learned: 1
      Gomory: 13
      Lift-and-project: 89
      Cover: 131
      Implied bound: 32
      Clique: 26
      MIR: 123
      StrongCG: 4
      Flow cover: 250
      GUB cover: 17
      Inf proof: 3
      Zero half: 12
      Network: 1
      RLT: 4
      Relax-and-lift: 14
      BQP: 2

    Explored 1707 nodes (290334 simplex iterations) in 66.55 seconds (67.93 work units)
    Thread count was 16 (of 16 available processors)

    Solution count 10: -2581.54 -2581.54 -2581.45 ... -2581.45
    No other solutions better than -2581.54

    Optimal solution found (tolerance 3.00e-02)
    Best objective -2.581543575333e+03, best bound -2.581543575333e+03, gap 0.0000%

    I'm wondering if there is still some numeric issues since the gap suddenly steps from 987% to 0.And by the way, the size of the model can't be reduced anymore since I have to construct the kkt condition of the model,which means I need to introduce a lot binaries to slack the complementary condition.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    I'm wondering if there is still some numeric issues since the gap suddenly steps from 987% to 0.

    While quite rare, it is not unusual behavior, especially for more complex models. It is possible that a heuristic or a B&B dive finds some information which allows to prune a big chunk of the tree resulting in big MIPGap jumps.

    You can see that the No Relaxation Heuristic found a very good solution very quickly. This can lead to impactful presolve reductions which ultimately lead to quicker convergence.

    You should definitely check whether the solution computed by Gurobi satisfies the needs of your application.

    The RHS range of your constraints is questionable

    RHS range        [3e-14, 1e+04]

    It would be best to clean it up manually before optimizing and set very small coefficients to \(0\) or re-scale the model as suggested in my previous comment.

    The same applies regarding the Warning

    Warning for adding variables: zero or small (< 1e-13) coefficients, ignored

    And at least, you have the option to update to v10 to profit from performance improvements and bug fixes.

    0
  • Suyue Xu
    Curious
    Gurobi-versary
    Conversationalist

    Thank you, Jaromil

    I will try to clean up very small coefficients and pay attention to the numeric issues.Thank you for your kindly comment again!

    0
  • Suyue Xu
    Curious
    Gurobi-versary
    Conversationalist

    Hi Jaromil

    Unfortunately the MILP model can find a solution in less than 10 min,but i'm still not satisfied with the efficiency.After I revised problems you mentioned above, it seems that the heuristics model find the solution from the beginning but it struggles to find the best bound.Here is the log:

    Set parameter Username
    Set parameter MIPGap to value 0.01
    Set parameter CrossoverBasis to value 0
    Set parameter MIPFocus to value 3
    Set parameter NodefileDir to value ""
    Set parameter NoRelHeurTime to value 20
    Set parameter Cuts to value 3
    Set parameter PreSOS2BigM to value 0
    Set parameter TuneTrials to value 3
    Academic license - for non-commercial use only - expires 2024-06-06
    Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)

    CPU model: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
    Thread count: 8 physical cores, 16 logical processors, using up to 16 threads

    Optimize a model with 33808 rows, 14585 columns and 315796 nonzeros
    Model fingerprint: 0x73e9d9e9
    Variable types: 8130 continuous, 6455 integer (6455 binary)
    Coefficient statistics:
      Matrix range     [3e-04, 1e+04]
      Objective range  [3e-01, 2e+02]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e-03, 1e+04]
    Presolve removed 29486 rows and 10511 columns
    Presolve time: 0.41s
    Presolved: 4322 rows, 4074 columns, 14508 nonzeros
    Variable types: 2510 continuous, 1564 integer (1564 binary)
    Starting NoRel heuristic
    Found phase-1 solution: relaxation 34839.7
    Found phase-1 solution: relaxation 34825.8
    Found phase-1 solution: relaxation 34536.8
    Found phase-1 solution: relaxation 34473.5
    Found phase-1 solution: relaxation 7818.41
    Found phase-1 solution: relaxation 7461.44
    Found phase-1 solution: relaxation 6905.05
    Found phase-1 solution: relaxation 6068.39
    Found phase-1 solution: relaxation 5208.38
    Found phase-1 solution: relaxation 2641.62
    Found phase-1 solution: relaxation 2615.4
    Found phase-1 solution: relaxation 2246.63
    Found phase-1 solution: relaxation 1988.52
    Found phase-1 solution: relaxation 1772.27
    Found phase-1 solution: relaxation 1718.13
    Found phase-1 solution: relaxation 1564.16
    Found phase-1 solution: relaxation 1451.22
    Found phase-1 solution: relaxation 1451.21
    Found phase-1 solution: relaxation 1450.87
    Found phase-1 solution: relaxation 1449.03
    Found phase-1 solution: relaxation 1449.01
    Found phase-1 solution: relaxation 1355.37
    Found phase-1 solution: relaxation 1292.59
    Found phase-1 solution: relaxation 1255.96
    Found phase-1 solution: relaxation 1252.97
    Found phase-1 solution: relaxation 1219.44
    Found phase-1 solution: relaxation 1057.55
    Found phase-1 solution: relaxation 954.437
    Found phase-1 solution: relaxation 937.607
    Found phase-1 solution: relaxation 880.965
    Found phase-1 solution: relaxation 814.701
    Found phase-1 solution: relaxation 807.84
    Found phase-1 solution: relaxation 799.182
    Found phase-1 solution: relaxation 765.258
    Found phase-1 solution: relaxation 704.463
    Found phase-1 solution: relaxation 680.014
    Found phase-1 solution: relaxation 676.414
    Found phase-1 solution: relaxation 645.723
    Found phase-1 solution: relaxation 645.72
    Found phase-1 solution: relaxation 642.346
    Found phase-1 solution: relaxation 629.765
    Found phase-1 solution: relaxation 616.697
    Found phase-1 solution: relaxation 604.417
    Found phase-1 solution: relaxation 600.956
    Found phase-1 solution: relaxation 578.192
    Found phase-1 solution: relaxation 574.722
    Found phase-1 solution: relaxation 574.717
    Found phase-1 solution: relaxation 502.014
    Found phase-1 solution: relaxation 501.626
    Found phase-1 solution: relaxation 493.187
    Found phase-1 solution: relaxation 493.184
    Found phase-1 solution: relaxation 473.362
    Found phase-1 solution: relaxation 473.076
    Found phase-1 solution: relaxation 473.075
    Found phase-1 solution: relaxation 472.934
    Found phase-1 solution: relaxation 472.647
    Found phase-1 solution: relaxation 462.699
    Found phase-1 solution: relaxation 462.695
    Found phase-1 solution: relaxation 439.008
    Found phase-1 solution: relaxation 436.682
    Found phase-1 solution: relaxation 320.432
    Found phase-1 solution: relaxation 318.201
    Found phase-1 solution: relaxation 313.778
    Found phase-1 solution: relaxation 313.19
    Found phase-1 solution: relaxation 313.073
    Found phase-1 solution: relaxation 312.901
    Found phase-1 solution: relaxation 311.792
    Found phase-1 solution: relaxation 308.126
    Found phase-1 solution: relaxation 285.554
    Found phase-1 solution: relaxation 279.175
    Found phase-1 solution: relaxation 278.367
    Found phase-1 solution: relaxation 271.357
    Found phase-1 solution: relaxation 229.721
    Found phase-1 solution: relaxation 131.886
    Found phase-1 solution: relaxation 108.55
    Found phase-1 solution: relaxation 108.537
    Found phase-1 solution: relaxation 108.221
    Found phase-1 solution: relaxation 108.22
    Found phase-1 solution: relaxation 108.207
    Found phase-1 solution: relaxation 108.207
    Found phase-1 solution: relaxation 107.663
    Found phase-1 solution: relaxation 86.6035
    Found phase-1 solution: relaxation 86.2127
    Found phase-1 solution: relaxation 83.6826
    Found phase-1 solution: relaxation 81.1013
    Found phase-1 solution: relaxation 77.1161
    Found phase-1 solution: relaxation 72.7764
    Found phase-1 solution: relaxation 68.3536
    Found phase-1 solution: relaxation 67.9194
    Found phase-1 solution: relaxation 64.1304
    Found phase-1 solution: relaxation 58.6391
    Found phase-1 solution: relaxation 58.1782
    Found phase-1 solution: relaxation 51.0738
    Found phase-1 solution: relaxation 50.327
    Found phase-1 solution: relaxation 47.7701
    Found phase-1 solution: relaxation 47.7316
    Found phase-1 solution: relaxation 47.4314
    Found phase-1 solution: relaxation 46.3485
    Found phase-1 solution: relaxation 45.761
    Found phase-1 solution: relaxation 42.9752
    Found phase-1 solution: relaxation 42.867
    Found phase-1 solution: relaxation 42.705
    Found phase-1 solution: relaxation 42.6603
    Found phase-1 solution: relaxation 42.4227
    Found phase-1 solution: relaxation 42.3405
    Found phase-1 solution: relaxation 36.7601
    Found phase-1 solution: relaxation 34.053
    Found phase-1 solution: relaxation 0
    Found heuristic solution: objective -2071.378493
    Transition to phase 2
    Found heuristic solution: objective -4318.593812
    Found heuristic solution: objective -6168.785979
    Found heuristic solution: objective -6248.871868
    Found heuristic solution: objective -6963.104062
    Found heuristic solution: objective -7138.650896
    Found heuristic solution: objective -8039.967780
    Found heuristic solution: objective -10902.59250
    Found heuristic solution: objective -12139.52933
    Found heuristic solution: objective -12219.61522
    Found heuristic solution: objective -15226.24593
    Found heuristic solution: objective -15241.18757
    Found heuristic solution: objective -16367.48261
    Found heuristic solution: objective -19389.05496
    Found heuristic solution: objective -21158.74883
    Found heuristic solution: objective -21353.13808
    Found heuristic solution: objective -22494.49922
    Found heuristic solution: objective -22814.05203
    Elapsed time for NoRel heuristic: 5s (best bound -85144.4)
    Found heuristic solution: objective -23036.66308
    Found heuristic solution: objective -23375.82982
    Found heuristic solution: objective -23375.82983
    Found heuristic solution: objective -23375.82985
    Elapsed time for NoRel heuristic: 10s (best bound -85144.4)
    Found heuristic solution: objective -23375.82986
    Elapsed time for NoRel heuristic: 15s (best bound -85144.4)
    Found heuristic solution: objective -23375.82986
    Elapsed time for NoRel heuristic: 22s (best bound -85144.4)
    Root relaxation presolve removed 1509 rows and 1509 columns
    Root relaxation presolved: 2813 rows, 2565 columns, 11488 nonzeros


    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0   -7.4861268e+05   4.108696e+06   0.000000e+00     22s
        1641   -8.5144387e+04   0.000000e+00   0.000000e+00     22s
        1673   -8.5144387e+04   0.000000e+00   0.000000e+00     22s
    Extra simplex iterations after uncrush: 32

    Root relaxation: objective -8.514439e+04, 1673 iterations, 0.06 seconds (0.05 work units)

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

         0     0 -85144.387    0  590 -23375.830 -85144.387   264%     -   23s
         0     0 -54204.462    0  785 -23375.830 -54204.462   132%     -   25s
         0     0 -54204.462    0  781 -23375.830 -54204.462   132%     -   25s
         0     0 -51715.194    0  753 -23375.830 -51715.194   121%     -   25s
         0     0 -51715.194    0  753 -23375.830 -51715.194   121%     -   25s
         0     0 -51713.960    0  738 -23375.830 -51713.960   121%     -   25s
         0     0 -51713.960    0  763 -23375.830 -51713.960   121%     -   25s
         0     0 -51571.622    0  737 -23375.830 -51571.622   121%     -   25s
         0     0 -51571.622    0  762 -23375.830 -51571.622   121%     -   25s
         0     0 -51571.622    0  765 -23375.830 -51571.622   121%     -   25s
         0     0 -49984.710    0  794 -23375.830 -49984.710   114%     -   27s
         0     0 -48896.257    0  802 -23375.830 -48896.257   109%     -   28s
         0     0 -48525.927    0  718 -23375.830 -48525.927   108%     -   30s
         0     0 -48525.927    0  721 -23375.830 -48525.927   108%     -   30s
         0     0 -46779.528    0  674 -23375.830 -46779.528   100%     -   30s
         0     0 -46779.409    0  671 -23375.830 -46779.409   100%     -   30s
         0     0 -46612.486    0  693 -23375.830 -46612.486  99.4%     -   30s
         0     0 -46576.799    0  710 -23375.830 -46576.799  99.3%     -   30s
         0     0 -45061.350    0  673 -23375.830 -45061.350  92.8%     -   33s
         0     0 -45051.543    0  691 -23375.830 -45051.543  92.7%     -   33s
         0     0 -44832.460    0  677 -23375.830 -44832.460  91.8%     -   35s
         0     0 -44832.460    0  677 -23375.830 -44832.460  91.8%     -   37s
         0     0 -44832.460    0  464 -23375.830 -44832.460  91.8%     -   38s
         0     0 -44832.460    0  568 -23375.830 -44832.460  91.8%     -   39s
    H    0     0                    -23375.82990 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  547 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  481 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  454 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  417 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  422 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44832.460    0  422 -23375.830 -44832.460  91.8%     -   39s
         0     0 -44475.327    0  486 -23375.830 -44475.327  90.3%     -   41s
         0     0 -43343.206    0  490 -23375.830 -43343.206  85.4%     -   41s
         0     0 -43343.206    0  472 -23375.830 -43343.206  85.4%     -   41s
         0     0 -42622.193    0  495 -23375.830 -42622.193  82.3%     -   43s
         0     0 -42113.386    0  513 -23375.830 -42113.386  80.2%     -   43s
         0     0 -42113.386    0  603 -23375.830 -42113.386  80.2%     -   43s
         0     0 -42062.210    0  604 -23375.830 -42062.210  79.9%     -   43s
         0     0 -41097.172    0  600 -23375.830 -41097.172  75.8%     -   44s
         0     0 -41097.172    0  600 -23375.830 -41097.172  75.8%     -   44s
         0     0 -40946.632    0  587 -23375.830 -40946.632  75.2%     -   44s
         0     0 -40660.983    0  590 -23375.830 -40660.983  73.9%     -   45s
         0     0 -40660.983    0  593 -23375.830 -40660.983  73.9%     -   45s
         0     0 -40579.997    0  619 -23375.830 -40579.997  73.6%     -   45s
         0     0 -40579.997    0  628 -23375.830 -40579.997  73.6%     -   45s
    H    0     0                    -23375.82994 -40560.103  73.5%     -   46s
         0     0 -40058.088    0  595 -23375.830 -40058.088  71.4%     -   46s
         0     0 -39940.870    0  607 -23375.830 -39940.870  70.9%     -   46s
         0     0 -39836.725    0  617 -23375.830 -39836.725  70.4%     -   46s
         0     0 -39667.372    0  596 -23375.830 -39667.372  69.7%     -   47s
         0     0 -39604.819    0  602 -23375.830 -39604.819  69.4%     -   47s
         0     0 -39351.534    0  579 -23375.830 -39351.534  68.3%     -   48s
         0     0 -39189.161    0  619 -23375.830 -39189.161  67.6%     -   48s
         0     0 -39014.825    0  640 -23375.830 -39014.825  66.9%     -   48s
         0     0 -39014.825    0  640 -23375.830 -39014.825  66.9%     -   48s
         0     0 -38944.425    0  631 -23375.830 -38944.425  66.6%     -   49s
         0     0 -38887.376    0  630 -23375.830 -38887.376  66.4%     -   50s
         0     2 -38887.376    0  630 -23375.830 -38887.376  66.4%     -   51s
        57    49 infeasible    9      -23375.830 -38285.425  63.8%  1216   55s
       207   166 -37151.344   14  462 -23375.830 -37151.344  58.9%   827   60s
       366   329 -35780.082   18  324 -23375.830 -36641.835  56.8%   658   65s
       908   774 -35073.179   13  496 -23375.830 -36205.118  54.9%   468   70s
    H  920   774                    -23375.82999 -36193.893  54.8%   468   70s
      1359  1182 -35345.520   16  364 -23375.830 -35781.545  53.1%   454   75s
      1480  1185 -35620.140   20  443 -23375.830 -35732.148  52.9%   440   81s
      1492  1193 -33575.356   18  558 -23375.830 -35732.148  52.9%   437   89s
      1498  1197 -33230.431   22  565 -23375.830 -35732.148  52.9%   435   91s
      1499  1198 -30087.971   13  528 -23375.830 -35732.148  52.9%   435   95s
      1504  1201 -33219.850   22  538 -23375.830 -35732.148  52.9%   433  102s
      1510  1205 -32609.905   27  577 -23375.830 -34912.325  49.4%   432  105s
      1517  1210 -34346.471   14  554 -23375.830 -34346.471  46.9%   430  110s
      1521  1212 -33896.066   17  529 -23375.830 -33896.066  45.0%   429  115s
      1524  1214 -33759.697   17  576 -23375.830 -33759.697  44.4%   428  121s
      1530  1218 -33174.026   18  527 -23375.830 -33174.026  41.9%   426  127s
      1534  1221 -28235.239   16  545 -23375.830 -32660.098  39.7%   425  133s
      1538  1224 -32471.002   23  545 -23375.830 -32471.002  38.9%   424  135s
      1543  1227 -31821.621   15  567 -23375.830 -31821.621  36.1%   422  142s
      1547  1230 -31660.990   19  530 -23375.830 -31660.990  35.4%   421  147s
      1552  1233 -31369.953   14  523 -23375.830 -31369.953  34.2%   420  150s
      1557  1236 -31285.659   16  515 -23375.830 -31285.659  33.8%   419  155s
      1565  1242 -30641.469   20  555 -23375.830 -30776.959  31.7%   417  161s
      1566  1242 -30734.749   26  546 -23375.830 -30734.749  31.5%   416  165s
      1576  1249 -30562.352   16  547 -23375.830 -30562.352  30.7%   414  170s
      1580  1252 -30365.167   20  534 -23375.830 -30365.167  29.9%   413  176s
      1587  1256 -30173.546   22  572 -23375.830 -30173.546  29.1%   411  180s
      1593  1260 -30128.904   20  564 -23375.830 -30128.904  28.9%   409  185s
      1601  1266 -30037.731   21  502 -23375.830 -30037.731  28.5%   407  191s
      1610  1272 -29814.656   27  519 -23375.830 -29814.656  27.5%   405  195s
      1615  1275 -29633.881   14  518 -23375.830 -29633.881  26.8%   404  200s
      1621  1280 -29633.881   17  379 -23375.830 -29633.881  26.8%   464  205s
      1632  1287 -29633.881   21  486 -23375.830 -29633.881  26.8%   461  210s
      1638  1291 -29633.881   23  503 -23375.830 -29633.881  26.8%   459  216s
      1640  1293 -29633.881   17  515 -23375.830 -29633.881  26.8%   458  221s
      1645  1296 -29633.881   21  499 -23375.830 -29633.881  26.8%   457  228s
      1648  1298 -29633.881   17  522 -23375.830 -29633.881  26.8%   456  231s
      1650  1299 -29633.881   21  504 -23375.830 -29633.881  26.8%   456  235s
      1654  1302 -29633.881   22  518 -23375.830 -29633.881  26.8%   454  240s
      1661  1307 -29633.881   20  510 -23375.830 -29633.881  26.8%   453  246s
      1663  1308 -29633.881   22  493 -23375.830 -29633.881  26.8%   452  263s
      1667  1312 -29633.881   18  392 -23375.830 -29633.881  26.8%   472  265s
      1678  1320 -29633.881   16  489 -23375.830 -29633.881  26.8%   469  271s
      1680  1321 -29633.881   20  493 -23375.830 -29633.881  26.8%   468  275s
      1683  1323 -29633.881   14  490 -23375.830 -29633.881  26.8%   468  302s
      1687  1327 -29633.881   41  390 -23375.830 -29633.881  26.8%   479  305s
      1749  1340 -29633.881   47  391 -23375.830 -29633.881  26.8%   506  310s
      1813  1364 -29633.881   51  351 -23375.830 -29633.881  26.8%   533  315s
      1878  1389 -29199.202   53  316 -23375.830 -29633.881  26.8%   568  320s
      1929  1411 -29011.725   54  351 -23375.830 -29225.418  25.0%   589  325s
      2023  1462 -26982.495   53  302 -23375.830 -28469.300  21.8%   619  330s
      2157  1499 -24067.149   56  283 -23375.830 -27846.488  19.1%   640  336s
      2273  1504 -25726.303   55  310 -23375.830 -27432.426  17.4%   669  341s
    H 2308  1429                    -23375.83000 -27298.528  16.8%   680  344s
      2319  1435 -25933.386   57  294 -23375.830 -27270.183  16.7%   686  346s
      2483  1389 -26170.034   56  275 -23375.830 -26773.903  14.5%   710  351s
      2694  1326     cutoff   55      -23375.830 -26164.120  11.9%   730  356s
      2871  1254 -24862.156   61  237 -23375.830 -25764.787  10.2%   732  360s
      3172  1102 infeasible   62      -23375.830 -25025.324  7.06%   729  367s
      3311  1017     cutoff   60      -23375.830 -24614.620  5.30%   726  371s
      3672   833     cutoff   65      -23375.830 -23989.853  2.63%   699  375s

    Cutting planes:
      Learned: 1
      Gomory: 4
      Lift-and-project: 115
      Cover: 506
      Implied bound: 508
      Projected implied bound: 10
      Clique: 1679
      MIR: 876
      StrongCG: 8
      Flow cover: 2199
      Zero half: 87
      Network: 6
      RLT: 489
      Relax-and-lift: 402
      BQP: 74
      PSD: 14

    Explored 3983 nodes (2705378 simplex iterations) in 377.83 seconds (467.16 work units)
    Thread count was 16 (of 16 available processors)

    Solution count 10: -23375.8 -23375.8 -23375.8 ... -23036.7

    Optimal solution found (tolerance 1.00e-02)
    Best objective -2.337583000142e+04, best bound -2.355547955495e+04, gap 0.7685%

    Before the reformulation of the model,is there any possible way to improve the best bound?What' more,the log ends with arrays of 'infeasible' and 'cutoff',is this message indicate why the model moves very slow?

    Thanks in advance!

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Before the reformulation of the model,is there any possible way to improve the best bound?

    You could try combinations of the following parameters:

    Is there a particular reason why you set PreSOS2BigM?

    What' more, the log ends with arrays of 'infeasible' and 'cutoff', is this message indicate why the model moves very slow?

    These are actually good messages. This means that the current node has been cutoff or that it is infeasible. This leads to a smaller tree which is good.

    If nothing of this helps, I think that the last resort would be a stronger formulation. Maybe our Tech Talk on converting weak to strong MIP formulation is helpful.

    0

Please sign in to leave a comment.