<figure><img src="image_1.png" /></figure>

HAL
open science

Multicriteria dynamic clustering

Uri Hanani

► To cite this version:

Uri Hanani. Multicriteria dynamic clustering. [Research Report] IRIA-RR-358, IRIA. 1979, pp.39.
hal-04716609

HAL Id: hal-04716609

https://inria.hal.science/hal-04716609v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
INV: 07442 RR358

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_3.png" /></figure>

MULTICRITERIA
DYNAMIC CLUSTERING

Uri HANANI

39 p.

Rapport de Recherche N° 358

September 1979
# MULTICRITERIA DYNAMIC CLUSTERING

## Uri Hanani*

### Résumé :

Le problème général de classification à critères multiples est discuté. On montre qu'il existe une famille d'algorithmes de classification à critères multiples, capable de traiter divers problèmes de planification urbaine ainsi que différents problèmes qui se posent dans les systèmes informatiques. Pour illustrer ce problème général, un exemple détaillé de classification avec contrainte de taille est étudié. Un programme de classification multicritère est présenté.

### Abstract :

The general problem of multicriteria clustering is discussed. A formal algorithm based on Dynamic Clusters Method is presented using the concept of the kernel, as a representation of any given criterion. It is shown that there exists a family of multicriteria clustering algorithms, capable of handling various problems in urban planning (location of public service facilities with multiple criteria), as well as in the domain of information systems. A detailed example of clustering with equal groups constraint is discussed. Finally a computer program is presented.

**Keywords** : Multicriteria Decision Making, Dynamic clustering, Multicriteria clustering, Kernel's representation, Equal group partitioning, political redistricting.

<footnote>* School of Business Administration
Hebrew University of Jerusalem, Israël</footnote>
# MULTICRITERIA DYNAMIC CLUSTERING

## Table of contents

1. INTRODUCTION

1.1 Presentation of the problem

1.2 Models of Multicriteria Decision Making

1.2.1 General models

1.2.2 Criteria VS constraints

1.2.3 Urban Planning example

1.3 The Multicriteria Dynamic Cluster Approach

2. THE MULTICRITERIA DYNAMIC CLUSTERS (MDC) ALGORITHM

2.1 Notation

2.2 The algorithm

2.3 Relation between MDC and DCM (Dynamic Cluster Method)

2.4 Convergence of MDC

2.4.1 Theorem of convergence

2.4.2 Necessary condition to the convergence

3. CLUSTERING WITH EQUAL GROUP CONSTRAINTS

3.1 The problem

3.2 The MDC algorithm

3.2.1 The Kernels

3.2.2 The Multimetric

3.2.3 The Operators G and F

3.2.4 The Multicriteria W

3.3 Study of convergency

3.4 An example

4. OTHER MODIFICATIONS AND APPLICATION OF MDC

4.1 Modifications of the Equal group problem

4.2 The Political Districting Problem

4.3 Other Applications

4.4 Programming the Algorithm

5. CONCLUSION AND FURTHER RESEARCH

6. APPENDIX
# 1. INTRODUCTION

## 1.1 Presentation of the problem

In many scientific areas (geography, urban planning, management science, medicine, etc.) there exist large sets of data. These sets represent specific collections of objects defined by a finite number of parameters. Over these sets, questions concerning the inner structure as well as the best representation are being asked.

These problems have been investigated in the domain of Clustering and Automatic Classification (See Anderberg [1] and Cormack [5] for a detailed review). However, most of the algorithm which were developed apply only a single criterion defined on the set of the data. This is mainly, as a consequence of the enormous number of feasible solutions and the complexity of clustering problems. However, there are many applications of clustering problems which involve more than one single criterion.

Particular cases of these multicriteria problems have been studied by various authors. The Political Redistricting was investigated by Hess et al. [18], using transportation alike heuristic method and Garfinkel and Nemhauser [12], [13], who used the set covering and exhaustive enumeration. Hess [17] studied the allocation of Salemens' territories.

The main features of these techniques are that they have been used for specific cases of the general problem. Although, that in some cases they were found useful, their main drawback are : lack of ability to process great quantities of data; algorithms do not always converge; they are slow and inefficient to implement in the computer.

These features underlined the development of another approach, not based on traditional Operations Research methods. Two algorithm mainly after the Dynamic Clustering Method (DCM) of Diday [6], Diday and Schroeder [8] were developed (Hanani and Tapiero [15], [16]), having
the capability to handle large bodies of data, and were applied
to resolve the combined Location Districting Problem and equal groups
partitioning.

Recently, a major effort was devoted to research in the area
of multicriteria decision making (MCDM), which involves problems with
several differing criterion. Apart from the social-psychological
aspects of this area of research (see Rapaport [26]). One faces the
question of finding the suitable mathematical tools for finding the
optimal solution defined by these multicriteria.

Such fields as Goal Programming and multiobjective planning
(see Kornbluth [20], Zeleny [29]) were developed using mainly,
classical analytic methods as well as mathematical programming
techniques.

However, these techniques impose severe requirements on the
criteria (either linearity, quadratic, good functional behaviour,
Smoothness, etc.), which are unapplicable in most clustering problems.
Therefore, there is a need of developing suitable multicriteria
clustering algorithms.

Practically speaking, these techniques should have the following
properties :

1) Handle great quantities of data.

2) Efficient in consuming memory and machine time.

3) Obtaining at least "near optimal" solutions.

4) Inclusion of multicriteria as well as constraints, which are imposed on the solution.

5) Ability to treat general type criteria and constraints,
as well as being flexible enough to changes in multicriteria
assessment and evaluation.
The first three points are the ordinary requirements of any
clustering method, and the rest are necessary in order to serve as
an efficient tool in multicriteria decision making environment.

In this paper we introduce a general algorithm, based also on
dynamic clustering, and developed in accordance to the above mentioned
requirements.

## 1.2 Models of Multicriteria Decision Making

### 1.2.1 General models

Following extensive research, various kind of multicriteria
and multi-objective decision problems have been solved. Linear multi-
objective were studied by Zeleny [29], while non-linear problems were dealt
by cubic splines techniques (Polak [25] . An exhaustive survey is given by
MacCrimmon [23] and by Johnsen [19].

In addition, there arises the question how to define the
preference among the various criteria. Set aside the psychological
factors, there exists the need to express in definite manner the ranking
of the criteria. This definition has of course, great influence
on the optimal solution, i.e. the optimum is derived by the order of
preference of all multicriteria, defining a unique utility function.

We can represent the MCDM problem as consisting of three
interconnected parts (see fig. 1).
<figure><img src="image_4.png" /><figcaption>Fig. 1</figcaption></figure>

In the process we clearly distinguish between two different parts. The first (B) defines the ranking order (preference) on the original problem (A), the second (C) resolves the problem in accordance to this ranking, enabling the decisions maker (DM) to examine the results (block D) and mainly using "personal judgement" to decide whether to halt the process having satisfactory results, or to carry on and define a new order of preference, for which the algorithm is applied again. The way this model represents to MCDM emphasizes the interactive aspects of this problem.

This approach necessitates, at each iteration to define in exact way a unique utility, by measuring the order of preferences. This can be achieved, for example by the displacement from the "Displaced Ideal" of Zeleny [30].

We adopt here the concept of "consistent family of criteria" after Roy [27]. For a family of criteria W, we have a set of functions $\{W_j\}_{j=1}^S$, mapping W into $\mathbb{R}^S$, such as :
$$ W_j(a) \to \mathbb{R}^+ \quad a \in A, \forall j \in ]S] $$
$$ (]S] \Leftrightarrow \{S\} = \{1, 2, \dots, S\} $$

when :

$$ 1) W_j(a) = W_j(a') \quad \forall j \in ]S] $$

⇔ a is indifferent to a'

$$ 2) \text{ If there exist at least one } i \in ]S] $$

such as $W_i(a) < W_i(a') \Rightarrow$

a is preferred to or indifferent to a'.

### 1.2.2 Criteria VS constraints

It is evident that the concept of criterion (or objective function) and constraint are interconnected. Each multi-constraint problem can be transfered to multicriteria problem, by minimization the deviation from the constraints. Roughly speaking, we can say that for each constraint there exists a criterion with "zero value" (which corresponds to sensitivity analysis in mathematical programming, Kornbluth [21]).

This can be formulated as follows :

the constrained problem :

$$ \text{optimize } \{W(\underline{X})\} $$

$$ \text{subject to : } g_i(\underline{X}) = b_i \quad \forall i $$

can be transformed to multicriteria problem :

$$ \text{minimize } \{|g_i(\underline{X}) - b_i|\} \quad \forall i $$

$$ \text{optimize } \{W(\underline{X})\} $$
Although, there remains the problem of ranking the
deviations from each constraint as well as the criteria W, this
formulation is better from point of view of the DM. That is, because
it enables changing the order of preference, and as it is stated by
Monarchi et al. [24] most of the time there is not an "optimal"
solution to the problem, but only "satisfactory" alternatives.

1.2.3 Urban Planning Example

Many applications of MCDM as well as clustering problems
can be found in the domain of Urbanic planning (Cliff [4], Wilson [28]).
We present here an example of locating public service facilities
(schools, public parks, etc.) with multiple criteria.

Given a set E of N points in two dimensional plan. Each
point represents demand for public service. It is asked to locate the
capability of handling at most B points of demand. In addition, the
urban planner wishes to locate the facilities as "nearer" as possible
to the demand points. i.e., minimize the sum of distances from all
points to their facility. It is assumed that the demand is equal at
all points.

The problem is formulated as follows :

$$
\text{Minimize} \quad \left\{
\begin{array}{l}
W_1 = K \\[1em]
W_2 = \sum_{i=1}^{K} \sum_{j=1}^{N} d_E (\mathbf{X}_j - \bar{\mathbf{X}}_i)^2 \delta_{ij}
\end{array}
\right\}
$$

$$
\text{s.t.} \quad \sum_{j=1}^{N} \delta_{ij} \leq B \quad \forall i \in \mathcal{K}
$$

$$
\text{when : } \delta_{ij} = \begin{cases} 1 & \text{X}_j \text{ is served by } \bar{X}_i \\ 0 & \text{otherwise} \end{cases}
$$

when $d_E$ stands for euclidean distance.
$\bar{X}_i, \forall i \in \mathbb{K}]$ stands for the location of the $i^{th}$ facility, and it can be computed as for example, as the center of mass (for exact definition see 3.1).

Assuming, $N_B = [N_B]$, and that the criterion of minimal number of facilities has more importance, we have equality constraints :

$$ \sum_{j=1}^{N} \delta_{ij} = B \quad \forall i \in \mathbb{K}] $$

Another approach is to relax the equal group constraint, and transform it to a corresponding criterion, minimizing it first.

The problem is multicriteria without constraints :

$$ \text{Minimize} \quad \left\{ \begin{array}{ll} W_1 = \sum_{i=1}^{K} \left| \sum_{j=1}^{N} \delta_{ij} - B \right| & \\ W_2 = \sum_{i=1}^{K} \sum_{j=1}^{N} d_E(X_j - \bar{X}_i) \delta_{ij} & \end{array} \right. $$

## 1.3 The Multicriteria Dynamic Cluster Approach

The last example has been solved by using dynamic clustering (Hanani and Tapiero [15]). However, the algorithm was built for specific constraints, as well as to be capable of handling one single constraint at a time (in addition to the original criterion).

Therefore, the inevitable question concerning the possibility of solving general multicriteria clustering problem is arise.

The approach presented here adopts the concept of "kernel", taken from Dynamic clusters method (Diday [6]). Actually, the kernel was used then to represent the original data in accordance to some specific criterion. For example, notions such as center of gravity, the best K-means, were used as kernels.
Here, we generalize the role of kernels, and use multi-kernel
to represent multicriteria, serving as tools to optimize the latter.
Over these structures, some order of preference is defined, expressing
ranking of criteria, as well as the relative importance of the original
constraints.

In the following paragraph, this general algorithm is presented.

2. THE MULTICRITERIA DYNAMIC CLUSTERS ALGORITHM (MDC)

2.1 Notation

Let E be a finit subset E ∈ Rq

- P : the set of all possible partition of E

- $P_K$: the set of all partitions of E into K classes, and P an element as :

$$
P \in P_K \Leftrightarrow P = (P_1, \dots, P_K)
$$

We introduce S spaces of representations and we note :

- $\mathbb{L}^S$: $$ \begin{pmatrix} \mathbb{L}^1 \\ \vdots \\ \mathbb{L}^S \end{pmatrix} $$ the space of representation.

- $\mathbb{L}_K^j$: the set of all K-uples of $\mathbb{L}^j$ :

$$
L^j \in \mathbb{L}_K^j \iff \begin{array}{l} L^j = (\lambda_1^j, \lambda_2^j, \dots, \lambda_K^j) \\ \text{where } \lambda_i^j \in \mathbb{L}^j \ \forall i \in \mathbb{J} \ \mathbb{K} \end{array}
$$

$$
\text{where } \mathbb{L}_K^j = \mathbb{L}^j \times \mathbb{L}^j \times \dots \times \mathbb{L}^j \text{ (K times)}
$$

- $\mathbb{L}_K^S$: the set of all K-uples of all $j \in \mathbb{J}$ s]

$$
\mathbb{L}_K^S = \begin{pmatrix} \mathbb{L}^1 \\ \mathbb{L}^2 \\ \vdots \\ \mathbb{L}^K \end{pmatrix}
$$
let $\underline{L}^S$ be an element of $\mathbb{L}_K^S$ then write :

$$ \underline{L}^S = (\lambda_1^S, \dots, \lambda_K^S) $$

$$ \text{where } \lambda_i^S = \begin{pmatrix} \lambda_i^1 \\ \vdots \\ \lambda_i^s \end{pmatrix} \in \begin{pmatrix} \mathbb{L}^1 \\ \vdots \\ \mathbb{L}^s \end{pmatrix} $$

$$ \text{then } \underline{L}^S \in \mathbb{L}_K^S \Rightarrow \underline{L}^S = \begin{pmatrix} \lambda_1^1 & \cdots & \lambda_K^1 \\ \vdots & \ddots & \vdots \\ \lambda_1^s & \cdots & \lambda_K^s \end{pmatrix} $$

- $\underline{W}$ : denotes a set of criterion $W_j$, $j \in ]s]$, where,

$$ \underline{W} : \mathbb{P}_K \times \mathbb{L}_K^S \to (\mathbb{R}^+)^S $$

$$ \underline{W} = (W_1, W_2, \dots, W_s) $$

Each $W_j$, $\forall j \in ]s]$, $w_j$ is an application

$$ W_j : \mathbb{P}_K \times \mathbb{L}_K^j \to \mathbb{R}^+ $$

There are many alternatives to measure the criteria $\underline{W}$. In order to implement it, we have to introduce the notions of "multi metric" $\underline{D}$ a monotonic operation $\oplus$ over $\underline{D}$, defined in $(\mathbb{R}^+)^S$, and a corresponding order $\preceq$; an example of this order is the lexicographyc order over $\mathbb{R}^S$.

This monotonic operation $\oplus$ is defined as follow :

$$ A \preceq B, \quad C \preceq D \Rightarrow A \oplus C \preceq B \oplus D $$

Let $D_j$ be an application of $E \times \mathbb{L}_K^j \to \mathbb{R}^+$

$$ (x, \lambda_i^j) \to D_j (x, \lambda_i^j) $$

this function expresses "distance" between an element $x$ and a kernel $\lambda_i^j \in \mathbb{L}_K^j$

The multimetric $\underline{D}$ is an application of $E \times \underline{\mathbb{L}}^S \to \mathbb{R}^+$ such as

$$ D (x, \lambda_i^S) = \begin{pmatrix} D_1 (x, \lambda_i^1) \\ \vdots \\ D_s (x, \lambda_i^s) \end{pmatrix} $$

the summation $\sum_{x \in P_i} D_j (x, \lambda_i^j)$ expresses "distance between a kernel $\lambda_i^j$ and the classe $P_i$ of the K-partition of P.
The way to associate a K-partition with K-tuples of kernels,
will then be given by the application F :

$$
\mathbb{L}_K^S \to \mathbb{P}_K
$$

$$
\underline{L}^S = (\lambda_1^S, \lambda_2^S, \dots, \lambda_K^S) \implies F(\underline{L}^S) = P = (P_1, \dots, P_K)
$$

actually $\lambda_i^S$ is a column vector consisting of s $\lambda_j^i$ coordinates $j \in ]s]$

The application F is such that element X ∈ E is chosen to be
attached to multi-kernel λᵢ<sup>S</sup>, than any other λ<sub>ℓ</sub><sup>S</sup> ℓ ≠ i, as :

$$
P_i = \{ X \in E \mid \underline{D}(X, \lambda_i^S) \le \underline{D}(X, \lambda_\ell^S) \quad \forall \ell \in \mathbb{J} \}
$$

in case of equality X is assigned to the class of least index

In other words, Pᵢ is built by choosing the elements of E, which
are "nearer" (in terms of multidistance D) to λᵢ, than any other multi-
kernels λᵢ.

In order to associate a K-tuple multi-kernel to a K-partition,
we introduce the operator G :

$$
P_K \to \mathbb{L}_K^S
$$

$$
P = (P_1, \dots, P_K) \Rightarrow G(P) = \underline{L}^S = (\lambda_1^S, \lambda_2^S, \dots, \lambda_K^S)
$$

$$
G(P) = \begin{pmatrix} g_1(P) \\ \vdots \\ g_s(P) \end{pmatrix}
$$

G is an operator which consists of S functions g<sub>j</sub>(P), each
g<sub>j</sub> is defined by :

$$
g_j(P) = L^j = (\lambda_1^j, \dots, \lambda_K^j),
$$

where each $\lambda_i^j, \forall i \in ]K]$ is given by the elements of $\mathbb{L}^j$ which minimize

$$
\sum_{x \in P_i} D(P_i, \dots)
$$
Meaning that $\lambda_i^j$ is chosen from the whole space of $L^j$, as
the "nearest" (in terms of $D_j$) to $P_i$, and one which "represents"
in the best way the class $P_i$ (also in terms of $D_j$).

The analytic expression of optimizing the multicriteria is then by
using the notation of Dynamic Clustering :

$$
\text{Minimize } \underline{W}(P, \underline{L}^S) = \sum_{i \in \mathcal{I}} \sum_{K} \sum_{X \in P_i} \underline{D}(x, \lambda_i^S)
$$

The problem we are confronted with is :

$$
\text{Minimize } \underline{W}(v) \text{ for all } v \in \mathcal{P}_K \times \underline{L}_K^S
$$

2.2 The algorithm

The MDC algorithm consists of two major sequences :

$$
\{v_n\} \in \mathbb{P}_K \times \underline{L}_K^S, \text{ i.e. } v_n = (P^{(n)}, \underline{L}^{S, (n)})
$$

and

$$
u_n = \underline{W}(v_n) \in (\mathbb{R}^+)^S
$$

Let $P^{(o)} \in \mathbb{P}_K$ be an initial K-partition (chosen or be drawn by random trial). Then $\underline{L}^{S,(o)}$ is computed by :

$$
\underline{L}^{S, (o)} = G(P^{(o)})
$$

in a sequential operations :

$$
L^j, (o) = g_i(P^{(o)}) \quad \forall j \in \mathcal{I}_s
$$

which constitutes the first couple $v_1 = (P^{(o)}, \underline{L}^{S,(o)})$.

The sequence {$v_n$} is defined recursively :
$v_{n+1} = (P^{(n+1)}, \underline{L}^S, (n+1))$ is deduced from $v_n$ by :

$$P^{(n+1)} = F(\underline{L}^S, (n))$$

$$\text{and } \underline{L}^S, (n+1) = G(P^{(n+1)}) = \begin{pmatrix} g_1 & (P^{(n+1)}) \\ \vdots & \\ g_s & (P^{(n+1)}) \end{pmatrix} \quad \text{(see fig. 2).}$$

## 2.3 Relation between MDC and DCM

The MDC algorithm is a generalization of DCM algorithm. It can be obviously seen, that reducing the number of criteria S to 1, by substituting $S = \{1\}$, we have the DCM algorithm, and the following relationship holds :

Operator $G \to g$ function of representation

Operator $F \to f$ function of allocation

the multicriteria :

$$\underline{W} \to W$$

the multimetric :

$$\underline{D} \to D$$

the space of representation :

$$\underline{L}^S \to \underline{L}$$

the multi-kernel :

$$\lambda_i^S \in \underline{L}^S \to \underline{L}_i \in \underline{L}$$

the operation $\oplus$ is reduced to the usual ("+") operation defined in $\mathbb{R}^+$.
And the order relation $\prec$ is reduced to the usual "<" order relation defined in $\mathbb{R}^+$.

In practical manner, the usage of multiple kernels enables us to treat each criterion directly. Each sort of a kernel is defined for its appropriate criterion as in the DCM algorithm, the kernels are defined as representations of the classification from a point of view of the multicriteria $\underline{W}$.
<figure><img src="image_5.png" /><figcaption>Fig. 2 - The MDC algorithm</figcaption></figure>
The major question that we are confronted with in the MDC algorithm, is the various properties of the multicriteria function $\underline{W}$, as well as the multimetric $\underline{D}$, and the special order relation defined by it.

This mainly, implies looking for the sufficient conditions for the convergence of MDC.

In other words, having a specific multicriteria problem, we have to transfert it to a function $\underline{W}$ (which implies a specific order relation in$(\mathbb{R}^+)^S$) as well as defining a multidistance $\underline{D}$ (and F and G operators) such as will minimize $\underline{W}$ in terms of the order relation chosen.

## 2.4 The convergence of MDC

### 2.4.1 Theorem of convergence

Before presenting the convergence of the MDC algorithm, we have to investigate the properties of the multi-distance $\underline{D}$.

Without any loss of generality, we assume the following (see remark 2) :

**Hypothesis** : $D_j(A, .), \forall j \in ]s]$ is defined as such as there is a unique minimum for it, for $\forall A \in \mathcal{P}$, independent of any $D_\ell(A, .) \ell \in ]s]$ $\ell \neq j$.

**Corollary 1** : For $\underline{D}(A, .) = (D_1(A, .), ..., D_s(A, .))$ there exists a unique minimum for $\forall A \in \mathcal{P}$.

**Proof** : $\underline{D}$ is a S-tuple of metric $D_j$. In accordance to our hypothesis, $D_j(A, .), \forall j \in ]S]$ attains its own unique minimum. Let denote it as : $D_j(A, \lambda^{j*})$.

Therefore, the multi-distance $\underline{D}$ has a point where :

$$ \underline{D}(A, \lambda^{S*}) = (D_1(A, \lambda^{1*}), ..., D_s(A, \lambda^{S*})) $$
The value $\lambda^{S*}$ must be the minimum of $\underline{D}(A, \cdot)$, otherwise there
is a $\lambda^{S**}$ such as :

$\underline{D}(A, \lambda^{S**}) \oplus \underline{D}(A, \lambda^{S*})$ and as a result of the order over $(\mathbb{R}^{+})^S$
$\Rightarrow \exists m \in \mathbb{S}] \ D_m(A, \lambda^{m**}) < D_m(A, \lambda^{m*})$

which contradicts the minimality of $\lambda^{m*}$, as was stated earlier.

Q.E.D.

(from here on, we drop the special sign of the order relation $\oplus$ when it is
unnecessary).

**Corollary 2** : $\underline{D}(A, \lambda) = \sum_{a \in A} \underline{D}(a, \lambda)$

**Proof** : This corollary is immediatly obtained by the definition of
the algorithm and remark 1, concerning the monotony of the order
$\oplus$ (see 2.4.2. for a detailed exposition concerning the necessity of
this corollary).

The convergence of the algorithm is assured by the following
theorem.

**Theorem 1 :**

(i) The sequence $u_n = \underline{W}(v_n)$ is monotonically decreasing, converging and attains its limit.

(ii) The sequence $v_n = (p^{(n)}, \underline{l}^{S, (n)})$ is stationary - i.e., $\exists N, \forall n > N, v_n = v_{n+1}$

**Proof** : To demonstrate the decreasing of $\{u_n\}$, we have to show the inequalities :
$$1) \quad u_n = \underline{W}(P^{(n)}, \underline{L}^S, (n)) \le \underline{W}(P^{(n)}, \underline{L}^S, (n-1))$$

$$2) \quad \underline{W}(P^{(n)}, \underline{L}^S, (n-1)) \le \underline{W}(P^{(n-1)}, \underline{L}^S, (n-1)) = u_{n-1}$$

The first inequality is, in a matter of fact, the sum over all $i \in ]K]$ of:

$$\underline{D}(P_i^{(n)}, \underline{L}_i^S, (n)) \le \underline{D}(P_i^{(n)}, \underline{L}_i^S, (n-1))$$

which holds because of the definition of G.

Therefore, summing over $i$:

$$u_n = \underline{W}(P^{(n)}, \underline{L}^S, (n)) \le \underline{W}(P^{(n-1)}, \underline{L}^S, (n-1))$$

The second inequality may be written:

$$\sum_{i=1}^{K} \sum_{X \in P_i^{(n-1)}} \underline{D}(X, \underline{L}_i^S, (n-1)) \le \sum_{i=1}^{K} \sum_{X \in P_i^{(n-1)}} \underline{D}(X, \underline{L}_i^S, (n-1)) = u_{n-1}$$

Which is true after corollary 2 and the definition of F which takes for a multi-kernel $\underline{\lambda}^S, (n-1)$ a better partition $P^{(n)}$ than $P^{(n-1)}$. This proves the monotonic decreasing of $\{u_n\}$. In addition, the set of all K-partition of E. $P_K$ is finite (for demonstration see Even [9]). Therefore, the set of all kernels $\underline{L}_K^S$ obtained by $G(P_K)$ is also finite, thus the set of all $\underline{W}(v_n)$ is also finite.

Summing up, $\{u_n\}$ is a monotonic decreasing sequence on a finite set in $(\mathbb{R}^+)^S$, and is stationary. Every stationary sequence in $(\mathbb{R}^+)^S$ is converging. Moreover, because of the finiteness of $\{u_n\}$, there exists such a $N$ as:

$$\forall N > N, \quad u_n = u_{n+1} = u_N \quad \text{which completes the proof of part (i).}$$

In order to prove part (ii), we have to show that $\exists N, v_{N+1} = v_N$ and actually that:
From part (i) we know that :

$$ \exists N, \forall n \ge N \quad v_{n+1} = v_n \quad \text{or} \quad \underline{W}(v_{n+1}) = \underline{W}(v_n) $$

By the definition of G we have :

$$ G(P^{(n)}) = \underline{L}^{S, (n+1)} $$

$$ \text{In addition } \underline{L}^{S, (n+1)} = \underline{L}^{S, (n)} $$

$$ \text{as otherwise } \underline{L}^{S, (n+1)} \neq \underline{L}^{S, (n)} \\ \Rightarrow \underline{W}(v_n) > \underline{W}(P^{(n)}, \underline{L}^{S, (n+1)}) $$

which entails by the definition of F :

$$ \underline{W}(v_n) > \underline{W}(v_{n+1}) \text{ which contradicts } u_n = u_{n+1}. $$

$$ \text{In addition, } \underline{L}^{S, (n+1)} = \underline{L}^{S, (n)} \text{ by the same reasoning} $$

$$ \Rightarrow P^{(n+1)} = P^{(n)} $$

$$ \Rightarrow v_n = v_{n+1} $$

In other words, we have shown that $\exists N, \forall n > N$

$$ v_n = v_{n+1} $$

Q.E.D.

It should be noted that the optimum that the sequences $u_n$ and $v_n$ attain is a Local Optimum. Which means that, there is a neighbourhood in $(\mathbb{R}^+)^S$ over which $\underline{W}(P^{(N)}, \underline{L}^{S, (N)})$ is an optimum. However, a value $u^* = \underline{W}(P^*, \underline{L}^*)$ is a Global Optimum (minimum) if :

$$ \underline{W}(v^*) \le \underline{W}(v) \text{ for } \forall v \in \mathbb{P}_K \times \underline{L}_K^S $$
Therefore, for a value $v^*$, given by the MDC algorithm, this inequality holds for a set of $v$ which are only a part of $P_K \times L_K^S$. For further details on this subject see Diday [7].

### 2.4.2. Sufficient condition to the convergence

The proof of part (i) of theorem 1 is partially based on proving the inequality :

$$ \underline{W}(P^{(n)}, \underline{L}^S, (N-1)) \le \underline{W}(P^{(n-1)}, \underline{L}^S, (n-1)) = u_n $$

meaning that the operator $F$ decreases the multicriteria $\underline{W}$. Corollary 2, or actually, the hypothesis which underlines it, saying that $\forall j \ D_j(A, \lambda_j^j) = \sum_{X \in A} D_j(X, \lambda_j^j)$ is sufficient to prove this inequality, but it is not necessary one.

It is evident that we wish to have a "weaker" condition for this proof. Such a necessary condition, can be formulated by the introduction of function $\underline{R}$ as follows.

**Definition (Diday and Schroeder [8]):** Function $\underline{R}$

$(\underline{R} = \{R_j\}_{j=1}^s) \text{ is called semi-square if :}$

$$ \left. \begin{array}{l} R_j(\lambda_j^j, i, P_i) = \sum_{X \in P_i} D_j(X, \lambda_j^j) \\ \\ W_j(V_j) = \sum_{i \in \underline{K}] \cup \underline{K]}} R_j(\lambda_i^j, i, P_i) \end{array} \right\} \forall j \in \underline{S} $$

such as :

$$ \forall P \in F(\underline{L}_K^S), \ \underline{W}(F \circ G(P), G(P)) \le \underline{W}(P, G(P)) $$

**Corollary 3:**

$$ \underline{W}(P^{(n)}, \underline{L}^S, (n-1)) \le \underline{W}(P^{(n-1)}, \underline{L}^S, (n-1)) $$

iff $\underline{R}$ is semi-square.
**Proof** : Actually, the definition of $\underline{R}$ as semi-square is equivalent to the desired result.

$$ \underline{R} \text{ semi-square} \iff \underline{W}(\underline{F} \circ \underline{G}(\underline{P}^{(n-1)}), \underline{G}(\underline{P}^{(n-1)}) \le \underline{W}(\underline{P}^{(n-1)}, \underline{G}(\underline{P}^{(n-1)})) \\ \text{and as } \underline{G}(\underline{P}^{(n-1)}) = \underline{L}^{\underline{S}, (n-1)} \text{ and } \underline{F}(\underline{L}^{\underline{S}, (n-1)}) = \underline{P}^{(n)} \\ \iff \underline{W}(\underline{P}^{(n)}, \underline{L}^{\underline{S}, (n-1)}) \le \underline{W}(\underline{P}^{(n-1)}, \underline{L}^{\underline{S}, (n-1)}) $$

Q.E.D.

### 3. CLUSTERING WITH EQUAL GROUP CONSTRAINT

#### 3.1 The problem

Following is a detailed example to the application of the MDC. The problem we are confronted with is to find the most K densed clusters, under the equal size group constraint, which is special case of the example in 1.2.3.

For a matter of simplicity, we deal with euclidean space $E \subset \mathbb{R}^2$, when each $X \in E$ is described by $X = (X^1, X^2)$.

In mathematical programming terms, the problem is written as :

$$ \begin{array}{ll} \text{Min} & \displaystyle \sum_{i=1}^{K} \sum_{j=1}^{N} \{(\bar{X}_j^1 - \bar{X}_i^1)^2 + (\bar{X}_j^2 - \bar{X}_i^2)^2\} \delta_{ij} \\ \text{s.t.} & \sum_{j=1}^{N} \delta_{ij} = B \\ & \forall i \in \underline{K} \quad (N=\text{card}(E)) \end{array} $$

where

$$ \delta_{ij} = \begin{cases} 1 & X_j \in P_i \quad (P_i \text{ is cluster } i \in \underline{K}) \\ 0 & \text{otherwise} \end{cases} $$

and $\bar{X}_i = (\bar{X}_i^1, \bar{X}_i^2)$ is the center of gravity of cluster i given by

$$ \bar{X}_i^\ell = \frac{\sum_{j=1}^{N} X_j^\ell \delta_{ij}}{\sum_{j=1}^{N} \delta_{ij}} \quad \ell = 1, 2 \quad \forall i \in \underline{K} \quad (\text{see remark 3}) $$

when $B = N/K$ ($N = \text{card}(E)$)
In other words, we are looking for the least inner
variance K-partitioning, when the groups obtained must be equal sizes.
This problem has many modification, and has been approached dynamic
programming with weight function (Lechevallier [22]).

We present here the problem with slight modification,
relaxing the constraint into a second criterion, as follows.

$$
\text{Minimize} \quad \left\{
\begin{array}{l}
W_1 = \sum_{i=1}^{K} \sum_{j=1}^{N} \{(X_j^1 - \bar{X}_i^1)^2 + (X_j^2 - \bar{X}_i^2)^2\} \delta_{ij} \\
\\
W_2 = \sum_{i=1}^{K} |B - \sum_{j=1}^{N} \delta_{ij}|
\end{array}
\right\}
$$

the rest, is the same as the presentation above.

In this version of the problem, we wish to find the
minimum of W₂, for which the K-partition is as dense as possible.

3.2 The MDC algorithm

In order to apply the MDC algorithm to this problem we have to
define the couple (D, λ), as well as the multicriteria W, and the
operators F and G.

But, in the beginning we have to state what is the order of
preference. It is defined as the reverse lexicographic order, as
follows

$$
A = \begin{pmatrix} a_1 \\ a_2 \end{pmatrix} ; \quad B = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}
$$
$$A \preceq B \Leftrightarrow a_2 < b_2 \text{ or}$$

$$a_2 = b_2 \text{ and } a_1 \le b_1 \text{ (see remark 4)}$$

### 3.2.1 The Kernels

For the first criterion $W_1$ (minimum variance), we define the kernel as the center of gravity $\bar{X}_i$ of each class $P_i$.

$$L_K^1 = \{ (\lambda_1^1, \lambda_2^1, \dots, \lambda_K^1) / \lambda_i^1 \in L^1 \} \in L_K^1$$

$L^1$ is the set of all feasible centers of gravity in $\mathbb{R}^2$.

The second criterion $W_2$ expresses the minimization of deviations from equal size classes. In order to apply on appropriate kernel, we define the second kernel as a circle in plane containing B points of E, the origin of the circle is situated in the center of mass of the suitable class. Therefore kernel $\lambda^2$ is as follows.
$$ \underline{L_K}^2 = \{ (\lambda_1^2, \lambda_2^2, \dots, \lambda_K^2) / \lambda_i^2 \in \underline{\mathbb{L}}^2 \} \in \underline{\mathbb{L}}_K^2 $$

The space $\underline{\mathbb{L}}^2$ is the set of all triplets

$$ \lambda_i^2 = (r, C, B) \in \mathbb{R}^+ \times \mathbb{R}^2 \times \{B\} $$

$r \in \mathbb{R}^+$, $C = (C_1, C_2) \in \mathbb{R}^2$ and $B$ define a circle in $\mathbb{R}^2$, having a radius $r$, origin $C = (C_1, C_2)$ and containing exactly $B$ points of $E$ (whenever this circle is not defined, i.e., there are $B+m$ points in $\lambda_i^2$, $1 \le m \le \text{card}(E) - B + 1$, we change one point which is on the surface of $\lambda_i^2$, by moving it by some small distance $\Sigma > 0$).

### 3.2.2 The Multimetric

$$ \underline{D} = (D_1, D_2) \rightarrow (\mathbb{R}^+)^2 $$

$$ D_1 : E \times \underline{\mathbb{L}}^1 \rightarrow \mathbb{R}^+ $$

$$ (X, \lambda_i^1) \rightarrow D_1(X, \lambda_i^1) = d_E(X, \lambda_i^1) = (X^1 - \bar{X}_i^1)^2 + (X^2 - \bar{X}_i^2)^2 $$

$$ D_2 : E \times \underline{\mathbb{L}}^2 \rightarrow \mathbb{R}^+ $$

$$ (X, \lambda_i^2) \rightarrow D_2(X, \lambda_i^2) = \begin{cases} 0 & d_E(X, C(\lambda_i^2)) \le r(\lambda_i^2) \\ 1 & \text{otherwise} \end{cases} $$

### 3.2.3 The applications G and F

$$ G = (g_1, g_2) $$

$$ \underline{L}^1 = g_1(P) $$

$$ (P, \lambda_i^1) \rightarrow \min_{\lambda_i^1 \in \underline{\mathbb{L}}^1} \sum_{X \in P_i} D_i(x, \lambda_i^1) = \min_{\lambda_i^1 \in \underline{\mathbb{L}}^1} \sum_{X \in P_i} d_E(X, \lambda_i^1) $$
$$L^2 = g_2(P)$$

$$ (P, \lambda_i^2) \rightarrow \min_{\lambda^2 \in \mathbb{L}^2} \sum_{X \in P_i} D_2(x, \lambda_i^2) $$

It should be noted that looking for the "best" circle $\lambda^2$, would be a consuming time process, therefore we allow the origin $C = (C_1, C_2)$ of $\lambda_i^2$ to be only the points of $P_i$ $i \in ]K]$

$$F: L^2 \rightarrow P$$

We build the classes $P_i$ by the following procedure :

$$ P_i = \left\{ X \in E / \begin{pmatrix} D_1(X, \lambda_i^1) \\ D_2(X, \lambda_i^2) \end{pmatrix} \stackrel{\le}{\subseteq} \begin{pmatrix} D_1(X, \lambda_\ell^1) \\ D_2(X, \lambda_\ell^2) \end{pmatrix} \quad \begin{array}{l} \forall \ell \in ]K] \\ \ell \neq i \end{array} \right\} $$

(in case of equality, X is assigned to the least order i class).

### 3.2.4 The Multicriteria W:

$$ \underline{W} : \mathbb{P}_K \times \mathbb{L}_K^2 \rightarrow (\mathbb{R}^+)^2 $$

$$ \underline{W} = (W_1, W_2) $$

$$ W_1(P, L^1) = \sum_{i=1}^{K} \sum_{X \in P_i} D_1(X, \lambda_i^1) = \sum_{i=1}^{K} \sum_{X \in P_i} d_E(X, \bar{X}_i) $$

$$ W_2(P, L^2) = \sum_{i=1}^{K} \sum_{X \in P_i} D_2(X, \lambda_i^2) $$

To measure $\underline{W}$, we apply the same reverse lexicographic order over$(\mathbb{R}^+)^2$ as defined earlier in 3.2.
### 3.3 Study of convergence

The sufficient conditions assuring the convergence of MDC to a local minimum, developed in the above discussion are fully fulfilled by $\underline{D}$ chosen $j$, i.e. there exists a unique minimum for $D_j(A, \cdot)$, $j = 1,2$, over $A$, as well as $D_j(A, \lambda^j) = \sum_{a \in A} D_j(a, \lambda^j)$, $j = 1,2$.

In addition, the reverse lexicographic order defined is monotonic. Therefore, in accordance to Theorem 1, the algorithm applied to this problem, converges.

The minimal solution "tends" to obey the equal group constraint.
### 3.4 An Artificial Example

Let E be a set of 8 points as shown in Fig. 3 (a). It is asked to find a partition of two equal classes (B = 4).

In Fig. 3 (b) an initial random solution is drawn. Class 1 is denoted by points , and class 2 by the sign "X". In the first iteration centers of gravity ($\lambda^1$) are chosen (denoted by the same symbol with two circle ). After the second kernel are computed ($\lambda^2$), we have in Fig. 3 (c), two groups which are not equal. However, in iteration 2 better kernels are computed, and the solution obtained by iteration 3 (Fig. 3 (d)) is optimal.

<figure><img src="image_6.png" /><figcaption>Fig. 3 (a) Original data</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 3 (b) Iteration 1</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 3 (c) Iteration 2</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 3 (d) Iteration 3</figcaption></figure>

<caption>Fig. 3</caption>
# 4. OTHER MODIFICATIONS AND APPLICATIONS OF MDC

## 4.1 Modification of equal groups problem

The selection of the second type of kernel ($\lambda_i^2$) in the equal groups constrained problem, is relatively simple to compute. However, it is obvious that due to the overlapping of circles, it is not fast enough.

Another approach would be to search these kernels, as those surfaces in $\mathbb{R}^2$ such as they include exactly B points of E, and $\lambda_i^2 \cap \lambda_j^2$, $\forall i, j \in \mathbb{K}$. This condition assures the exclusiveness of the circles chosen.

In practice, this approach is less favourable due to two drawbacks. First, it implies looking for surface in the plane rather than circle, which is cumbersome and necessitates complicated computation.

Secondly, there is a need to find all feasible solutions to the allocation problem for all elements of E, i.e. determining mappings of E into equal groups, and choosing the best solution. Which is as a matter of fact, coming back to the original enumeration method, which we want to refrain from, by using clustering.

However, one should note the variety of special case algorithms which find the solution of our problem. Instead of circles, we can choose other kinds of geometrical shapes, as triangles, squares, etc.

Another approach would be to choose the second type of kernels ($\underline{L}^2$), as those points in the classes which are responsible for the deviation from the equal group constraint, and to replace $D_2$ by some other function; or to define $\underline{L}^2$ as some diameter depending on these points.
Summing up, in this example of the application of the general algorithm, we can notice the variety and the inclusiveness of its nature, enabling us to analyze vast family of different algorithm as an one "family" of techniques.

## 4.2 The Political Districting Problem

The equal group constrained problem is a special case of another problem named the Political Districting or the "voting problem". Here, instead of geographic coordinates only, we have a set of parameters consisting of the previous parameters, as well as an additional one. In the voting problem it is the number of voters at each points $t_j$, therefore $X_j \in E$, $X_j = (X_j^1, X_j^2, t_j)$. The constraint expresses the wish to have at each group a specific number of voters (actually the sum of all $t_j$ divided by the number of groups).

We will not discuss here the exact formulation of this problem (see appendix in Hess et al. [18]) and its solution by multicriteria clustering, to which another paper is devoted. However, it is obvious that the second type of kernel used here, is a set of circles which include a specific sum over parameter $t_j$ (notice that in equal group problem we have $t = t_j = 1 \forall X_j \in E, X_j = (X_j^1, X_j^2, 1)$).

## 4.3 Other Applications

Besides the applications in Urban Planning there exists some other fields of research, in which other variants of the equal groups problem, as well as the voting problem, exist.

For example, applications in computer science and information Systems should be mentioned. Namely, the restructuring of computer programs (Ferrari [10]), the paging problem in virtual storage operating system, (Babonneau et al. [2]), the reorganization of Data Base (Flory et al. [11]), and locating central processing units (CPU) in a computer network (Chang and Tang [3]).
In all these applications, there exists a set of data over which some criterion (sometimes multicriteria) is defined, as well as some constraints, which have the same formulation discussed above. In spite of the different properties of each application, we can formulated them by terms of multicriteria clustering and apply the MDC algorithm.

### 4.4 Programming the Algorithm

In order to implement the MDC algorithm by an efficient program, we have to take into consideration the trade-off between CPU-time and memory size. In addition, there arises the question : how to implement various application (types of different kernels) in one program, which concerns highly sophisticated methods of programming.

Therefore, the program which was written in Advanced Fortran (CDC FTN Fortran), used a storage which is (approximatly) linear of the number of points N. The program was constructed to solve the equal group constrained problem (with slight modification of the algorithm, for details see appendix and Hanani [14], Hanani and Tapiero [15]).

## 5. CONCLUSION AND FURTHER RESEARCH

This paper presented a general multicriteria decision making clustering model. By generalizing the concept of kernels (taken from Dynamic Clustering terminology), we formulated a general Multicriteria Dynamic Clustering algorithm, and showed that its properties of convergences are actually the same as the ordinary Dynamic Cluster algorithm. therefore, having a complete compatibility of the general algorithm (MDC) and its particular case (DCM).

This highly sophisticated algorithm can be immediatly applied to many MCDM problem.

In addition, we demonstrated by detailed example, a general method to solve vast family of MCDM and constrained problems.
However, this is only a first step, and further research has to be made in the following domains:

1) The extension of $F$ operator in the same manner as $G$, using family of function $\{f_j\} = F$.

2) The study of the globality of solution

3) The inclusion of the number of classes $K$ as a criterion.

4) Using other methods (linear programming minimal spanning trees, etc.) for $\{g_i\}$, as well as modifications on $\mathbb{R}$ and $\mathcal{D}$.

5) Other applications in various branches of scientific research.
## Acknowledgments

The author wishes to thank Prof. C.S. Tapiero and Prof. E. Diday, for their consistent help and encouragement in writing this article. Thanks are also due to S. Toledano for the MND program, which serves as a base to MDC program, and to J.SID1 which kind by reviewed and corrected this paper in its last version.
# APPENDIX

## THE PROGRAM

The program was designed to solve equal group clustering
($B = N/K = [N/K]$).

There was a slight modification in the algorithm, as follows.

The equality constraint was treated as a "zero value" criterion, i.e., the second type kernel was non-overlapping surfaces in plane. However, to avoid the cumbersome computation of solving many allocation problems (see 4.1) a local minima for $L^2$ was chosen, as well as appropriate $D_2$ distance.

The first kernel $L^1$, was chosen as a group containing exactly B points (its origin coincides with the center of mass of the class).

In Fig. 4 the data set E is presented. There are 110 points on the X-Y plane (this data represents real population dispersed in urban region). An equal group partitioning was attained (Fig. 5) by a computation consuming only 6 sec. CPU-time and approximately 25 K of memory, in CDC CYBER-74 computer.

Notice that the two coordinates are not in the same scales (X-scale is greater than Y-scale as 3:2), therefore the groups are as spread along X axis; and due to an overlapping of points in the computer drawing, there are actually less points in the drawing.
<figure><img src="image_10.png" /><figcaption>Fig. 5 - Equal group partitioning</figcaption></figure>
**Remark 1:**

The usage of the summation by $\Sigma$ implies using the law $+$
defined as usual in $\mathbb{R}$. However, we can introduce any other law $\oplus$,
which holds in some space $\mathbb{R}^*$, which will obeys the monotonic properties.
Therefore, having some other sense of "summation" $\Sigma^*$.

Actually, the following presentation of the algorithm will hold
on to the above mention formalization as well.

**Remark 2 :**

In fact there is, at least formally, a loss of generality in
assuming this hypothesis. However, following the formalization of
DCM algorithm (Diday [8]), this hypothesis is usually drawn.

**Remark 3 :**

Other method to express the notion of the center of gravity
of groupe $P_i$ is by looking for a point $X^*$ such as :

$$
D(X^*, P_i) \inf_{X \in \mathbb{R}^2} D(X, P_i)
$$

**Remark 4 :**

In general we define the reverse lexicographic order
for s attributes as :

<figure><img src="image_11.png" /></figure>

$$
\Leftrightarrow \exists m, s \ge i > m \quad a_i = b_i, \text{ and } a_m < b_m
$$
BIBLIOGRAPHY

[1] ANDERBERG, M.R., "Cluster Analysis for Applications", Academic Press, 1973.

[2] BABONNEAU, J.Y., et al. "Automatic and General Solution to the Adaptation of Programs in a Paging Environment", 6<sup>th</sup> ACM Symposium on Operating Systems Principles (nov. 1977), 109-116.

[3] CHANG, S.K., and D.T. TANG "Processor Allocation in a Distributed Computer System", *Proceeding of Computer network Symposium*, Maryland, 1975, 47-54.

[4] CLIFF, A.D., et al. "Elements of Spatial Structures, A Quantitative Approach", Cambridge University Press, Cambridge, England 1975.

[5] CORMACK, R.M., "A Review of Classification", *J.R. Statist. Soc.*, Series A, 134, 3, (1971), 321-367.

[6] DIDAY, E., "Nouvelles méthodes et nouveaux concepts en classification automatique et reconnaissances des formes", *These d'Etat*, 1972.

[7] DIDAY, E., "The Dynamic clusters Method and Optimization in non Hierachical clustering", *IFIP 73* (Rome), Springer-Verlag Berlin, 1973, 241-252.

[8] DIDAY, E., and SCHROEDER A., "A New Approach in Mixed Distribution Detections", *RIARO*, 10, 6, June 1976, 75-106.

[9] EVEN S., "Algorithms Combinatories", Macmillan Comp., 1973

[10] FERRARI D., "Improving Program Locality by Strategy-Oriented Restructuring", *IFIP 74*, 266-270.
[11] FLORY, A., et al., "Data Base Reorganization by Clustering Methods", *Information Systems*, 3, 1978, 59-62.

[12] GARFINKEL R.S., and NEMHAUSER G.L. "Optimal Political Districting by Implicit Enumeration Techniques", *Management Sciences*, 16 (April 1970), B-495-B-508.

[13] GARFINKEL R.S., and NEMHAUSER G.L. "*Integer Programming*", Wiley & Sons, N.Y., 1972.

[14] HANANI U. "The Solution of the Partitioning Problems by Dynamic Clusters Method", *Thesis*, Hebrew University of Jerusalem, Israel, 1976 (In Hebrew).

[15] HANANI U., and TAPIERO C.S. "Geographical Partitioning Problems Dynamic Clusters Approach", W.P. n° 77-06, Hebrew University of Jerusalem, to appear in *City and Region* (in Hebrew).

[16] HANANI U., and TAPIERO C.S. "The Combined Location-Districting Problem : A Dynamic Cluster Analysis Approach" (Fortcoming).

[17] HESS S.W., "Experiences with Sales Distributing Model : Criteria and Implementation", *Management Sciences*, 18, Part II, (1971), P-41-P-54.

[18] HESS S.W., et al. "Non partisan Political Redistricting by Computer", *Operations Research*, 13, (1965), 998 - 1006.

[19] JOHNSEN, E., "*Studies in Multiobjectives Decisions Models*, Monograph n° 1, Economic Research Center in Lund, Sweden, 1968.

[20] KORNBLUTH, J.S.H. "A survey of Goal Programming", *Omega*, 1, 2 (April 1973), 193-205.
[21] KORNBLUTH, J.S.H. "Duality, Indifference and Sensitivity in Multiple Objective Linear Programming", *Operational Research Quarterly*, 25, 4, (Dec. 1974), 599-614.

[22] LECHEVALLIER, Y. "Classification automatique optimale sous contrainte d'ordre total", *Rapport de recherche*, n° 200, (nov. 1976), IRIA, Rocquencourt, France.

[23] MacCRIMMON, K.R. "An overview of Multiple Objective Decision Making" in, *Multiple Criteria Decision Making* J.L. Cochrane and M. Zeleny (eds.), University of S. Carolina Press, S. Carolina, 1973.

[24] MONARCHI, D.E., et al. "An Interative Multiple Objective Decision Making Aid Using Nonlinear Goal Programming", in, *Multiple Criteria Decision Making*, M. Zeleny (ed.), Springer-Verlag, N.Y., 1975, 235-253.

[25] POLAK, E. "On the Approximation of Solutions to Multiple Criteria Decision Making Problems", in, *Multiple Criteria Decision Making*, M. Zeleny (ed.), Springer-Verlag, N.Y., 1975, 271-282.

[26] RAPAPORT, A. "Interpersonal Comparison of Utilities", in, *Multiple Criteria Decision Making*, M. Zeleny (ed.), Springer-Verlag, N.Y., 1975, 271-282.

[27] ROY, B. "Why Multicriteria Decision Aid may not fit in with the Assessment of a Unique Criterion", in, *Multiple Criteria Decision Making*, M. Zeleny (ed.), Springer-Verlag, N.Y. 1975, 283-286.

[28] WILSON, A.G. "*Urban and Regional Models in Geography and Planning*", Wiley & Sons, 1974.

[29] ZELENY, M. "*Linear Multiobjective Programming*", Springer-Verlag, Berlin, 1974.

[30] ZELENY, M. "The Theory of the Displaced Ideal", in, *Multiple Criteria Decision Making*, M. Zeleny (ed.), Springer-Verlag N.Y., 1974, 153-206.