Optimization Online


A non-iterative polynomial algorithm for linear programming

Jing-Yuan Wei (weijingyuan***at***gmail.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 right-hand 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 non-iterative 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 non-iterative and mutually independent features of computing the elements of f enable a parallel polynomial algorithm for linear programming.

Keywords: Linear programming, Mathematical programming, Optimization, Polynomial-time 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, F19-T2 Xihuan Plaza, 1 Xiwai St, Xicheng District, Beijing, China. June 2013

Download: [PDF]

Entry Submitted: 06/26/2013
Entry Accepted: 06/26/2013
Entry Last Modified: 10/07/2013

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