Integer Programming for the Maximum Cut Problem: A Refined Model and Implications for Branching
We present a refined integer programming model for the Maximum Cut problem along with new and extended structural results. Through the relationship between odd-cycle inequalities and parity constraints we uncover a fast separation routine, and a further analysis of the impact of partitioning decisions leads to a new branching rule. In our computational comparison of branching strategies, we demonstrate a significant impact of our model and techniques on state-of-the-art branch-and-cut algorithms and show that our branching rule improves over previous problem-specific ones.
- Published in:
SIAM Conference on Applied and Computational Discrete Algorithms - Type:
Inproceedings - Authors:
Charfreitag, Jonas; Mallach, Sven; Mutzel, Petra - Year:
2023
Citation information
Charfreitag, Jonas; Mallach, Sven; Mutzel, Petra: Integer Programming for the Maximum Cut Problem: A Refined Model and Implications for Branching, SIAM Conference on Applied and Computational Discrete Algorithms, 2023, https://epubs.siam.org/doi/10.1137/1.9781611977714.6, Charfreitag.etal.2023a,
@Inproceedings{Charfreitag.etal.2023a,
author={Charfreitag, Jonas; Mallach, Sven; Mutzel, Petra},
title={Integer Programming for the Maximum Cut Problem: A Refined Model and Implications for Branching},
booktitle={SIAM Conference on Applied and Computational Discrete Algorithms},
url={https://epubs.siam.org/doi/10.1137/1.9781611977714.6},
year={2023},
abstract={We present a refined integer programming model for the Maximum Cut problem along with new and extended structural results. Through the relationship between odd-cycle inequalities and parity constraints we uncover a fast separation routine, and a further analysis of the impact of partitioning decisions leads to a new branching rule. In our computational comparison of branching strategies, we...}}
