THE NODE CAPACITATED GRAPH PARTITIONING PROBLEM - A COMPUTATIONAL STUDY

In this paper we consider the problem of k-partitioning the nodes of a graph with capacity restrictions on the sum of the node wrights in ea ch 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 heu ristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heu ristics, have been implemented in a branch-and-cut routine using a for mulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of probl ems: equipartitioning problems arising in finite element methods and p artitioning problems associated with electronic circuit layout and com piler design. (C) 1998 The Mathematical Programming Society, Inc. Publ ished by Elsevier Science B.V.