我有一个整数线性优化问题，我对可行的、好的解决方案感兴趣。据我所知，例如 Gnu 线性规划工具包只返回最优解（假设它存在）。这需要无穷无尽的时间，而且并不是我正在寻找的：我会对任何好的解决方案感到满意，而不仅仅是最佳解决方案。
因此，例如在一段时间后停止并返回他迄今为止找到的最佳解决方案的 LP-Solver 将完成这项工作。
有没有这样的软件？如果该软件是开源的，或者至少像啤酒一样免费，那就太好了。
或者：有没有其他方法通常可以加速整数 LP 问题？请问这个地方合适吗？
问问题
2223 次
5 回答
8
许多求解器提供时间限制参数；如果您设置了时间限制参数，一旦达到时间限制，它们将停止。如果找到了整数可行解，它将返回找到的最佳可行解。
您可能知道，整数规划是 NP 难的，快速找到最佳解决方案和可行的解决方案是一门真正的艺术。要比较不同的求解器，请参阅 Hans Mittelmann 教授的优化软件基准。MILP 基准——尤其是 MIPLIB2010 和可行性基准应该是最相关的。
除了选择一个好的求解器外，还有很多事情可以做来缩短求解时间，包括调整求解器的参数和模型重构。包括我自己在内的许多研究和工业界人士都致力于改善 MIP 模型的求解时间，无论是一般模型还是特定模型。
如果您是学术用户，请注意 CPLEX 和 Gurobi 等顶级商业系统可免费用于学术用途。有关详细信息，请参阅各自的网站。
最后，您可能想看看OR-Exchange，它是 Stack Overflow 的姊妹网站，专注于运筹学领域。
（免责声明：我目前在 Gurobi Optimization 工作，之前曾在提供 CPLEX 的 ILOG 工作）。
于 2011-10-06T23:20:51.393 回答
4
如果您想快速获得 feasibel 整数解，并且不需要最优解，可以尝试
增加相对或绝对 Gap。通常求解器的相对差距有 0.0001% 的小差距。这意味着求解器将继续搜索 MIP 解，直到 MIP 解与最优解的距离不超过 0.0001%。将此 gab 增加到例如 1%。，因此您得到了很好的解决方案，但求解器不会花费很长时间来证明最优性。
为有关MIP 启发式的求解器参数尝试不同的值。
CPLEX 和 GUROBI 有参数控制，MIP 强调。这意味着求解器将更加重视寻找可行的解决方案或证明最优性。将重点放在可行的 MIP 解决方案上。
CPLEX、Gurobi、MOPS 或 GLPK 等大多数求解器都有间隙和启发式设置。据我所知，只能在 CPLEX 和 Gurobi 中设置 MIP 重点。
于 2013-02-04T09:26:48.687 回答
1
解决 ILP 的常用方法是分支定界。这利用了许多子LP（没有-I）的解决方案。最终的最优结果是所有子 LP 中最好的。至少找到一种解决方案后，您可以随时停止，并获得迄今为止最好的解决方案。
一个可以做到这一点的软件包是免费的 lpsolve。查看 set_timeout 以获得时间限制，当它是 ILP 时，求解函数可以在 SUPOPTIMAL 中返回 best_so_far 值。
于 2011-10-06T08:45:05.927 回答
1
据我所知CPLEX可以。它可以在搜索中返回包含原始可行解决方案的解决方案池，如果您将搜索重点放在可行性而不是最优性上，则可以生成更多可行的解决方案。最后，您可以导出池。您可以使用游泳池进行热启动，这完全取决于您。CPlex 现在至少在我的国家是免费的，因为您可以注册成为研究人员。
于 2012-08-03T01:59:52.323 回答
0
你能考虑微软解算器基金会吗？唯一的限制是您喜欢的技术堆栈，在这里您应该使用 Microsoft 技术：C#、vb.net 等。这里是如何在 Excel 中使用它的示例：http: //channel9.msdn.com/帖子/建模与求解器基础 30。
关于您的问题，如果您设置效率（例如 85% 或 0.85），则可能没有完全优化的解决方案。结果，您可以看到此类限制的所有可能解决方案。
于 2011-10-06T08:20:23.657 回答