Abstract
| Original language | English |
|---|---|
| Journal | Networks |
| Volume | 58 |
| Issue number | 4 |
| Pages (from-to) | 301-310 |
| ISSN | 0028-3045 |
| DOIs | |
| Publication status | Published - Nov 2011 |
Keywords
- column generation
- integer programming
- cutting planes
- Dantzig-Wolfe decomposition
Cite this
}
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 journal › Journal article › Research › peer-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 -