Jan W. Owsinski

The paper outlines an approach, applicable to both the problem of clustering and to (‘‘optimum’’) ordering, which starts from a formulation of the objective function and the constraints, equivalent to a binary mathematical programming problem. This formulation, for both ordering and clustering, represents a number of very positive features, like possibility of dealing with incomplete and inconsistent data, while posing essential numerical difficulties. For clustering, it implies a globally optimal solution in that both cluster content and cluster number are obtained. We reformulate this problem by parameterising it and show that, under certain additional assumptions, an effective algorithm can be deduced for both clustering and ordering, which suboptimises the objective function. In the case of clustering, the algorithm is an analogue of the classical hierarchical merger procedures, while in the case of ordering it relies on iterations, in which just one object is moved. Some essential properties are given, along with a simple illustration. In spite of the analogy, the properties of the approach and the respective algorithms are different for the two cases considered, i.e. clustering and ordering. Keywords: Clustering, Ordering, Mathematical Programming, Parameterisation, Suboptimisation Algorithms, Objective Functions.