我有一个整数线性规划问题，我尝试过的求解器(CPLEX、CBC)需要很长时间才能解决，即使它们很早就找到了最优解。他们只是需要很长时间才能完全证明这一点。
很容易为我的最小化问题的目标值计算一个微不足道的下界，但在 CPLEX 的输出(最佳界列)中我可以看到它甚至在很长很长一段时间内都没有接近。它几乎立即找到了非常好的解决方案，但它错误地认为最佳解决方案可能会更好。
现在我不得不承认我真的不知道这些求解器是如何工作的，但看起来它们正在浪费时间尝试改进可笑的弱下限，寻找不可能乐观的解决方案。所以我的问题是:
是否可以告诉求解器目标的合理下限有助于它更快地运行？
如果是这样，哪些求解器可以接受作为附加输入提供的已知下限？
作为说明，我粘贴了示例运行中 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 的解决方案(因为我可以用更简单的方法证明这一点)，尤其是目标值为负的情况下(因为这在我的系统中是不可能的)型号)。
最佳答案
如果您有一个很好的下限，从一个可行的解决方案，您可以将其作为 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
关于mathematical-optimization - 建议 ILP 求解器的下限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40048946/