Reducing the Size of the Nondominated Set: Pruning by Clustering
Loading...
Links to Files
Permanent Link
Collections
Author/Creator
Author/Creator ORCID
Date
1980
Type of Work
Department
Program
Citation of Original Publication
Morse, Joel N. "Reducing the Size of the Nondominated Set: Pruning by Clustering," Computers and Operations Research, Vol. 7, No.1-2, 1980, pp. 55-66
Rights
Subjects
Abstract
The multicriterion_ simplex methods of Evans and Steuer(!} and Yu and Zeleny[2) have encouraged model builders to consider matrix criteria. When conflicting objectives are simultaneously considered, there is no such thing as an optimum solution. Rather, a preferred class of basic feasible solutions called the nondominated set results. Since this set can be extremely large, some means must be found to prune it. Steuer[3] has proposed a filtering method. Another mechanistic aid to the decision maker ยท (DM), based on cluster analysis, is presented in this paper. The idea is to portray the nondominated set N by a representative subset. Cluster analysis partitions N into groups of relatively homogeneous elements. In this research I added a very general evaluative criterion: minimum redundancy. Since there is a threshold of resolution beyond which the OM cannot perceive the difference between two very similar solution vectors, there is little point in making him waste time processing all of N in the search for a final solution. Two forms of cluster analysis are tested - direct clustering and hierarchical clustering. Within the group of hierarchical methods there are eight algorithms. In the present application the two worst things that could happen are clusiers that "chain" and outlying vectors (the residue set) that are obscured. Taking account of these two undesirable outcomes, three algorithms worked best on the particular data used Ward's Method, the Group Average Method, and the Centroid Method. The hierarchical methods are recommended over direct clustering. {However, some similarity between direct and hierarchical clustering is discovered.) Hierarchical clustering serves to minimize redundancy, and thereby reduces the chance that the selection of a final solution will stress the decision maker beyond his information endurance. The concepts stressed in this paper are very similar to those expressed in Tom[4]. This article presents computational experience with the cluster analysis which was developed independently by Torn, whose approach and mine will be combined under an algorithmic strategy called Two-Stage Pruning (TSP). TSP first reduces the nondominated set to a representative set. This set, in turn, is interactively manipulated until a decision evolves.