Implementing an Interior-Point Solver: Design Choices and Data Structures

Mathieu Tanneau, Polytechnique Montréal

This talk presents the design and implementation of the interior-point solver Tulip.jl. We start with a brief introduction to interior-point methods for linear programming, highlighting their key algorithmic components. Then, we describe some practical aspects of presolve, including classical primal and dual reductions and relevant data structures. Finally, we focus on the resolution of linear systems that underlie interior-point algorithms: we review recent developments such as specialized linear algebra, a renewed interest for iterative methods, and the use of hardware acceleration.

Please use this link to attend the virtual seminar: