Multiple Optimal Solutions in Linear Programming Models

Since 1950, empirical studies using linear programs (LP) have all neglected the consequences of one important aspect of mathematical programming. Simply stated, the polyhedral nature of the solution set in LP models may cause multiple optimal solutions if some plausible conditions are realized. If and when empirical problems possess alternate optimal solutions, why is only one of them usually selected for presentation in final reports which, often, also make efficiency judgments and prescribe sweeping policy changes? When LP is used for analyzing empirical problems, an implicit comparison is usually made between the activities actually chosen and operated by the economic agent under scrutiny and the optimal activities suggested by the model's solution. In several instances (Wicks), the use of LP for policy planning has inspired the use of Theil' s U-inequality coefficient to assess formally the discrepancy between actual and optimal (predicted) activities. Desired values of the U coefficient are those close to zero, attained when the squared distance between actual and LP optimally predicted activities is small. Implicitly, however, minimum distance criteria have been used by many authors to assess the plausibility and performance of their LP models. In the presence of multiple optimal solutions, however, the selection of a specific solution for final analysis is crucial and should not be left to computer codes as probably has been the case in all reported studies. Furthermore, the empirical LP problem is made even more complex by the existence of quasioptimal solutions; that is, those solutions which change the optimal value of the objective function only by a fractional percentage. Because the information used to specify empirical problems is seldom exact, quasi-optimal solutions may legitimately be considered as suitable candidates for final reporting. The conditions under which multiple primal and dual optimal solutions can occur in linear programming problems are related to the phenomenon of degeneracy, a rather plausible situation in empirical studies. Degeneracy of the primal solution occurs when a set of activities employs inputs in exactly that proportion which exhausts completely two or more available resources. Analogously, degeneracy of the dual solution is encountered when, given an optimal plan, the accounting loss for some nonbasic activity happens to be the same (zero) as that of the activities included in the optimal plan. Hence, the likelihood of either primal or dual degeneracy increases rapidly with the size of the model. Baumol (p. 315) asserts that "computational experience indicates that such cases (primal and dual degeneracy) are encountered more frequently than might be expected in advance." Thus, a correct and informative report of empirical results generated by LP should include complete information about the problem's size and an explicit statement of whether the primal and dual solutions pres nted are indeed unique. Unfortunately, a search of the empirical literature has revealed that a majority of papers fail to disclose even the number of columns and rows in the matrix of constraints. No paper mentioned whether or not the reported solutions are unique.