Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems |
| |
| Authors: | Amy Cohn Michael Magazine George Polak |
| |
| Institution: | 1. Department of Industrial and Operations Engineering, College of Engineering, University of Michigan, Ann Arbor, Michigan 48109‐2117;2. Quantitative Analysis and Operations Management, College of Business, University of Cincinnati, Cincinnati, Ohio 45221;3. Department of Information Systems and Operations Management, Raj Soin College of Business, Wright State University, Dayton, Ohio 45435 |
| |
| Abstract: | 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 |
| |
| Keywords: | set partitioning branch‐and‐price delayed column generation branch‐and‐bound |
|
|
