Cutting Planes for Branch-and-Price Algorithms

Guy Desaulniers, Jacques Desrosiers, Simon Spoorendonk

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the first case, cuts are added to the compact formulation, either at the master level or the subproblem level, and the decomposition process is reapplied. In the second case, we show that it is possible to model inequalities defined on the master problem variables by adding new variables and constraints to the subproblem formulation. The augmented subproblem indirectly indicates that there exists an augmented compact formulation that includes these new variables and constraints. Three examples on how to apply this framework are presented: the vehicle routing problem with time windows, the edge coloring problem, and the cutting stock problem. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 301–310 2011
    Original languageEnglish
    JournalNetworks
    Volume58
    Issue number4
    Pages (from-to)301-310
    ISSN0028-3045
    DOIs
    Publication statusPublished - Nov 2011

    Keywords

    • column generation
    • integer programming
    • cutting planes
    • Dantzig-Wolfe decomposition

    Cite this

    Desaulniers, G., Desrosiers, J., & Spoorendonk, S. (2011). Cutting Planes for Branch-and-Price Algorithms. Networks, 58(4), 301-310. https://doi.org/10.1002/net.20471
    Desaulniers, Guy ; Desrosiers, Jacques ; Spoorendonk, Simon. / Cutting Planes for Branch-and-Price Algorithms. In: Networks. 2011 ; Vol. 58, No. 4. pp. 301-310.
    @article{9e5547c74c2b4cc19abe5e1f7f450923,
    title = "Cutting Planes for Branch-and-Price Algorithms",
    abstract = "This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the first case, cuts are added to the compact formulation, either at the master level or the subproblem level, and the decomposition process is reapplied. In the second case, we show that it is possible to model inequalities defined on the master problem variables by adding new variables and constraints to the subproblem formulation. The augmented subproblem indirectly indicates that there exists an augmented compact formulation that includes these new variables and constraints. Three examples on how to apply this framework are presented: the vehicle routing problem with time windows, the edge coloring problem, and the cutting stock problem. {\circledC} 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 301–310 2011",
    keywords = "column generation, integer programming, cutting planes, Dantzig-Wolfe decomposition",
    author = "Guy Desaulniers and Jacques Desrosiers and Simon Spoorendonk",
    year = "2011",
    month = "11",
    doi = "10.1002/net.20471",
    language = "English",
    volume = "58",
    pages = "301--310",
    journal = "Networks",
    issn = "0028-3045",
    publisher = "JohnWiley & Sons, Inc.",
    number = "4",

    }

    Desaulniers, G, Desrosiers, J & Spoorendonk, S 2011, 'Cutting Planes for Branch-and-Price Algorithms', Networks, vol. 58, no. 4, pp. 301-310. https://doi.org/10.1002/net.20471

    Cutting Planes for Branch-and-Price Algorithms. / Desaulniers, Guy; Desrosiers, Jacques; Spoorendonk, Simon.

    In: Networks, Vol. 58, No. 4, 11.2011, p. 301-310.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Cutting Planes for Branch-and-Price Algorithms

    AU - Desaulniers, Guy

    AU - Desrosiers, Jacques

    AU - Spoorendonk, Simon

    PY - 2011/11

    Y1 - 2011/11

    N2 - This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the first case, cuts are added to the compact formulation, either at the master level or the subproblem level, and the decomposition process is reapplied. In the second case, we show that it is possible to model inequalities defined on the master problem variables by adding new variables and constraints to the subproblem formulation. The augmented subproblem indirectly indicates that there exists an augmented compact formulation that includes these new variables and constraints. Three examples on how to apply this framework are presented: the vehicle routing problem with time windows, the edge coloring problem, and the cutting stock problem. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 301–310 2011

    AB - This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the first case, cuts are added to the compact formulation, either at the master level or the subproblem level, and the decomposition process is reapplied. In the second case, we show that it is possible to model inequalities defined on the master problem variables by adding new variables and constraints to the subproblem formulation. The augmented subproblem indirectly indicates that there exists an augmented compact formulation that includes these new variables and constraints. Three examples on how to apply this framework are presented: the vehicle routing problem with time windows, the edge coloring problem, and the cutting stock problem. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 301–310 2011

    KW - column generation

    KW - integer programming

    KW - cutting planes

    KW - Dantzig-Wolfe decomposition

    U2 - 10.1002/net.20471

    DO - 10.1002/net.20471

    M3 - Journal article

    VL - 58

    SP - 301

    EP - 310

    JO - Networks

    JF - Networks

    SN - 0028-3045

    IS - 4

    ER -

    Desaulniers G, Desrosiers J, Spoorendonk S. Cutting Planes for Branch-and-Price Algorithms. Networks. 2011 Nov;58(4):301-310. https://doi.org/10.1002/net.20471