The Node Capacitated Graph Partitioning Problem: A Computational Study.
Please always quote using this URN: urn:nbn:de:0297-zib-1469
- In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design.
Download full text files
Additional Services
| Author: | Carlos E. Ferreira, Alexander Martin, Cid C. de Souza, Robert Weismantel, Laurence Wolsey |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1994/06/13 |
| Series (Serial Number): | ZIB-Report (SC-94-17) |
| ZIB-Reportnumber: | SC-94-17 |
| Published in: | Appeared in: Mathematical Programming 81 (1998) 229-256 |
