High performance solution of linear optimization problems

ALOP Autumn School, Trier, 31 August 2017

Julian Hall


These two lectures and associated lab session present theory and techniques underlying important high performance solution methods for linear optimization problems. Since performance is principally dependent on the underlying numerical linear algebra it is this which will be explored in greatest detail. The first lecture focuses on serial techniques for the simplex method, in particular those used to exploit hyper-sparsity. The second lecture discusses parallel techniques for the simplex method as well as alternative methods for linear optimization. The lab session will give the opportunity to experiment with high performance serial numerical linear agebra techniques as well as study interior point methods and applications of linear optimization in machine learning and data science.


Lab materials:

The aim of this lab is to introduce some concepts and techniques which are fundamental to high performance numerical linear algebra, to formulate and solve two optimization problems and explore an interior point method implementation in MATLAB.

The lab assumes some basic knowledge of MATLAB and how to find out more using the help facility. Some instructions on how to time calculations and produce formatted output are given here.