High performance solution of large-scale linear programming problems

Invited seminar, Stirling, 1 November 2019

Julian Hall

Abstract

The requirement to solve large-scale linear programming (LP) problems is ubiquitous: they are the fundamental model in optimal decision-making, but also solved in vast numbers when finding the optimal solution of large-scale discrete optimization problems. Most LP problems are solved with the simplex algorithm, and this talk will focus on the computational challenges of using it to solve large-scale sparse problems on both serial and multi-core architectures. Performance is primarily determined by techniques to exploit the particular nature of the underlying numerical linear algebra requirements. These have characteristics that should be of interest to a general audience. There will also be an introduction to novel techniques for fast approximate solution of LP problems.


Slides:

Stirling19.pdf

Code:

HiGHS