Mixed-integer programming techniques for the connected max-k-cut problem
| Autor: | Martin Schmidt, Imke Joormann, Hendrik Lüthen, Christopher Hojny |
|---|---|
| Přispěvatelé: | Discrete Mathematics |
| Rok vydání: | 2020 |
| Předmět: |
Connectivity
Mathematical optimization 021103 operations research Computer science Maximum cut 0211 other engineering and technologies Graph partition Mixed-integer programming 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Branch-and-cut 010201 computation theory & mathematics Theory of computation Max-cut Fraction (mathematics) Heuristics Focus (optics) Branch and cut Integer programming Software |
| Zdroj: | Mathematical Programming Computation, 13, 75-132. Springer |
| ISSN: | 1867-2957 1867-2949 |
| DOI: | 10.1007/s12532-020-00186-3 |
| Popis: | We consider an extended version of the classical Max-$$k$$ 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink