在线性程序中屏障求解后避免交叉的缺点

Question

我正在运行一个大型LP（大约500万非零），我想加快解决过程。我尝试了一个并发求解来测试哪个算法最快地解决了我的问题，我发现屏障方法是明显的赢家（求解器= 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（P87）

Answer 1

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