论文标题
用于线性优化的模块化内点求解器的设计和实现
Design and implementation of a modular interior-point solver for linear optimization
论文作者
论文摘要
本文介绍了Tulip的算法设计和实现，Tulip是一种用于线性优化的开源内部求解器。它实现了具有多个中心性校正的正规均匀内部算法，因此处理无限制和不可行的问题。该求解器用朱莉娅（Julia）编写，因此允许灵活而有效的实现：Tulip的算法框架完全脱离了线性代数实现和模型的算术。特别是，这允许无缝整合结构化问题的专业例程。报道了广泛的计算结果。我们发现，在H. Mittelmann的屏障线性编程求解器的基准上，郁金香与开源内部求解器具有竞争力。此外，我们在Dantzig-Wolfe分解的背景下为结构化的主问题设计了专门的线性代数例程。这些例程在电力系统操作和两阶段随机编程中产生的大且密集的实例中产生了十倍的速度，从而超过了最先进的商业内部方法求解器。最后，我们说明了郁金香通过以扩展精度解决问题来使用不同级别的算术精度的能力。
This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements a regularized homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. The solver is written in Julia, thus allowing for a flexible and efficient implementation: Tulip's algorithmic framework is fully disentangled from linear algebra implementations and from a model's arithmetic. In particular, this allows to seamlessly integrate specialized routines for structured problems. Extensive computational results are reported. We find that Tulip is competitive with open-source interior-point solvers on the H. Mittelmann's benchmark of barrier linear programming solvers. Furthermore, we design specialized linear algebra routines for structured master problems in the context of Dantzig-Wolfe decomposition. These routines yield a tenfold speedup on large and dense instances that arise in power systems operation and two-stage stochastic programming, thereby outperforming state-of-the-art commercial interior point method solvers. Finally, we illustrate Tulip's ability to use different levels of arithmetic precision by solving problems in extended precision.
