Évènement

Kirill Kukharenko
Otto-von-Guericke University Magdeburg

Date(s) : 18/12/2024   iCal
10h30 - 12h00

The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). 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. A key issue in the simplex algorithm’s performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. We prove that it is always possible to limit the number of consecutive degenerate 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. This is a joint work with Laura Sanità.

Emplacement
Saint-Charles - FRUMAM (2ème étage)

Catégories

• Séminaire