In 1973 Gill and Murray proposed a non-simplex active-set method (also known as basis-deficiency-allowing dual simplex variation since P.-Q. Pan’s 1998 work) for the primal linear problem in inequality form min{cT x AT x b}. In this note a non-simplex active-set method for its dual linear program in standard form max{bT y Ay c y O} is given, so we obtain a different but equivalent description of the basis-deficiency-allowing primal simplex variation of Pan, which is an exterior method that allows us to work with a subset of independent columns of A which is not necessarily a square basis. The new description reveals more clearly the relations with Gill and Murray’s work; moreover, we focus our attention in providing several alternatives to address several features not properly addressed by Pan, namely their sparse implementation, suitable Phase I’s and Farkas’ connection.
linear programming, basis-deficiency-allowing simplex variations, non-simplex active-set methods, Phase I, Farkas’ lemma, sparsity.
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).