.png){kind=icon}
Return
Accelerating column generation for variable sized bin-packing problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2005.07.033.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. The computational experiments were conducted on a broad range of instances, many of them published in the literature. They show a significant reduction of the number of column generation iterations and computing time. (c) 2006 Elsevier B.V. All rights reserved.
Keywords:
integer programming
column generation
variable sized bin-packing
multiple length cutting stock
convergence
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSaveShareSave
View more