Optimization Online


Computational study of valid inequalities for the maximum $k$-cut problem

Vilmar Jefté Rodrigues de Sousa (vilmar.de.sousa***at***gerad.ca)
Miguel F. Anjos (miguel-f.anjos***at***polymtl.ca)
Sébastien Le Digabel (sebastien.le.digabel***at***gerad.ca)

Abstract: We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study of four classes of inequalities from the literature: clique, general clique, wheel and bicycle wheel. We considered 10 combinations of these classes and tested them on both dense and sparse instances for k in {3, 4, 5, 7}. Our computational results suggest that the bicycle wheel and wheel are the strongest inequalities for k=3, and that for k in {4, 5, 7} the wheel inequalities are the strongest by far. Furthermore, we observe an improvement in the performance for all choices of k when both bicycle wheel and wheel are used, at the cost of 72% more CPU time on average when compared with using only one of them.

Keywords: Maximum k-cut, graph partitioning, semidefinite programming, computational study.

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Annals of Operations Research, 265(1), p. 5-27, 2018. DOI: 10.1007/s10479-017-2448-9


Entry Submitted: 03/16/2016
Entry Accepted: 03/18/2016
Entry Last Modified: 04/20/2018

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