optimization - 在 MIP 求解器 (Gurobi) 中保持切割而不分支

Question

我有一个 MIP，我几乎可以肯定地知道它的解决方案。我想用 gurobi 来证明真正的解决方案(即使它不是我提供的)与我给出的解决方案的偏差不应超过 0.5%。我相信简单地保持切割而不分枝可能会节省更多时间。你知道我可以在 gurobi 中简单地进行切割而不分支的方法吗？这是代码性能:

将参数 LogFile 的值更改为 上一个:gurobi.log 默认值:将参数 MIPFocus 的值更改为 3 上一个:0 最小值:0 最大值:3 默认值:0将参数 Cuts 的值更改为 3 上一个:-1 最小值:-1 最大值:3 默认值:-1优化具有 1794 行、673 列和 4180 个非零值的模型找到启发式解决方案:目标 -22.8549Presolve去掉了18行17列预解析时间:0.01s预求解:1776 行，656 列，4464 个非零值

加载的 MIP 从目标 -342.641 开始

变量类型:592个连续型，64个整数(64个二进制)预求解:1776 行，656 列，4464 个非零值

根松弛:目标-6.775689e+02，迭代682次，0.02秒

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

     0     0 -677.56892    0   64 -342.64109 -677.56892  97.7%     -    0s
     0     0 -666.45290    0   72 -342.64109 -666.45290  94.5%     -    0s
     0     0 -658.68050    0   72 -342.64109 -658.68050  92.2%     -    1s
     0     0 -540.92023    0   72 -342.64109 -540.92023  57.9%     -    3s
     0     0 -503.36031    0   72 -342.64109 -503.36031  46.9%     -    4s
     0     0 -485.13025    0   72 -342.64109 -485.13025  41.6%     -    6s
     0     0 -472.73790    0   72 -342.64109 -472.73790  38.0%     -    8s
     0     0 -461.23185    0   72 -342.64109 -461.23185  34.6%     -    9s
     0     0 -453.99476    0   72 -342.64109 -453.99476  32.5%     -   10s

     0     0 -452.23014    0   72 -342.64109 -452.23014  32.0%     -   10s
     0     3 -452.23014    0   72 -342.64109 -452.23014  32.0%     -   11s
   642   586 -397.07656   12   54 -342.64109 -429.76289  25.4%   120   15s
  1425  1290 -397.34606   11   60 -342.64109 -422.53417  23.3%   114   20s
  1716  1553 -382.83438   18   72 -342.64109 -420.42709  22.7%   111   25s
  1727  1560 -376.17473   16   72 -342.64109 -420.42709  22.7%   110   30s
  1733  1564 -410.28764   10   72 -342.64109 -420.42709  22.7%   110   35s
  1744  1571 -382.83438   18   72 -342.64109 -420.42709  22.7%   109   40s
  1750  1577 -412.59771   12   69 -342.64109 -416.84728  21.7%   113   45s
  1817  1602 -380.32997   19   60 -342.64109 -404.73090  18.1%   120   50s
  2618  2045 -375.99924   18   62 -342.64109 -391.32863  14.2%   126   55s
  3159  2315 -369.40052   22   59 -342.64109 -386.33088  12.8%   127   60s
  3808  2595 -362.27693   20   60 -342.64109 -382.29310  11.6%   127   65s
  4503  2903 -350.90325   24   54 -342.64109 -379.52932  10.8%   126   71s
  4895  3078 -349.90847   23   55 -342.64109 -378.33598  10.4%   126   78s
  5339  3242 -363.26836   21   59 -342.64109 -376.77299  10.0%   126   80s

....

Answer 1

为了避免在 Gurobi (Cplex) 中出现分支，您可以将参数 NodeLimit (Cplex 中的 NodLim) 设置为 1。要完成您最终想要的，只需验证您的解决方案在 0.5% 或最优范围内，您可以加载已知的作为一种解决方案(mip 开始，正如你已经在做的那样)设置 MIPFocus参数设置为 3(移动边界)并将 MIPGap 参数设置为 0.005，这将使 Gurobi(cplex)在找到所需条件时停止。

如果您确信您的解决方案比求解器找到的任何解决方案都要好，那么您也可以关闭启发式算法，使用 Heuristics范围。 Gurobi 通常会花费大约 5% 的时间来寻找更好的解决方案，除非它找到的任何解决方案比您提供的现有解决方案更好，否则这将无济于事。在 Cplex 中，参数为 HeurFreq ，您将其设置为 -1 以关闭。

您可能还会打开可以改善边界的预求解，尤其是在根处。尝试调出 Presolve到 2，PreDual到 2。还有一个 Symmetry在根部进行额外缩减的参数。通常默认设置是最好的，但在您的情况下，它们可能至少值得尝试。

仅对于 CPLEX，有一个 Probing参数，您可以将其设置为 3。这通常会减慢求解时间，但也可能会改善根部的边界。