Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems

Daniel Porumbel () and François Clautiaux ()
Additional contact information
Daniel Porumbel: CEDRIC, CNAM, Conservatoire National des Arts et Métiers, Paris, 75003 France
François Clautiaux: Université de Bordeaux, 351, cours de la Libération, 33 405 TALENCE, France

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 170-184

Abstract: 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 different 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.

Keywords: column generation; cutting and packing; aggregation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0718 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:170-184

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().