Optimization Online


Decomposition theorems for linear programs

Jean-Bertrand Gauthier(jean-bertrand.gauthier***at***hec.ca)
Jacques Desrosiers(jacques.desrosiers***at***gerad.ca)
Marco Lübbecke(marco.luebbecke***at***rwth-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/2014
Entry Accepted: 10/08/2014
Entry Last Modified: 10/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society