Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach

Richard Martin Lusby, Mette Gamst, Simon Spoorendonk

    Research output: Book/ReportReport

    Abstract

    When modelling a given problem using linear programming techniques several possibilities often exist, and each results 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 to apply 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 good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. This paper also includes a discussion on the types of problems for which the method is of particular interest. Furthermore, it proves the correctness of the procedure and considers how to include interesting extensions such as cutting planes and advanced branching strategies. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Bin Packing problem. Compared to the standard branch-and-price approach from the literature, the method shows promising performance and appears to be an attractive alternative.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages23
    Publication statusPublished - 2016

    Bibliographical note

    Technical report

    Cite this

    Lusby, R. M., Gamst, M., & Spoorendonk, S. (2016). Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach. DTU Management Engineering.
    Lusby, Richard Martin ; Gamst, Mette ; Spoorendonk, Simon. / Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach. DTU Management Engineering, 2016. 23 p.
    @book{8ad78b3d22334d188c96071bd507b902,
    title = "Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach",
    abstract = "When modelling a given problem using linear programming techniques several possibilities often exist, and each results 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 to apply 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 good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. This paper also includes a discussion on the types of problems for which the method is of particular interest. Furthermore, it proves the correctness of the procedure and considers how to include interesting extensions such as cutting planes and advanced branching strategies. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Bin Packing problem. Compared to the standard branch-and-price approach from the literature, the method shows promising performance and appears to be an attractive alternative.",
    author = "Lusby, {Richard Martin} and Mette Gamst and Simon Spoorendonk",
    note = "Technical report",
    year = "2016",
    language = "English",
    publisher = "DTU Management Engineering",

    }

    Lusby, RM, Gamst, M & Spoorendonk, S 2016, Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach. DTU Management Engineering.

    Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach. / Lusby, Richard Martin ; Gamst, Mette; Spoorendonk, Simon.

    DTU Management Engineering, 2016. 23 p.

    Research output: Book/ReportReport

    TY - RPRT

    T1 - Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach

    AU - Lusby, Richard Martin

    AU - Gamst, Mette

    AU - Spoorendonk, Simon

    N1 - Technical report

    PY - 2016

    Y1 - 2016

    N2 - When modelling a given problem using linear programming techniques several possibilities often exist, and each results 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 to apply 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 good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. This paper also includes a discussion on the types of problems for which the method is of particular interest. Furthermore, it proves the correctness of the procedure and considers how to include interesting extensions such as cutting planes and advanced branching strategies. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Bin Packing problem. Compared to the standard branch-and-price approach from the literature, the method shows promising performance and appears to be an attractive alternative.

    AB - When modelling a given problem using linear programming techniques several possibilities often exist, and each results 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 to apply 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 good as the tighter of the two formulations, and we show how branching can be performed on the decision variables of either formulation. This paper also includes a discussion on the types of problems for which the method is of particular interest. Furthermore, it proves the correctness of the procedure and considers how to include interesting extensions such as cutting planes and advanced branching strategies. Finally, we test and compare the performance of the proposed approach on publicly available instances of the Bin Packing problem. Compared to the standard branch-and-price approach from the literature, the method shows promising performance and appears to be an attractive alternative.

    M3 - Report

    BT - Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach

    PB - DTU Management Engineering

    ER -

    Lusby RM, Gamst M, Spoorendonk S. Simultaneously Exploiting Two Formulations: an Exact Benders Decomposition Approach. DTU Management Engineering, 2016. 23 p.