Accession Number:

ADA183217

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s):

• Zikan,Karel
• Cottle,Richard W.

Report Date:

1987-07-01

Pagination or Media Count:

15.0

Abstract:

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.

Descriptors:

• *LINEAR PROGRAMMING
• ALGORITHMS
• ITERATIONS
• LOW COSTS
• NETWORK FLOWS
• OPTIMIZATION
• SEARCHING
• VARIABLES
• WEIGHTING FUNCTIONS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE