Miguel Anjos

Professor and Chair of Operational Research



Contact

Miguel Anjos

Professor and Chair of Operational Research




Miguel Anjos

Professor and Chair of Operational Research



Design and implementation of a modular interior-point solver for linear optimization


Journal article


M. Tanneau, M.F. Anjos, A Lodi
Mathematical Programming Computation, vol. 13, 2021, pp. 509-551

Semantic Scholar ArXiv DBLP DOI
Cite

Cite

APA   Click to copy
Tanneau, M., Anjos, M. F., & Lodi, A. (2021). Design and implementation of a modular interior-point solver for linear optimization. Mathematical Programming Computation, 13, 509–551.


Chicago/Turabian   Click to copy
Tanneau, M., M.F. Anjos, and A Lodi. “Design and Implementation of a Modular Interior-Point Solver for Linear Optimization.” Mathematical Programming Computation 13 (2021): 509–551.


MLA   Click to copy
Tanneau, M., et al. “Design and Implementation of a Modular Interior-Point Solver for Linear Optimization.” Mathematical Programming Computation, vol. 13, 2021, pp. 509–51.


BibTeX   Click to copy

@article{m2021a,
  title = {Design and implementation of a modular interior-point solver for linear optimization},
  year = {2021},
  journal = {Mathematical Programming Computation},
  pages = {509-551},
  volume = {13},
  author = {Tanneau, M. and Anjos, M.F. and Lodi, A}
}

Abstract

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.




Follow this website


You need to create an Owlstown account to follow this website.


Sign up

Already an Owlstown member?

Log in