swMATH ID: 40848
Software Authors: Tanneau, Mathieu; Anjos, Miguel F.; Lodi, Andrea
Description: Design and implementation of a modular interior-point solver for linear optimization. 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.
Homepage: https://ds4dm.github.io/Tulip.jl/dev/
Source Code: https://github.com/ds4dm/Tulip.jl
Dependencies: Julia
Keywords: linear programming; interior-point methods; open-source software
Related Software: LDLFactorizations.jl; UnitBlockAngular.jl; LPBenchmarks; MathOptInterface.jl; JuMP; Julia; CVXPY; ECOS; CLP; Pyomo; SuiteSparse; Mosek; YALMIP; GLPK; CPLEX; Gurobi
Cited in: 1 Publication

Citations by Year