Sign consistent linear programming problems

Abstract

This article studies linear programming problems in which all minors of maximal order of the coefficient matrix have the same sign. We analyse the relationship between a special structure of the non-degenerate dual feasible bases of a linear programming problem and the structure of its associated matrix. In the particular case in which the matrix has all minors of each order k with the same strict sign ϵ _k , we provide a dual simplex revised method with good stability properties. In particular, this method can be applied to the totally positive linear programming problems, of great interest in many applications.

Keywords:

• dual simplex
• sign consistency
• sign regularity
• totally positive linear programming problems
• growth factor

AMS Subject Classifications:

• 90C05
• 65K05
• 90C31
• 90C46
• 15A48

Acknowledgments

The authors are thankful to the referees for their valuable comments and suggestions.