- Decomposition theorems for linear programs Jean-Bertrand Gauthier(jean-bertrand.gauthierhec.ca) Jacques Desrosiers(jacques.desrosiersgerad.ca) Marco Lübbecke(marco.luebbeckerwth-aachen.de) Abstract: It is well known that any feasible arc-flow solution to a network problem defined on a graph $G = (N, A)$, where $N$ is the set of nodes whereas $A$ is the set of arcs, can be expressed using at most $|A| + |N|$ paths and cycles having nonzero flow, out of these, at most $|A|$ cycles. This \textit{existence theorem} is used in a number of proofs establishing the complexity of strongly polynomial algorithms for network flow problems such as the minimum mean cycle-canceling algorithm. While it is the crucial component of the analysis, the heart of the algorithm is the residual network upon which are derived two theorems that demonstrate its validity, the Augmenting Cycle Theorem and the Negative Cycle Optimality Theorem. This paper generalizes these theorems to linear programming. Given a linear program~(LP) with $m$ constraints and $n$ lower and upper bounded variables, any solution $\vx^0$ to LP can be represented as a non-negative 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($\vx^0$), two alternative optimality conditions for linear programming, and eventually, a class of primal algorithms that rely on an Augmenting Weighted Cycle Theorem. Keywords: network problems, flow decomposition, linear programming, residual problem, optimality conditions Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Network Optimization Citation: Accepted to Operations Research Letters Download: [PDF]Entry Submitted: 10/08/2014Entry Accepted: 10/08/2014Entry Last Modified: 10/08/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.