A general phase-I method in linear programming
Phase I of the simplex method finds a basic feasible solution to linear programming (LP) problems. Phase I procedures can also be used for generating feasible points of other problems with linear constraints, or even for checking the consistency of a system of linear equalities/\(inequalities.\) The traditional phase I methods work under the following conditions: (1.1) The incoming variable takes a feasible value. (1.2) The feasible basic variables remain feasible after a transformation (the number of infeasibilities does not increase). (1.3) The outgoing variable leaves the basis at a feasible level (lower or upper bound). By relaxing conditions 1.2, new possibilities arise though still within the frame of the simplex method. This paper presents a procedure based on this relaxation from which more efficient iterations can be expected in phase I - especially in the presence of degeneracy - simply owing to the new way of determining the outgoing variable. This procedure - called FEWPHI - is then combined with an adaptive composite column selection strategy - called ADACOMP - for determining the incoming variable. Though some extra computational effort is required this seems to be outweighed by the more favourable overall performance of the program based on the described method. This improved performance is partly due to the theoretically better numerical stability. Some computational experiences are also reported. In the last section FEWPHI is further generalized by relaxing condition 1.1 too.
- An improved general Phase-I method in linear programming
- A strictly improving linear programming Phase I algorithm
- An artificial-free simplex-type algorithm for general LP models
- A piecewise linear dual phase-1 algorithm for the simplex method
- A phase-1 approach for the generalized simplex algorithm
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3744918 (Why is no real title available?)
- scientific article; zbMATH DE number 3616184 (Why is no real title available?)
- Pivot selection methods of the Devex LP code
- The Composite Simplex Algorithm
- The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
- Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation
- An improved general Phase-I method in linear programming
- A new pivoting rule for solving various degeneracy problems
- A strictly improving linear programming Phase I algorithm
- MOPS -- Mathematical optimization system
- A piecewise linear dual phase-1 algorithm for the simplex method
- Advances in design and implementation of optimization software
- A phase-1 approach for the generalized simplex algorithm
- A generalized dual phase-2 simplex algorithm.
- A Variant of the Dual Pivoting Rule in Linear Programming
- On a dual method for a specially structured linear programming problem with application to stochastic programming
- A Potential Reduction Algorithm with User-Specified Phase I–Phase II Balance for Solving a Linear Program from an Infeasible Warm Start
- Direct phasing by binary integer programming
- MILP acceleration: a survey from perspectives of simplex initialization and learning-based branch and bound
This page was built for publication: A general phase-I method in linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069441)
