A novel Pareto-optimal cut selection strategy for Benders Decomposition

Decomposition approaches can be used to generate practically efficient solution algorithms for a wide class of optimization problems.
For instance, scenario-expanded two-stage stochastic optimization problems can be solved efficiently in practice using Benders Decomposition.
The performance of the approach can be influenced by the choice of the cuts that are added during the course of the algorithm.

The so-called Magnanti-Wong method aims for Pareto-optimal cuts.
Cuts based on minimal infeasible subsystems of a modified version of the sub problem have proven to provide strong cuts.
Most recently, methods using facets of the sub problem's value function's epigraph have been developed.

We contribute to the field of cut selection strategies for Benders Decomposition by developing an innovative notion of Pareto-optimality, which implies an efficient cut selection strategy.
The strategy aims for cuts that exclude a large set of points from being optimal.
We further develop the algorithmic framework to exploit the potential of our cut selection strategy optimally.
We benchmark our cut selection strategy against several other cut selection strategies on various instances.
Some instances are taken from the MIPLib, some others are network design problems, and others are randomly generated mixed-integer linear programs.
The computational results show that the developed method is, measured in CPU seconds needed to solve a problem to optimality, at least competitive for or better than the benchmark approaches for all three instance classes, especially, when it is combined as hybrid selection strategy with the minimal infeasible subsystem cut selection.
In addition, the method clearly outperforms the other cut selection strategies measured in the number of cuts needed to solve a problem to optimality.
Hence, the method is especially effective in situations with scarce memory or with a sub problem that is difficult to solve.



View A novel Pareto-optimal cut selection strategy for Benders Decomposition