Improved primal simplex: a more general theoretical framework and an extended experimental analysis

DOI10.1287/IJOC.2015.0656MaRDI QIDQ2802253zbMATHOpenAlexFDO

Authors Jérémy Omer, Samuel Rosat, Vincent Raymond, François Soumis

Publication date 25 April 2016

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

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

zbMATH Keywords

linear programmingdecompositiondegeneracysimplexprimal algorithms

Mathematics Subject Classification ID

Linear programming (90C05)

Recommendations

• A linear programming decomposition focusing on the span of the nondegenerate columns
• A new version of the improved primal simplex for degenerate linear programs
• An improved primal simplex algorithm for degenerate linear programs
• An improved initial basis for the simplex algorithm
• A primal-dual simplex method for linear programs

Cites work

• A class of methods for linear programming
• A degeneracy exploiting LU factorization for the simplex method
• A new version of the improved primal simplex for degenerate linear programs
• A practicable steepest-edge simplex algorithm
• A practical anti-cycling procedure for linearly constrained optimization
• A primal deficient-basis simplex algorithm for linear programming
• An improved primal simplex algorithm for degenerate linear programs
• Column generation decomposition with the degenerate constraints in the subproblem
• Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
• Integral simplex using decomposition with primal cutting planes
• Large-scale linearly constrained optimization
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
• Pivot selection methods of the Devex LP code
• The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• The positive edge criterion within COIN-OR's CLP

Cited in

(5)

• Dynamic penalization of fractional directions in the integral simplex using decomposition: application to aircrew scheduling
• Influence of the normalization constraint on the integral simplex using decomposition
• A new version of the improved primal simplex for degenerate linear programs
• A linear programming decomposition focusing on the span of the nondegenerate columns
• The positive edge pricing rule for the dual simplex

Describes a project that uses

Uses Software

• DEVEX

This page was built for publication: Improved primal simplex: a more general theoretical framework and an extended experimental analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802253)