Retour

G-2014-67

Decomposition theorems for linear programs

, et

référence BibTeX

Given a linear program (LP ) with m constraints and n lower and upper bounded variables, any solution x0 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 (x0 ), two alternative optimality conditions for linear programming, and eventually, a class of primal algorithms that rely on an Augmenting Weighted Cycle Theorem.

, 13 pages

Axe de recherche

Application de recherche

Publication

, et
Operations Research Letters, 42(8), 553–557, 2014 référence BibTeX