Given a graph $G=(V,E)$ where $|V|=n$ and $|E|=m$. Graph partitioning problems on $G$ are to find a partition of the vertices in $V$ into clusters satisfying several additional constraints in order to minimize or maximize the number (or the weight) of the edges whose endnodes do not belong to the same cluster. These problems are usually modeled by a compact integer formulation using $O(n^3)$ triangle inequalities, whatever the value of $m$ is. Thus the sparsity of the graph is not taken into account in the formulation. In this paper, we prove that when the additional constraints satisfying some monotonicity property, one can reduce the number of triangle inequalities to $O(nm)$ without deteriorate the integer formulation and its linear programming relaxation. We then present numerical experiments on two graph partitioning problems with respectively additional knapsack and capacity constraints to show the benefit of using the reduced formulation comparing with the original formulations.
Citation
submitted to Discrete Optimization
Article
View Improved compact formulations for graph partitioning in sparse graphs