Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations

This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more