  


Improved compact formulations for graph partitioning in sparse graphs
Dang Phuong Nguyen(dangphuong.nguyencea.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 (01 Programming ) Citation: submitted to Discrete Optimization Download: [PDF] Entry Submitted: 06/22/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  