Group for Research in Decision Analysis

G-2019-36

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

, , and

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