Cutting Planes for Branch-and-Price Algorithms

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Standard

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

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

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Harvard

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

APA

CBE

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

MLA

Desaulniers, Guy, Jacques Desrosiers, and Simon Spoorendonk. "Cutting Planes for Branch-and-Price Algorithms". Networks. 2011, 58(4). 301-310. Available: 10.1002/net.20471

Vancouver

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

Author

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

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

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Bibtex

@article{9e5547c74c2b4cc19abe5e1f7f450923,
title = "Cutting Planes for Branch-and-Price Algorithms",
publisher = "John/Wiley & Sons, Inc. John/Wiley & Sons Ltd.",
author = "Guy Desaulniers and Jacques Desrosiers and Simon Spoorendonk",
year = "2011",
doi = "10.1002/net.20471",
volume = "58",
number = "4",
pages = "301--310",
journal = "Networks",
issn = "0028-3045",

}

RIS

TY - JOUR

T1 - Cutting Planes for Branch-and-Price Algorithms

A1 - Desaulniers,Guy

A1 - Desrosiers,Jacques

A1 - Spoorendonk,Simon

AU - Desaulniers,Guy

AU - Desrosiers,Jacques

AU - Spoorendonk,Simon

PB - John/Wiley & Sons, Inc. John/Wiley & Sons Ltd.

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

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

VL - 58

SP - 301

EP - 310

ER -