Heuristic Selection of Advanced Bases for a Class of Linear Programming Models

This paper describes a procedure for selecting a starting basis for a class of large linear programming models. This class, a generalization of the transportation problem, is the product of a matrix generator described elsewhere. The procedure is joined to the matrix-generator process and uses structural criteria and implicit knowledge of the model being generated to assess the attractiveness of vectors for an optimal solution. Additionally, it allows the analyst to describe, through a set of multipliers, the general features of the expected optimal solution. The multipliers are employed heuristically in conjunction with the other criteria to select a set of vectors, both logical and structural, for submission to a standard mathematical programming computational system as a starting basis. Examples of applications of the basis selector and possible extensions are presented.