是否有一个整数线性规划软件也返回非最佳解决方案？
我有一个整数线性优化问题，我对可行、好的解决方案感兴趣。据我所知，例如 Gnu 线性编程套件仅返回最佳解决方案（假设它存在）。 这需要无尽的时间，而且不完全是我正在寻找的：我会对任何好的解决方案感到满意，而不仅仅是最佳的解决方案。
因此，LP 求解器在一段时间后停止并返回迄今为止找到的最佳解决方案，就可以完成这项工作。
有这样的软件吗？如果该软件是开源的或者至少像啤酒一样免费，那就太好了。
或者：是否有其他方法通常可以加速整数 LP 问题？ 这是问的正确地方吗？
I have an integer linear optimisation problem and I'm interested in feasible, good solutions. As far as I know, for example the Gnu Linear Programming Kit only returns the optimal solution (given it exists).
This takes endless time and is not exactly what I'm looking for: I would be happy with any good solution, not only the optimal one.
So a LP-Solver that e.g. stops after some time and returns the best solution he found so far, would do the job.
Is there any such software? It would be great if that software was open source or at least free as in beer.
Alternatively: Is there any other way that usually speeds up Integer LP problems?
Is this the right place to ask?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果您想快速获得可行的整数解，并且不需要最优解，则可以尝试
增加相对或绝对差距。通常求解器的相对间隙较小，例如 0.0001%。这意味着求解器将继续搜索 MIP 解，直到 MIP 解与最优解的距离不超过 0.0001%。将此 gab 增加到例如 1%。这样您就得到了好的解，但求解器不会花费很长时间来证明最优性。
尝试有关MIP 启发式的求解器参数的不同值。
CPLEX 和 GUROBI 有参数可以控制，MIP 重点。这意味着求解器将更加注重寻找可行的解决方案或证明最优性。将重点放在可行的 MIP 解决方案上。
大多数求解器（例如 CPLEX、Gurobi、MOPS 或 GLPK）都具有间隙和启发式设置。据我所知，MIP 重点只能在 CPLEX 和 Gurobi 中设置。
If you would like to get a feasibel integer solution fast and if you don't need the optimal solution, you can try
Increase the relative or absolute Gap. Usually solvers have small gaps of say 0.0001% for relative gap. This means that the solver will continue searching for MIP solutions until it the MIP solution is not farther than 0.0001% away from the optimal solution. Increase this gab to e.g. 1%., So you get good solution, but the solver will not spent a long time in proving optimality.
Try different values for solver parameters concerning MIP heuristics.
CPLEX and GUROBI have parameters to control, MIP emphasis. This means that the solver will put more emphasis on looking for feasible solutions or on proving optimality. Set emphasis to feasible MIP solutions.
Most solvers like CPLEX, Gurobi, MOPS or GLPK have settings for gap and heuristics. MIP emphasis can be set - as far as I know - only in CPLEX and Gurobi.
解决 ILP 的常用方法是分支定界。这利用了许多子LP（无-I）的解决方案。最终的最优结果是所有子LP中最好的。由于至少找到了一种解决方案，因此您可以随时停止并获得迄今为止最好的解决方案。
一个可以做到这一点的软件包是免费的 lpsolve。查看 set_timeout 给出时间限制，当 ILP 时，求解函数可以在 SUPPTIMAL 中返回 best_so_far 值。
A usual approach for solving ILP is branch-and-bound. This utilized the solution of many sub-LP (without-I). The finally optimal result is the best of all sub-LP. As at least one solution is found you could stop anytime and would have a best-so-far.
One package that could do it, is the free lpsolve. Look there at set_timeout for giving a time limit, and when it is ILP the solve function can return in SUPOPTIMAL the best_so_far value.
据我所知CPLEX可以。它可以返回包含搜索中原始可行解的解池，如果指定搜索侧重于可行性而不是最优性，则可以生成更可行的解。最后你可以导出池。您可以使用游泳池进行热启动，因此这完全取决于您。 CPlex 现在至少在我国是免费的，因为您可以注册成为研究员。
As far as I know CPLEX can. It can return the solution pool which contains primal feasible solutions in the search, and if you specify the search focus on feasibility rather on optimality, more faesible solutions can be generated. At the end you can just export the pool. You can use the pool to do a hot start so it's pretty up to you. CPlex is free now at least in my country as you can sign up as a researcher.
您能考虑一下 Microsoft Solver Foundation 吗？唯一的限制是您喜欢的技术堆栈，正如您猜测的那样，您应该使用 Microsoft 技术：C#、vb.net 等。以下是如何在 Excel 中使用它的示例：http://channel9.msdn.com/posts/Modeling-with-Solver-Foundation-30 。
关于您的问题，如果您设置效率（例如 85% 或 0.85），则可能没有完全优化的解决方案。在结果中，您可以看到此类限制的所有可能解决方案。
Could you take into account Microsoft Solver Foundation? The only restriction is technology stack that you prefer and here you should use, as you guess, Microsoft technologies: C#, vb.net, etc. Here is example how to use it with Excel: http://channel9.msdn.com/posts/Modeling-with-Solver-Foundation-30 .
Regarding to your question it is possible to have not a fully optimized solutions if you set efficiency (for example 85% or 0.85). In outcome you can see all possible solutions for such restriction.
许多求解器提供时间限制参数；如果您设置了时间限制参数，则一旦达到时间限制，它们就会停止。如果找到了整数可行解，它将返回到该点找到的最佳可行解。
如您所知，整数规划是 NP 困难的，并且快速找到最佳解决方案以及良好的可行解决方案是一门真正的艺术。要比较不同的求解器，请参阅 Hans Mittelmann 教授的优化软件基准。 MILP 基准 - 特别是 MIPLIB2010 和可行性基准应该是最相关的。
除了选择好的求解器之外，还可以采取许多措施来缩短求解时间，包括调整求解器的参数和重新制定模型。研究和工业界的许多人（包括我自己）都将我们的职业生涯致力于提高 MIP 模型的求解时间，无论是一般模型还是特定模型。
如果您是学术用户，请注意，CPLEX 和 Gurobi 等顶级商业系统可免费供学术使用。详情请参阅各自的网站。
最后，您可能需要查看 OR-Exchange，它是 Stack Overflow 的姊妹网站，专注于运筹学领域。
（免责声明：我目前在 Gurobi Optimization 工作，之前在 ILOG 工作，该公司提供 CPLEX）。
Many solvers provide a time limit parameter; if you set the time limit parameter, they will stop once the time limit is reached. If an integer feasible solution has been found, it will return the best feasible solution found to that point.
As you may know, integer programming is NP-hard, and there is a real art to finding optimal solutions as well as good feasible solutions quickly. To compare the different solvers, see Prof. Hans Mittelmann's Benchmarks for Optimization Software. The MILP benchmarks - particularly MIPLIB2010 and the Feasibility Benchmark should be most relevant.
In addition to selecting a good solver, there are many things that can be done to improve solve times including tuning the parameters of the solver and model reformulation. Many people in research and industry - including myself - spend our careers working on improving the solve times of MIP models, both in general and for specific models.
If you are an academic user, note that the top commercial systems like CPLEX and Gurobi are free for academic use. See the respective websites for details.
Finally, you may want to look at OR-Exchange, a sister site to Stack Overflow that focuses on the field of operations research.
(Disclaimer: I currently work for Gurobi Optimization and formerly worked for ILOG, which provided CPLEX).