Dr. Thorsten Bonato

Abstract
The max-cut problem is an NP-hard combinatorial optimization problem defined on undirected weighted graphs. It consists in finding a subset of the graph's nodes such that the aggregate weight of the edges between the subset and its complement is maximized. This book deals with a new separation approach to be used within a branch-and-cut algorithm for solving max-cut problems to optimality. The method is based on graph contraction and allows the fast separation of so-called odd-cycle inequalities. In addition, we describe techniques to add possibly missing edges to an already contracted graph. This allows solving max-cut problems on sparse graphs by means of methods that were originally intended for complete graphs and could not have been applied otherwise. We investigate the theoretical aspects of this combined approach and also explain its realization within a branch-and-cut framework. Finally, we evaluate the performance of our separation procedure on a variety of test instances.


Keywords
combinatorial optimization, max-cut problem, cut polytope, polyhedral combinatorics, branch-and-cut, separation, lifting, projection, graph contraction, artificial extension, odd-cycle inequality, target cuts, unconstrained quadratic 0-1 optimization,


Author

Thorsten Bonato studied mathematics with focus on scientific computing at the Ruprecht Karls University in Heidelberg, Germany, where he received his doctorate in mathematics in 2011. During his doctoral studies, he worked in several interdisciplinary projects and research cooperations, such as the project "FORSYS-ViroQuant" for the investigation of virus-host cell interactions. He specializes in discrete and combinatorial optimization.

COPYRIGHT: Die Werbetexte, Grafiken, Fotos usw. dürfen unter den folgenden Bedingungen kostenlos für private und kommerzielle Projekte verwendet werden. Eine schriftliche Genehmingung des Verlages ist nicht erforderlich.

ZITIEREN: Die Zitierbarkeit ist für alle unserer Bücher gegeben. Sowohl Texte als auch Abbildungen dürfen im Rahmen des wissenschaftlichen Zitierens frei verwendet werden. Auf Nachfrage senden wir die Originalabbildungen auch in Druckqualität zu. Schreiben Sie uns eine email an info@optimus-verlag.de