  


Vector Space Decomposition for Linear Programs
Jean Bertrand Gauthier(jeanbertrand.gauthierhec.ca) Abstract: This paper describes a vector space decomposition algorithmic framework for linear programming guided by dual feasibility considerations. The resolution process moves from one basic solution to the next according to an exchange mechanism which is defined by a direction and a postevaluated step size. The core component of this direction is obtained via the smallest reduced cost that can be achieved upon dividing the set of dual variables in two subsets: one being fixed whiles the other being optimized. From a primal perspective, such a pricing problem selects a convex combination of variables entering the basis. The direction is uniquely completed by identifying a posteriori affected variables, if any. The degenerate status of the current solution can be exploited in specific variants. This unified framework is presented in a generic format from which different variants can be extracted. These include several well known algorithms. The most known special case is the Primal Simplex algorithm where all dual variables are fixed: this results in the choice of a single entering variable, indeed a myopic strategy commonly leading to degenerate pivots. At the other extreme, we find the strongly polynomial Minimum Mean CycleCanceling algorithm for the capacitated network ow problem for which all dual variables are optimized at every iteration. Somewhere in between these two extremes lies another special case, the Improved Primal Simplex algorithm for which one fixes the dual variables associated with the nondegenerate basic variables and optimizes the rest. The two last variants both bestow a pricing problem providing necessary and suffcient optimality conditions. As a result, nondegenerate directions are also issued from these pricing steps. These directions move on the edges of the polyhedron for the latter while the former can identify interior directions by combining edge directions. Other properties are derived on different variants of this generic framework. Keywords: primal simplex algorithm; degeneracy; optimized reduced costs; combination of entering variables; positive edge rule; nondegenerate pivot algorithms; vector space Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Submitted Download: [PDF] Entry Submitted: 02/26/2015 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  