Box Method for Linear Programming. Part 2. Treatment of Problems in Standard Form with Explicitly Bounded Variables

摘要

A crucial aspect of the Box Method for linear programming is the finding of a minimum-weight basis corresponding to a given interior feasible point. This subproblem leads to the formation of the Box Problem, a special linear program having a closed form solution which provides the search direction at the current iteration. Finding a minimum-weight basis is a matroidal(or, combinatorial) optimization problem that can be handled by a greedy algorithm. This paper suggests a way of efficiently solving the minimum-weight basis problem in cases where the (primal, standard form) linear program contains explicitly bounded variables. It is shown that the main part of the task requires almost no more computational effort or storage space than does a problem of the same size without upper bounded variables. While this result is believed to be valuable in its own right, there is additional benefit to be gained in applications where the finding of a minimum-weight basis (for a linear program without explicit upper bounds on its variables) is done by a special greedy algorithm. Such is the case with minimum-cost network flow problems which will be discussed in Part III of this series.