An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple objective linear programming problem (MOLP). Motivated by these difficulties, some researchers in recent years have suggested that outcome set-based approaches should instead be developed and used to solve problem (MOLP). In this article, we present a finite algorithm, called the Outer Approximation Algorithm, for generating the set of all efficient extreme points in the outcome set of problem (MOLP). To our knowledge, the Outer Approximation Algorithm is the first algorithm capable of generating this set. As a by-product, the algorithm also generates the weakly efficient outcome set of problem (MOLP). Because it works in the outcome set rather than in the decision set of problem (MOLP), the Outer Approximation Algorithm has several advantages over decision set-based algorithms. It is also relatively easy to implement. Preliminary computational results for a set of randomly-generated problems are reported. These results tangibly demonstrate the usefulness of using the outcome set approach of the Outer Approximation Algorithm instead of a decision set-based approach. This revised version was published online in July 2006 with corrections to the Cover Date.