A general phase-I method in linear programming
type: Item
instance of: scholarly article
title: A general phase-I method in linear programming
zbMATH Open document ID: 0583.90060
DOI: 10.1016/0377-2217(86)90215-8
published in: European Journal of Operational Research
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3934765
zbMATH Keywords: simplex method
zbMATH Keywords: Phase I procedures
zbMATH Keywords: improved performance
zbMATH Keywords: computational experiences
author: István Maros
describes a project that uses: DEVEX
MaRDI profile type: Publication
OpenAlex ID: W2042342288
cites work: The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
cites work: Q3844775
cites work: Pivot selection methods of the Devex LP code
cites work: Q4180134
cites work: Q3929393
cites work: The Composite Simplex Algorithm
description: scientific article; zbMATH DE number 3934765