何时和为什么GLPK_MI切换到对偶单纯形
我使用CVXPY和GLPK_MI求解器来解决一个混合整数规划问题.求解器以简单单纯形开始，但经过一些尝试后，它切换到使用“长步骤双单纯形”(请参阅下面的解题器日志文件)。我想知道GLPK_MI何时为什么决定改变它的方法？是否有任何参数来改变/设置这个开关点？在尝试简单单纯形之后，在使用对偶单纯形之前，是否有任何方法阻止求解器(即有或没有最优解)？
提前感谢您的时间和帮助！
[21:05:53] [INFO] [dku.utils] - -------------------------------------------------------------------------------
[21:05:53] [INFO] [dku.utils] - Numerical solver
[21:05:53] [INFO] [dku.utils] - -------------------------------------------------------------------------------
[21:05:53] [INFO] [dku.utils] - (CVXPY) Aug 19 09:05:53 PM: Invoking solver GLPK_MI to obtain a solution.
[21:05:53] [INFO] [dku.utils] - (CVXPY) Aug 19 09:05:53 PM: Applying reduction ConeMatrixStuffing
[21:05:53] [INFO] [dku.utils] - 0: obj = 0.000000000e+00 inf = 1.822e+03 (1230)
[21:05:53] [INFO] [dku.utils] - * 4138: obj = -2.197596897e+07 inf = 1.422e-13 (0) 3
[21:05:53] [INFO] [dku.utils] - Long-step dual simplex will be used
[21:05:53] [INFO] [dku.utils] - + 4138: mip = not found yet >= -inf (1; 0)
[21:05:53] [INFO] [dku.utils] - + 4153: >>>>> -2.197593056e+07 >= -2.197593092e+07 < 0.1% (16; 0)
[21:05:53] [INFO] [dku.utils] - + 4153: mip = -2.197593056e+07 >= tree is empty 0.0% (0; 31)回答 1
Stack Overflow用户
发布于 2021-08-27 11:38:03
有人猜测：
为什么/当双重单纯形？
双单纯形是基于Branch-and-Cut搜索的默认选择.您真的很想在解决整数编程问题时使用它！
为什么？基本上，因为添加削减或执行分支决策，在搜索过程中在BnC中所做的事情通常会破坏原始可行性(您得到了一个原始可行的解决方案，并添加了一个新的削减/约束:现在可能不可行)，并且还需要额外的工作(以修复可行性)。
在双重单纯形中，这些切割不会破坏双重可行性。您可能已经失去了双最优性，但可以很容易地继续优化这里。
您的示例切换单纯形方法
您的日志显示，求解器在分支和切割开始时，正处于双单形状态。
在此之前，没有mip指示符，我猜是关于解决根节点/又名根松弛的问题。你可以用原始的或双重的单纯形做这件事。求解者可以根据问题统计(例如变量与约束比)来决定这一点。
但随后，BnC启动，解决程序将利用我前面概述的双单纯形的优点。
备注
你的另一个问题对我来说没有什么意义。它不能保证，当切换发生时，您得到了任何可行的解决方案，我不知道您将如何处理根节点解决方案。
我的意思是:你只需放弃基于MIP的优化，只需解决LP-松弛。这在某种程度上等同于Is there any way to stop the solver (i.e., with or without optimum solution) after trying simple simplex and before using dual simplex? .但是再一次..。这不是什么有意义的事情。
关于参数化，我敢打赌，您可以显式地为这两个阶段(根节点、BnC搜索)设置算法。考虑阅读GLPK文档，这是非常完整的！(但请记住:在为您决定这些事情方面，这些解决者往往比用户更好/更好)
https://stackoverflow.com/questions/68929743
复制相似问题
腾讯云开发者
