linear-programming - 线性规划求解障碍后避免交叉的缺点

Question

我正在运行一个大型 LP(大约 5M 非零)，我想加快求解过程。我尝试了并发求解来测试哪种算法可以最快地解决我的问题，我发现屏障方法是明显的赢家(求解器 = Xpress MP，但我猜其他求解器也是一样的)。

但是，我想进一步加快它的速度。我注意到真正的障碍求解时间不到总求解时间的 1%。其余时间用于交叉 (~40%) 和原始求解(在新基础上找到角解)(~60%)。不幸的是，我找不到告诉求解器进行双交叉的设置(Cplex 中有一个，但我没有 Cplex 的许可证)。因此我无法比较这是否会更快。

因此，我尝试关闭交叉，这会产生巨大的速度提升，但根据文档，有一些缺点。到目前为止，我所知道的缺点是:

• 障碍解决方案往往是中间解决方案。
• 没有交叉的障碍不会产生基本解决方案(尽管求解器设置提到“无论是否使用交叉，完整的原始和对偶解决方案都可用。”)。
  • 没有基础，您将无法使用高级启动信息重复优化相同或相似的问题。
  • 没有依据，您将无法获得进行敏感性分析的范围信息。

我的问题很简单。还有哪些其他缺点很重要，可以证明非常低效的交叉步骤(Cplex 和 Xpress MP 均启用交叉作为默认设置)。或者，我的问题是否特殊？其他问题的交叉步骤是否非常快？最后，中面解决方案有什么问题(这意味着角最优值也不是唯一的)？

来源:

• http://www.cs.cornell.edu/w8/iisi/ilog/cplex101/usrcplex/solveBarrier2.html (屏障算法高阶理论)
• http://tomopt.com/docs/xpress/tomlab_xpress008.php (Xpress MP 求解器设置)
• https://d-nb.info/1053702175/34 (第 87 页)

Answer 1

主要缺点:解决方案将“丑陋”，即解决方案值中有许多 0.000001 和 0.9999999。其次你可能会得到一些不同的双重。最后，需要一个基础来进行快速“热启动”。加速大型模型的一种可能方法是使用单纯形法并使用来自代表性基础运行的高级基础。