Computational study of a column generation algorithm for bin packing and cutting stock problems
type: Item
instance of: scholarly article
title: Computational study of a column generation algorithm for bin packing and cutting stock problems
zbMATH Open document ID: 0949.90066
author: F. Vanderbeck
published in: Mathematical Programming. Series A. Series B
publication date: 2000-12-05T00:00:00Z
review text: Guided by the Cutting Stock Problem (CSP) this paper studies how features like cutting planes, rounding heuristics, early branching and variable fixing can be incorporated in a branch and price (column generation) algorithm. In particular it is shown that a lower bound provided by the LP relaxation of a column generation formulation of the CSP dominates combinatorial bounds. This leads to a new pseudopolynomial heuristic for the CSP. The author discusses in detail the branching scheme and other implementational details for branch and price algorithms. A computational study on bin packing and cutting stock problems reveals the effects of various algorithmic settings and shows the efficiency of the resulting algorithm for these problem classes.
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1419753
zbMATH Keywords: integer programming
zbMATH Keywords: column generation
zbMATH Keywords: bin packing
zbMATH Keywords: cutting stock
reviewed by: Rainer E. Burkard
MaRDI profile type: Publication
full work available at URL: s101070050105
OpenAlex ID: W1992439238
DOI: 10.1007/S101070050105
description: scientific article; zbMATH DE number 1419753