A general phase-I method in linear programming (Q1069441)

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.