2

我有一个线性 MIP 问题，Gurobi 在 10 次迭代中找到了解决方案。
要真正证明解决方案是最优的，需要更多的时间。
日志如下。

有没有办法让 Gurobi 停下来？

我尝试了自动调整工具。
它告诉我设置Heuristics=0.
如果我遵循这个建议，找到解决方案的总运行时间会减少。
但是这个总时间远远超过启发式算法的 10 次迭代的时间。

我是 MIP 的新手，所以，从日志中，我真的不知道哪个参数将是一个好的停止标准 (GAP, BestBound, ...) 。

Optimize a model with 434 rows, 380 columns and 1332 nonzeros
Found heuristic solution: objective -0.667665
Presolve removed 74 rows and 72 columns
Presolve time: 0.00s
Presolved: 360 rows, 308 columns, 1428 nonzeros
Variable types: 188 continuous, 120 integer (120 binary)

Root relaxation: objective 1.454681e+00, 383 iterations, 0.00 seconds

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

     0     0    1.45468    0   80   -0.66764    1.45468   318%     -    0s
H    0     0                      -0.2958055    1.45468   592%     -    0s
     0     0    1.33723    0   87   -0.29581    1.33723   552%     -    0s
H    0     0                      -0.0360081    1.33723  3814%     -    0s
     0     0    1.32350    0   88   -0.03601    1.32350  3776%     -    0s
     0     0    1.31284    0   62   -0.03601    1.31284  3746%     -    0s
     0     5    1.31284    0   62   -0.03601    1.31284  3746%     -    0s
H  407   237                      -0.0223424    1.12204  5122%  13.3    0s
H  606   348                      -0.0139589    1.09397  7937%  12.8    0s
H 1209   691                       0.0000905    1.00647     -   12.2    0s
H 1543   852                       0.0000935    1.00647     -   15.4    1s
 12464  8280    0.31259   37   45    0.00009    0.83003     -   16.1    5s
 32517 21750     cutoff   44         0.00009    0.75633     -   15.8   10s
 41026 27530    0.15234   45   67    0.00009    0.40720     -   15.7   15s
 67008 28123    0.00079   87    9    0.00009    0.00252  2599%  12.1   20s
 123660 32561    0.00088   82   13    0.00009    0.00197  2008%   8.0   25s
 183205 53085    0.00111   80   14    0.00009    0.00175  1766%   6.5   30s
 242669 70749    0.00115   82   13    0.00009    0.00160  1611%   5.6   35s
 300464 86096    0.00016   83   14    0.00009    0.00150  1499%   5.2   40s
 360002 99530    0.00116   77   12    0.00009    0.00141  1407%   4.8   45s
 419747 111348    0.00092   82   11    0.00009    0.00134  1330%   4.5   50s
 479404 121404    0.00094   78   18    0.00009    0.00128  1265%   4.4   55s
 538670 130127    0.00061   86    9    0.00009    0.00122  1206%   4.2   60s
 599541 137721    0.00071   87   10    0.00009    0.00117  1152%   4.1   65s
 659419 143977    0.00049   81   13    0.00009    0.00113  1104%   4.0   70s
 719366 148872    0.00090   82    7    0.00009    0.00108  1058%   3.9   75s
 778800 152645     cutoff   81         0.00009    0.00104  1015%   3.8   80s
 838419 155900    0.00064   82   12    0.00009    0.00101   975%   3.7   85s
 898257 157892    0.00038   82   11    0.00009    0.00097   937%   3.7   90s
 959133 158950    0.00064   82    9    0.00009    0.00093   898%   3.6   95s
 1019118 158672     cutoff   86         0.00009    0.00090   863%   3.6  100s
 1077389 157263    0.00034   79   16    0.00009    0.00087   828%   3.5  105s
 1136559 154819    0.00015   83    6    0.00009    0.00084   795%   3.5  110s
 1197408 151286    0.00033   79   11    0.00009    0.00080   760%   3.5  115s
 1256981 146998    0.00058   85   11    0.00009    0.00077   726%   3.4  120s
 1315053 141986    0.00015   87    9    0.00009    0.00074   693%   3.4  125s
 1369901 136123     cutoff   84         0.00009    0.00071   662%   3.4  130s
 1423732 129573    0.00042   84   11    0.00009    0.00068   631%   3.3  135s
 1483143 120871    0.00036   86   11    0.00009    0.00065   593%   3.3  140s
 1541197 111293    0.00020   84   11    0.00009    0.00061   553%   3.3  145s
 1598804 100832    0.00030   81   15    0.00009    0.00057   511%   3.3  150s
 1655909 89315    0.00039   84   11    0.00009    0.00053   466%   3.2  155s
 1704245 77614    0.00018   82   15    0.00009    0.00049   420%   3.2  160s
 1750024 63910    0.00014   83   12    0.00009    0.00044   367%   3.2  165s
 1795438 46988     cutoff   78         0.00009    0.00037   299%   3.2  170s
 1847433 21718    0.00012   82   10    0.00009    0.00026   178%   3.2  175s

Cutting planes:
  Gomory: 54
  MIR: 14
  Flow cover: 28

Explored 1875647 nodes (5924527 simplex iterations) in 178.11 seconds
Thread count was 4 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 9.353429694370e-05, best bound 9.353429694481e-05, gap 0.0%
4

2 回答 2

4

如果你想证明解是最优的，不要提前终止。参数调整工具非常有用，grbtune但看起来你可以通过专注于移动边界来做得更好。有关如何移动边界的建议，请参阅参数调整指南的MIP 部分。例如，我会尝试增加Cuts参数，设置MIPFocus为 2 或 3，和/或设置Presolve为 2。

免责声明：我负责 Gurobi 技术支持。

于 2014-02-19T04:04:57.983 回答
2

我只想添加一些解释：

Gurobi 启发式算法在 10 次迭代中找到了解决方案。不能保证这个解决方案是最优的，特别是剩下的时间都花在证明这一点上。

通过禁用启发式，所述解决方案（只是）稍后发现。建议的参数设置在这方面是成功的，即减少了整体运行时间（可用的解决方案并被证明是最佳的）（即使实际解决方案稍后可用）。

正如上面的 Greg Glockner 所指出的，由于大部分时间都花在证明您的解决方案的最优性上，因此将重点/重点放在这可能会加快您的解决方案时间。您也可以定义停止标准，我设置 Toleranze/Gap 参数，如此处所述。

于 2014-02-26T10:26:55.950 回答