Solving capacitated clustering problems (Q799059): Difference between revisions
From MaRDI portal
Latest revision as of 13:02, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving capacitated clustering problems |
scientific article |
Statements
Solving capacitated clustering problems (English)
0 references
1984
0 references
The authors consider the following special cluster problem with side conditions: n given entities have to be clustered into p mutually exclusive and exhaustive groups of restricted (upper) size such that the sum of \(L_ s\)-distances between each entity and a designated group median (some entity, too) is minimized. Well-known heuristics and the description of the corresponding algorithm in pidgin ALGOL are given. A second well-known method using Lagrangian relaxation and a subgradient algorithm is given. The two algorithms are combined for a third approach. Computational results indicate that the three methods are comparable with respect to computing time and quality of solution for larger values of n and p \((n=100\), \(p=20)\).
0 references
capacitated clustering problems
0 references
side conditions
0 references
heuristics
0 references
pidgin ALGOL
0 references
Lagrangian relaxation
0 references
subgradient algorithm
0 references