Simultaneously exploiting two formulations: An exact benders decomposition approach

Richard Martin Lusby*, Mette Gamst, Stefan Røpke, Simon Spoorendonk

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
Article number105041
JournalComputers and Operations Research
Volume123
ISSN0305-0548
DOIs
Publication statusPublished - 2020

Keywords

  • Mixed Integer Programming
  • Benders Decomposition
  • Cutting Stock Problem
  • Split Delivery Vehicle Routing

Fingerprint

Dive into the research topics of 'Simultaneously exploiting two formulations: An exact benders decomposition approach'. Together they form a unique fingerprint.

Cite this