  


A noniterative polynomial algorithm for linear programming
JingYuan Wei (weijingyuangmail.com) Abstract: Consider a linear programming problem with n primal and m dual variables paired with n dual and m primal slack variables respectively, and aggregately denote these variables and slack variables as a vector z of length 2(n+m). Unlike existing algorithms such as simplex and interior point methods solving linear programming by iteratively generating a sequence of feasible points to approach the optimal solution, the paper defines a function f mapping the constraint matrix and the righthand side and objective vectors defining the linear programming problem to a binary vector of length n+m. It is shown that, under the uniqueness assumption of the optimal solution z* and for each (primal or dual) variable z_i, f_i is zero if and only if the optimal value z*_i is zero, and f_i is one if and only if z*_i is positive. Computation of f_i for each i consists of solving two groups of linear equations using O(m^2n) operations. Computing f_i is then noniterative and independent of computing f_j for j <> i. Hence, at most O(m^2n^2) operations are required to compute f and consequently to solve the linear programming problem. The noniterative and mutually independent features of computing the elements of f enable a parallel polynomial algorithm for linear programming. Keywords: Linear programming, Mathematical programming, Optimization, Polynomialtime algorithm, Strictly complementary slacknes, Parallel algorithm Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Optimization Software and Modeling Systems (Parallel Algorithms ) Category 3: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Reliance M. & E. Engineering Co. Ltd, F19T2 Xihuan Plaza, 1 Xiwai St, Xicheng District, Beijing, China. June 2013 Download: [PDF] Entry Submitted: 06/26/2013 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  