An Improved Primal Simplex Algorithm for Degenerate Linear Programs

DOI10.1287/ijoc.1100.0425zbMath1243.90121OpenAlexW2097828930MaRDI QIDQ2899148

François Soumis, Abdelmoutalib Metrane, Guy Desaulniers, Issmail El Hallaoui

Publication date: 28 July 2012

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.1100.0425

zbMATH Keywords

linear programmingdegeneracyprimal simplex algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Related Items (26)

Improved integral simplex using decomposition for the set partitioning problem ⋮ Distributed integral column generation for set partitioning problems ⋮ A linear programming decomposition focusing on the span of the nondegenerate columns ⋮ The positive edge pricing rule for the dual simplex ⋮ The positive edge criterion within COIN-OR's CLP ⋮ Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows ⋮ Dynamic constraint and variable aggregation in column generation ⋮ Integral simplex using decomposition with primal cutting planes ⋮ Integral Column Generation for Set Partitioning Problems with Side Constraints ⋮ Dynamic penalization of fractional directions in the integral simplex using decomposition: application to aircrew scheduling ⋮ Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation ⋮ Linear fractional approximations for master problems in column generation ⋮ Dynamic constraint aggregation for solving very large-scale airline crew pairing problems ⋮ About the minimum mean cycle-canceling algorithm ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Improving a primal–dual simplex-type algorithm using interior point methods ⋮ The double pivot simplex method ⋮ A column generation approach for solving the patient admission scheduling problem ⋮ Column generation decomposition with the degenerate constraints in the subproblem ⋮ Influence of the normalization constraint on the integral simplex using decomposition ⋮ A new version of the improved primal simplex for degenerate linear programs ⋮ Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis ⋮ Improving set partitioning problem solutions by zooming around an improving direction ⋮ Vector Space Decomposition for Solving Large-Scale Linear Programs ⋮ The minimum mean cycle-canceling algorithm for linear programs ⋮ Integral Simplex Using Decomposition for the Set Partitioning Problem

This page was built for publication: An Improved Primal Simplex Algorithm for Degenerate Linear Programs