3

我有一个整数线性规划问题，我尝试过的求解器（CPLEX、CBC）需要很长时间才能解决，即使他们很早就找到了最优解。他们只需要永远充分证明这一点。

为我的最小化问题的目标值计算一个微不足道的下限很容易，但在 CPLEX 的输出（Best Bound 列）中，我可以看到它甚至在很长很长时间内都没有接近。它几乎可以立即找到非常好的解决方案，但它错误地认为最佳解决方案可能会好得多。

现在我不得不承认我真的不知道这些求解器是如何工作的，但看起来他们正在浪费时间试图改进可笑的弱下限，寻找不可能乐观的解决方案。所以我的问题是：

  1. 告诉求解器一个不错的目标下限可以帮助它更快地运行吗？

  2. 如果是这样，哪些求解器可以接受作为附加输入提供的已知下限？

作为说明，我粘贴了示例运行中 CPLEX 输出的前几行（运行时间更长，目标没有任何进一步的改进，最佳界限的改进也非常缓慢）：

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
      0     0     -388.6997   178                   -388.6997        9
*     0+    0                          297.0000     -388.6997        9  230.88%
*     0+    0                          275.0000     -388.6997        9  241.35%
      0     2     -388.6997   178      275.0000     -387.8106        9  241.02%
*    20+   20                          185.0000     -307.6363       80  266.29%
*    30+   30                          135.0000     -307.6363       90  327.88%
*    30+   30                           94.0000     -307.6363       90  427.27%
*    60+   60                           90.0000     -307.6363      120  441.82%
*   160+  126                           77.0000     -307.6363      272  499.53%
*   200+   93                           12.0000     -307.4836      325     ---
    300   182     -135.2988   107       12.0000     -268.6638      466     ---
   1200   934      -50.6022    85       12.0000     -206.2938     1480     ---
   2197  1755      -96.9612    93       12.0000     -189.8013     2470     ---
   3226  2600       -2.8316    87       12.0000     -179.9669     3480     ---
   4374  3521     -156.2442   110       12.0000     -170.4183     4567     ---
   5490  4421     -128.0871    97       12.0000     -167.3696     5623     ---
   6971  5603     -147.5022   108       12.0000     -162.4180     7055     ---
   8739  6997     -103.5374   113       12.0000     -156.3532     8673     ---

我希望我可以告诉求解器不要费心寻找目标低于 10 的解决方案（因为我可以用更简单的方法证明这一点），尤其是没有负目标值的解决方案（因为在我的模型中甚至不可能）。

4

1 回答 1

1

如果您有一个良好的下限，则可以从可行的解决方案中将其作为 MIP 开始提供给 CPLEX。

然后，CPLEX 将尝试改进该解决方案并忽略其分支定界算法中边界低于该值的任何分支。

您可以在此处查看更多详细信息： https ://www.ibm.com/support/knowledgecenter/SS9UKU_12.5.0/com.ibm.cplex.zos.help/UsrMan/topics/discr_optim/mip/para/49_mipStarts.html

于 2017-02-17T16:25:16.797 回答