GLPK_MI 何时以及为何切换到对偶单纯形
When and why GLPK_MI switches to dual simplex
我使用 CVXPY 和 GLPK_MI 求解器来解决混合整数规划问题。求解器从简单单纯形开始，但经过一些尝试后，它切换到使用“长步对偶单纯形”（请参阅下面来自求解器的日志文件。）我想知道 GLPK_MI 何时以及为何决定切换其方法？ change/set这个切换点有参数吗？在尝试简单单纯形之后和使用对偶单纯形之前，是否有任何方法可以停止求解器（即有或没有最优解）？
提前感谢您的宝贵时间和帮助！
[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)
一些猜测：
为什么/什么时候对偶单纯形？
对偶单纯形是 在 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 搜索）明确设置算法。考虑阅读非常完整的 GLPKs 文档！ （但请记住：在为您决定这些事情方面，这些求解器通常非常好/更好）
我使用 CVXPY 和 GLPK_MI 求解器来解决混合整数规划问题。求解器从简单单纯形开始，但经过一些尝试后，它切换到使用“长步对偶单纯形”（请参阅下面来自求解器的日志文件。）我想知道 GLPK_MI 何时以及为何决定切换其方法？ change/set这个切换点有参数吗？在尝试简单单纯形之后和使用对偶单纯形之前，是否有任何方法可以停止求解器（即有或没有最优解）？
提前感谢您的宝贵时间和帮助！
[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)
一些猜测：
为什么/什么时候对偶单纯形？
对偶单纯形是 在 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 搜索）明确设置算法。考虑阅读非常完整的 GLPKs 文档！ （但请记住：在为您决定这些事情方面，这些求解器通常非常好/更好）