Laurent and 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.
Gap inequalities for the max-cut problem: a cutting-plane algorithm
GALLI, LAURA;
2012-01-01
Abstract
Laurent and 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.