  


Decomposition theorems for linear programs
JeanBertrand Gauthier(jeanbertrand.gauthierhec.ca) Abstract: It is well known that any feasible arcflow 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 cyclecanceling 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 nonnegative combination of at most $m + n$ socalled 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/2014 Modify/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  