aussois_header.png

Corner Benders' Cuts
Matheus Ota  1  , Ricardo Fukasawa  1  , Aleksandr Kazachkov  2  
1 : Combinatorics and Optimization [Waterloo]
2 : University of Florida

Benders' decomposition is a very important tool in dealing with large scale optimization problems. It has been used in a wide variety of applications with great success. It relies on adding so called Benders' cuts to a master problem, to help capture the effect that the master problem decisions have in the subproblems. 

On the other hand, the study of corner polyhedra has been used in the context of cutting planes for mixed-integer programs also with great success. It allows the derivation of several results in cutting planes and can be seen as one possible way to derive Mixed-Integer Rounding and Gomory Mixed-Integer cuts. 

We propose a new way of generating Benders' cuts, using corner relaxations, which we call Corner Benders' cuts. We prove some basic theoretical properties of such cuts and show how they can be used for instance to recover Dantzig-Wolfe bounds. Our computational experiments show that, in our test problem, the approach can lead to significant improvements over the state-of-the-art branch-and-cut approach. 

 

 

 


Personnes connectées : 3 Vie privée | Accessibilité
Chargement...