Optimization Online


Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem

Christopher Hojny (hojny***at***mathematik.tu-darmstadt.de)
Imke Joormann (i.joormann***at***tu-braunschweig.de)
Hendrik Lüthen (luethen***at***mathematik.tu-darmstadt.de)
Martin Schmidt (martin.schmidt***at***uni-trier.de)

Abstract: We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved.

Keywords: Max-cut, Connectivity, Branch-and-cut, Mixed-integer programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 07/26/2018
Entry Accepted: 07/26/2018
Entry Last Modified: 06/06/2019

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