Approximating the Split Closure
Matteo Fischetti, Domenico Salvagnin
INFORMS Journal on Computing · 2013 · Volume 25 · Issue 4
Abstract
The split closure has been proved in practice to be a very tight approximation of the integer hull formulation of a generic mixed-integer linear program. However, exact separation procedures for optimizing over the split closure have unacceptable computing times in practice; hence, many different heuristic strategies have been proposed in the last few years. In this paper we present a new overall framework for approximating the split closure that merges different ideas from the previous approaches. Computational results prove the effectiveness of the proposed procedure compared to the state of the art, showing that a good approximation of the split closure bound can be obtained with very reasonable computing times.
Keywords
mixed-integer programming, Gomory cuts, split cuts
Enable JavaScript for citation tools and additional paper interactions.