多年来是否有关于 LP/MIP 求解器运行时加速的概述?

计算科学 优化 线性求解器 约束优化
2021-12-07 04:45:49

每当我阅读使用 LP/MIP 方法的 OR 论文时,它们都会包括使用的时间求解器,以及版本和年份。我想知道随着硬件和软件(求解器)的当前进步,现在同样的实验会快多少。

例如,如果 2012 年在 CPLEX 8.0 上进行了一项实验,那么现在使用当前的 CPLEX 版本会快多少?(知道硬件如何影响这一点,也会很棒)

这对于了解我是否可以以某种方式对程序建模至关重要。我一直在寻找一个统一的来源或至少一些我可以用来进行转换的信息。不幸的是,我没有任何运气。

有人能给它带来光明吗?

PS:这是我第一次写帖子。如果格式不合适,我深表歉意。

1个回答

在计算机速度(基本上由摩尔定律驱动)和用于求解 LP 尤其是 MILP 的算法方面都取得了进展。总体而言,算法的改进所产生的影响至少与硬件的改进一样大。

这将如何适用于您的特定模型是一个不同的问题。特别是对于 MILP,求解器的性能很大程度上取决于特定模型,您无法从基准研究中真正概括。

一些讨论这个问题的论文包括:

Bixby, Robert E. “解决现实世界的线性程序:十年甚至更多的进步。” 运筹学 50.1(2002):3-15。

比克斯比、罗伯特和爱德华·罗斯伯格。“计算混合整数规划的进展——从转折点的另一边回顾。” 运筹学年鉴 149.1(2007):37-41。

Bixby, Robert E. “线性和混合整数规划计算的简史”。Documenta Mathematica 2012 (2012): 107-121。