Article ID: | iaor20001174 |
Country: | Netherlands |
Volume: | 111 |
Issue: | 3 |
Start Page Number: | 582 |
End Page Number: | 588 |
Publication Date: | Dec 1998 |
Journal: | European Journal of Operational Research |
Authors: | Bryson Noel, Joseph Anito |
Keywords: | lagrange multipliers, programming: integer |
In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed in different groups. For certain classes of the problem or, under certin assumptions, the partitioning exercise can be formulated as a sequence of linear programs (LPs), each with a parametric objective function. Such LPs can be solved using the parametric linear programming procedure developed by Gass and Saaty. In this paper, a parametric linear programming model for solving cluster analysis problems is presented. We show how this model can be used to find optimal solutions for certain variations of the clustering problem or, in other cases, for an approximation of the general clustering problem.