DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
The Box Method for Linear Programming. Part 2. Treatment of Problems in Standard Form with Explicitly Bounded Variables.
STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
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 matroidalor, 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.
APPROVED FOR PUBLIC RELEASE