Premium
Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems
Author(s) -
Cohn Amy,
Magazine Michael,
Polak George
Publication year - 2009
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20343
Subject(s) - cluster analysis , column generation , rank (graph theory) , computer science , set (abstract data type) , mathematical optimization , integer programming , class (philosophy) , cluster (spacecraft) , linear programming , algorithm , mathematics , machine learning , artificial intelligence , programming language , combinatorics
Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009