Optimization Online


Improved compact formulations for graph partitioning in sparse graphs

Dang Phuong Nguyen(dang-phuong.nguyen***at***cea.fr)
Michel MINOUX(michel.minoux***at***lip6.fr)
Viet Hung NGUYEN(hung.nguyen***at***lip6.fr)
Thanh Hai NGUYEN(thanhhai.nguyen***at***cea.fr)
Renaud SIRDEY(renaud.sirdey***at***cea.fr)

Abstract: 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.

Keywords: graph partitioning; triangle constraints; metric constraints; max cut; sparse graph

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Citation: submitted to Discrete Optimization

Download: [PDF]

Entry Submitted: 06/22/2015
Entry Accepted: 06/22/2015
Entry Last Modified: 06/22/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society