Simultaneously exploiting two formulations: An exact benders decomposition approach

• Published in: Computers & operations research 2020-11, Vol.123, p.105041, Article 105041
• Main Authors: Lusby, Richard Martin, Gamst, Mette, Ropke, Stefan, Spoorendonk, Simon
• Format: Article
• Language: English
• Subjects: Benders decomposition; Cutting stock problem; Decomposition; Integer programming; Linear programming; Lower bounds; Mixed integer; Mixed integer programming; Operations research; Problem solving; Route planning; Split delivery vehicle routing; Vehicle routing
• ISSN: 0305-0548; 0305-0548
• DOI: 10.1016/j.cor.2020.105041

•We present a Benders decomposition approach to exploit two MIP formulations of the same problem.•We test the method on the Cutting Stock Problem and the Split Delivery Vehicle Routing Problem.•We provide a comparison with existing approaches for both problems.•We show that the approach provides promising results. When modelling a given problem using integer linear programming techniques several possibilities often exist, each resulting in a different mathematical formulation of the problem. Usually, advantages and disadvantages can be identified in any single formulation. In this paper we consider mixed integer linear programs and propose an approach based on Benders decomposition to exploit the advantages of two different formulations when solving a problem. We propose applying Benders decomposition to a combined formulation, comprised of two separate formulations, augmented with linking constraints to ensure consistency between the decision variables of the respective formulations. We demonstrate the applicability of the proposed methodology to situations in which one of the formulations models a relaxation of the problem and to cases where one formulation is the Dantzig-Wolfe reformulation of the other. The proposed methodology guarantees a lower bound that is as good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Cutting Stock Problem and the Split Delivery Vehicle Routing Problem. Compared to the best approaches from the literature, the proposed method shows promising performance and appears to be an attractive alternative.