Speaker
Kirill Kukharenko
Otto von Guericke University Magdeburg
Topic
All 'round the Simplex Algorithm
The simplex algorithm is one the most popular algorithms to solve linear programs (LP). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron.
The two key issues with the simplex algorithms are, on the one hand, degeneracy, which may cause the algorithm to get stuck at the current extreme point solution with no improvement made for (possibly) many iterations, and potentially long paths taken by the simplex in the graph of the on the underlying polyhedron, on the other hand. In this talk we will present our advances for both of these problems.
For the former, we show that it is always possible to limit the number of consecutive non-improving pivots that the simplex algorithm performs to n-m-1, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form. We relax the latter issue of long paths with the question of bounding the diameter of graphs of polytopes and develop a workaround by constructing polytope extensions having surprisingly small combinatorial diameter.
Zoom-Link for online participation: https://cwi-nl.zoom.us/j/87542191297?pwd=QTIxYlNQUmQ5UTFKb0NSaVVsbGFJZz09
