Generalization of a Primal-dual Simplex Algorithm by Curet
GAO Pei-wang
Abstract：Curet's primal‐dual approach is essentially to solve a series of primal relaxed linear program‐ming sub‐problems w hile keeping the dual feasibility .So it must be started by an initial dual feasible solu‐tion .For the case of negative coefficients in the objective function ,this paper makes a generalization of Cu‐ret's primal‐dual algorithm .First ,the artificial constraint is introduced to achieve a new objective function with all the nonnegative coefficients by a simple elementary row operation .Then ,Curet's algorithm is ap‐plied to obtain a primal feasible solution closer to the optimality by updating the new objective function at each iteration .Finally ,the complementary slackness condition is achieved to arrive at the optimality .Com‐paring to the classical two‐phase simplex algorithm ,the computational results show that our algorithm u‐ses fewer iterations and spends less executive time on most instances ,and therefore such generalization is valuable .
Keywords：Linear programmingsimplex algorithmprimal-dual simplex algorithmdual feasible so-lutioncomputational efficiency
Publication Date：2014-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：7( 19-25 )