修改约束的RHS(GLPK)时会发生什么? [英] What happens when I modified the RHS of a constraint (GLPK)?

问题描述

我正在提高，使GLPK的MIP问题的约束小于或等于RHS.但是，有时，在重新优化之后，GLPK无法在时限内找到任何可行的解决方案.因此，我猜测它不会检查先前的解决方案是否可行.有人对此有经验吗?还是可以将我指向不是源代码本身的文档?

I am increasing the RHS of less-than-or-equal constraint of a MIP problem with GLPK. However, sometimes, after re-optimizing, GLPK cannot find any feasible solution within the time limit. So I am guessing it does not check if the previous solution was feasible. Does anybody have any experience with that? Or can point me to a document that is not the source code itself?

此外，我想在为其他任何求解器(例如Gurobi，Cplex，SCIP，CBC)添加约束后知道什么工作流程，因此任何信息都将对您有所帮助.

Also, I would like to know what is the workflow after I add a constraint for any other solver (e.g. Gurobi, Cplex, SCIP, CBC) so any information is helpful.

干杯！

推荐答案

更改模型中的某些内容后，通常会丢弃所有求解信息，并从头开始解决问题.即使您已解决问题，但这并不一定意味着它更容易解决MIP求解器，特别是，它可能始终会导致不同的LP解决方案，从而导致不同的分支，从不同的起点开始的原始启发式方法，并且最终倒霉.因此，最后，您可能只是不幸的是，求解器现在花费的时间更长.

After changing something in the model, all solving information is typically discarded and the problem is solved from scratch. Even though you relaxed the problem, this does not necessarily mean that it is easier to solve for a MIP solver, in particular, it may always lead to different LP solutions, that cause different branching, primal heuristic start from a different starting point and are unlucky in the end. So in the end, you might just be unlucky that the solver takes longer now.

在MIP求解器中执行"warmstart"非常困难. SCIP提供了此类功能，请参见 http://scip.zib.de/doc-5.0.1/html/REOPT.php ，但这仅在您更改目标系数或加强约束时才有效(它基于以下假设:以前不可行的一切仍然不可行，因此您只需要仅在树的可行部分中再次搜索.

Performing a "warmstart" in a MIP solver is quite hard. SCIP provides such functionality, see http://scip.zib.de/doc-5.0.1/html/REOPT.php, but this only works if you change objective coefficients or tighten constraints (it is based on the assumption that everything that was infeasible before is still infeasible, so you only have to search again only in the feasible part of the tree).

但是，在您的特定情况下，仅存储可行的解决方案并在下一次运行中尝试它们将有所帮助.这是SCIP默认情况下所做的.而且，SCIP(以及您提到的所有替代方案)应该比GLPK更稳定和更高效.请参阅 http://plato.asu.edu/ftp/milpc.html 作为MIPLIB 2010上MIP求解程序的基准，标准MIP基准集:GLPK能够在2小时的时间内解决87个实例中的2个，而CBC解决53个，SCIP解决76个，CPLEX和Gurobi都解决了所有87个实例.而且Xpress和SAS在基准测试集上的表现也很好.

In your particular case, though, just storing the feasible solutions and trying them in the next run would help already. This is what SCIP does by default. Also, SCIP (as well as all the alternatives you mentioned) should be much more stable and performant than GLPK. Please see http://plato.asu.edu/ftp/milpc.html for a benchmark of MIP solvers on MIPLIB 2010, the standard MIP benchmark set: GLPK is able to solve 2 of 87 instances within the time limit of 2 hours, while CBC solves 53, SCIP solves 76, and CPLEX and Gurobi both solve all 87 instances. Also Xpress and SAS perform very well on the benchmark set.

这篇关于修改约束的RHS(GLPK)时会发生什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！