Hypergraph Partitioning for Exploiting Localities in Nonlinear Constrained Optimization

In this paper, we present a new hypergraph partitioning algorithm that jointly optimizes the number of hyperedge cuts and the number of shared vertices in nonlinear constrained optimization problems. By exploiting the localities of constraints with respect to their variables, we propose to partition the constraints into subproblems. We use a relaxed global search to solve the subproblems and resolve those violated global constraints across the subproblems by updating the corresponding penalties. As resolving violated global constraints is computationally expensive, we propose to reduce the number of global constraints by increasing the number of shared variables. This trade-off is advantageous because the number of global constraints in many benchmarks can be significantly reduced by having a small number of variables shared across the subproblems. Partitioning in this context can be achieved by partitioning the corresponding hypergraph. We improve hMETIS to jointly optimize the number of hyperedge cuts and the number of shared vertices. Our experimental results demonstrate improved solution quality with similar computational overhead on some VLSI cell placement benchmarks.