Name
Abstract | ||
|---|---|---|
In this paper, we study different strategies to stabilize and accelerate the column generation method, when it is applied specifically to the variable sized bin-packing problem, or to its cutting stock counterpart, the multiple length cutting stock problem. Many of the algorithms for these problems discussed in the literature rely on column generation, processes that are known to converge slowly due to primal degeneracy and the excessive oscillations of the dual variables. In the sequel, we introduce new dual-optimal inequalities, and explore the principle of model aggregation as an alternative way of controlling the progress of the dual variables. Two algorithms based on aggregation are proposed. The first one relies on a row aggregated LP, while the second one solves iteratively sequences of doubly aggregated models. Working with these approximations, in the various stages of an iterative solution process, has proven to be an effective way of achieving faster convergence. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ejor.2005.07.033 | European Journal of Operational Research |
Keywords | Field | DocType |
Integer programming,Column generation,Variable sized bin-packing,Multiple length cutting stock,Convergence | Convergence (routing),Column generation,Mathematical optimization,Iterative and incremental development,Algorithm,Degeneracy (mathematics),Integer programming,Cutting stock problem,Model aggregation,Bin packing problem,Mathematics | Journal |
Volume | Issue | ISSN |
183 | 3 | 0377-2217 |
Citations | PageRank | References |
27 | 1.42 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cláudio Alves | 1 | 184 | 16.29 |
| José M. Valério De Carvalho | 2 | 168 | 14.06 |