Benders decomposition: an integer-programming extension with further computational enhancements
We extend Benders decomposition in two ways. We begin by introducing a new integer Benders decomposition algorithm (IBDA) that solves pure integer programs (IPs). IBDA solves a mixed-integer relaxation of the IP by Benders decomposition and then conducts a type of local search to identify promising solutions to the original problem. IBDA's key contributions are the local-search technique and a novel use of solution-elimination constraints. We prove IBDA's correctness and demonstrate that the algorithm solves certain IPs faster than other available techniques. Slow Benders master-problem solution ...
(For more, see "View full record.")