Integer Programming and the Theory of Grouping

Abstract

This paper is written with three objectives in mind. First, to point out that the problem of grouping, where a larger number of elements n are combined into m mutually exclusive groups (m < n) should be recognized as a problem in Integer Programming, and that such recognition can help us in avoiding complete enumeration of stages in grouping from n to n — 1 … to m, and of alternative possibilities in each stage. Second, to formulate mathematically some simple versions of the relevant Integer Programming Problem, so that the available computer codes can solve it. When the grouping attempts to minimize the within groups sums of squares, the so-called string property is proved to be necessary for the minimum (Lemma 1). It is shown that the string property can be exploited to write the non-linear within group sums of squares as a linear function (Lemma 2). An attempt is made to generalize the string property for the higher dimensional case. Third, to give some numerical examples to clarify the mathematical models and to illustrate the advantages of Integer Programming formulation by comparing with the numerical examples appearing in the literature [8], [13]. Zero-One programming where the integer variables can take values of zero or one only appears to be most efficient from the limited experience of the author. The paper is divided into three sections which closely correspond to the three objectives noted above.