Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe heuristic separation algorithms for gap inequalities and their special cases, and show that an LP-based cutting-plane algorithm based on these separation heuristics can yield very good upper bounds in practice. © 2012 Springer-Verlag.
Galli, L., Kaparis, K., Letchford, A.N. (2012). Gap inequalities for the max-cut problem: A cutting-plane algorithm. Springer [10.1007/978-3-642-32147-4_17].
Gap inequalities for the max-cut problem: A cutting-plane algorithm
Galli L.;
2012
Abstract
Laurent & Poljak introduced a class of valid inequalities for the max-cut problem, called gap inequalities, which include many other known inequalities as special cases. The gap inequalities have received little attention and are poorly understood. This paper presents the first ever computational results. In particular, we describe heuristic separation algorithms for gap inequalities and their special cases, and show that an LP-based cutting-plane algorithm based on these separation heuristics can yield very good upper bounds in practice. © 2012 Springer-Verlag.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
