{"id":32799,"date":"2026-01-21T17:02:40","date_gmt":"2026-01-21T17:02:40","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/integer-programming-for-the-maximum-cut-problem-a-refined-model-and-implications-for-branching\/"},"modified":"2026-09-17T11:26:17","modified_gmt":"2026-09-17T11:26:17","slug":"integer-programming-for-the-maximum-cut-problem-a-refined-model-and-implications-for-branching","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/integer-programming-for-the-maximum-cut-problem-a-refined-model-and-implications-for-branching\/","title":{"rendered":"Integer Programming for the Maximum Cut Problem: A Refined Model and Implications for Branching"},"content":{"rendered":"<p>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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[32],"class_list":["post-32799","publication","type-publication","status-publish","hentry","publication-type-inproceedings"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32799","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/14"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32799\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32799"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32799"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}