Solving capacitated clustering problems (Q799059)

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)\).