|
 
|
[PC16] Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems
Revue Internationale avec comité de lecture : Journal INFORMS Journal of Computing, vol. 29(1), pp. 170-184, 2016, (doi:dx.doi.org/10.1287/ijoc.2016.0718)
motcle:
Résumé:
We propose an aggregation method to reduce the size of column generation (CG) models for covering
problems in which the feasible subsets depend on a resource constraint. The aggregation relies on a correlation
between the resource consumption of the elements and the corresponding optimal dual values. The resulting
aggregated dual model is a restriction of the original one, and it can be rapidly optimized to obtain a feasible dual solution. A primal bound can also be obtained by restricting the set of columns to those saturated by
the dual feasible solution obtained by aggregation. The convergence is realized by iterative disaggregation
until the gap is closed by the bounds. Computational results show the usefulness of our method for di erent
cutting-stock problems. An important advantage is the fact that it can produce high-quality dual bounds
much faster than the traditional lagrangian bound used in stabilized column generation.
BibTeX
| @article { | |||
| PC16, | |||
| title | = | "{Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems}", | |
| author | = | "D. Porumbel and F. Clautiaux", | |
| journal | = | "INFORMS Journal of Computing", | |
| year | = | 2016, | |
| volume | = | 29, | |
| number | = | 1, | |
| pages | = | "170-184", | |
| doi | = | "dx.doi.org/10.1287/ijoc.2016.0718", | |
| } | |||
