Decomposition theorems for linear programs

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