Embedding Cuts in a Branch-and-Cut Framework: a Computational Study with {0, 1/2}-Cuts

Embedding cuts into a branch-and-cut framework is a delicate task, the main so when the implemented separation procedures are very successful and do produce a large set of violated cuts. In this case, it is of crucial importance to balance between the benefits deriving from a tighter (but larger) LP relaxation, and the overhead introduced for its solution. In this paper we describe a separation heuristic for 0-1/2 cuts, special cases of Chvatal-Gomory cuts which play an important role in combinatorial problems formulated as Integer Linear Programming (ILP) problems. Our separation procedure is embedded within CPLEX, a widely-used commercial MIP solver. Computational results on a large testbed of ILP instances including satisfiability, max-satisfiability, and linear ordering problems, are reported. On these problems, our first attempt of incorporating 0-1/2 cuts within the CPLEX framework produced a code which was not significantly faster than the standard version, due to the excessive number of zum cuts generated - though these cuts appear to be of better quality with respect to those found by other general-purpose methods, and sometimes turn out to be facet defining for the underlying integer polytope. However, a more sophisticated cut-selection strategy produced a considerable speedup on our testbed. This is particularly interesting in that our separation procedure was used as black-box - all the improvements came from a more clever way to exploit the violated cuts. In other words, our cut selection policy does not need a tight interaction with the separation procedure. Therefore, we expect that a similar approach can be useful to deal with other families of cuts, in particular those for which finding a violated member is easy, but finding a violated member with specific properties (maximum violation, maximum depth, etc.) can be difficult.