Groupe d’études et de recherche en analyse des décisions

# Decomposition theorems for linear programs

## Jean-Bertrand Gauthier, Jacques Desrosiers et Marco E. Lübbecke

Given a linear program (LP ) with m constraints and n lower and upper bounded variables, any solution $$x^0$$ to LP can be represented as a nonnegative combination of at most $$m + n$$ so-called weighted paths and weighted cycles, among which at most n weighted cycles. This fundamental decomposition theorem leads us to derive, on the residual problem LP ($$x^0$$ ), two alternative optimality conditions for linear programming, and eventually, a class of primal algorithms that rely on an Augmenting Weighted Cycle Theorem.

, 13 pages