3

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

将参数 LogFile 的值更改为 Prev：gurobi.log 默认值：将参数 MIPFocus 的值更改为 3 Prev：0 最小值：0 最大值：3 默认值：0 将参数 Cuts 的值更改为 3 Prev：-1 最小值：-1 最大值：3默认值：-1 优化具有 1794 行、673 列和 4180 个非零值的模型 找到启发式解决方案：目标 -22.8549 预求解删除 18 行和 17 列预求解时间：0.01 秒预求解：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

……

4

1 回答 1

3

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

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

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

仅对于 CPLEX，有一个Probing参数，您可以将其设置为 3。平均而言，这会减慢求解时间，但也可能会改善您在根处的界限。

于 2014-07-20T19:10:27.433 回答