Simultaneously Exploiting Two Formulations: An Exact Benders Decomposition Approach

Lusby, R. M. (Guest lecturer)

    Activity: Talks and presentationsConference presentations

    Description

    When modeling a given problem using 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. Computational results are reported for the Bin Packing Problem and the Split Delivery Vehicle Routing Problem.
    Period9 Jul 2018
    Event titleEURO 2018 conference on Operational Research
    Event typeConference
    LocationValencia, Spain