Groupe d’études et de recherche en analyse des décisions

G-2019-36

Tulip: An open-source interior-point linear optimization solver with abstract linear algebra

, et

This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements the homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. Tulip's most remarkable feature is that its algorithmic framework is fully disentangled from linear algebra implementations. This allows to seamlessly integrate specialized routines for structured problems, which we illustrate in the case of structured problems found in Dantzig-Wolfe decomposition. Extensive computational results are reported. We find that, using general-purpose sparse linear algebra, Tulip is competitive with open-source interior-point solvers on the Netlib LP testset. Furthermore, armed with specialized linear algebra, Tulip outperforms state-of-the-art commercial solvers on a set of large-scale, decomposable instances that arise in power systems operation.

, 25 pages