A tour of simplex algorithm

Session date: 9 October 2023

Session host: Konstantin Sidorov

Summary:

In this session, I will introduce the simplex algorithm, an approach to solving linear programs by greedily enumerating the extreme points of the feasible set. Despite being relatively simple geometrically, this approach can become very involved once it gets into the implementation – so my goal for this session is to give a complete picture including both the problem geometry and handling the corner cases. On top of that, I will discuss the key points from the duality theory in linear programming – where the simplex algorithm often gives a way to land a simple and constructive proof to a non-trivial fact!

Relevant papers