Cutting planes (cuts) are very popular in the OR community, where they are
used to strengthen the Linear Programming (LP) relaxation of Mixed-Integer
Programs (MIPs) in the hope of improving the performance of an exact LPbased
solver. In particular, an intense research effort has been devoted to the
study of families of general cuts, whose validity does not require the presence
of a specific MIP structure—as opposed to problem-specific cuts such as, e.g.,
subtour elimination or comb inequalities for the traveling salesman problem.
Among general cuts, Gomory’s Mixed-Integer Cuts (GMICs) play a central
role both in theory and in practice. These cuts have been introduced by Ralph
Gomory about 50 years ago in his seminal paper [1]. Though elegant and computationally
cheap, they were soon abandoned because they were considered of
little practical use [2]. The situation changed radically more than 30 years later,
when Balas, Ceria, Cornu´ejols and Natraj [3] found how to take advantage of
exactly the same cuts but in an different framework. In our view, this is a good
example of the importance of a sound framework for MIP cuts.
Even today, MIP solvers are quite conservative in the use of general cuts, and
in particular of GMICs, because of known issues due to the iterative accumulation
of the cuts in the optimal LP basis. This leads to numerical instability
because of a typically exponential growth of the determinant of the LP basis.
Following our recent joint work with Balas and Zanette [4, 5], in this talk we
argue that the known issues with cutting plane methods are largely due to the
overall framework where the cuts are used, rather than to the cuts themselves.
This is because the two main cutting plane modules (the LP solver and the cut
generator) form a closed-loop system that is intrinsically prone to instability.
Hence a kind of “decoupling filter” needs to be introduced in the loop if one
wants to exploit the full power of a given family of cuts.
A main goal of the talk is to refocus part of the current research effort from
the definition of new cut families to the way the cuts are actually used. In fact,
cutting planes still miss an overall “meta-scheme” to control cut generation and
to escape local optima by means of diversification phases—very well in the spirit
of Tabu or Variable Neighborhood Search meta-schemes for primal heuristics.
The development of sound meta-schemes on top of a basic separation tool is
therefore an interesting new avenue for future research, with contributions expected
from all the three CP/AI/OR communities. The relax-and-cut framework
for GMICs recently proposed in the joint work with Salvagnin [6] can be viewed
as a first step in this direction.