Using extra dual cuts to accelerate column generation

Using extra dual cuts to accelerate column generation

0.00 Avg rating0 Votes
Article ID: iaor2007241
Country: United States
Volume: 17
Issue: 2
Start Page Number: 175
End Page Number: 182
Publication Date: Mar 2005
Journal: INFORMS Journal On Computing
Authors:
Keywords: packing, duality
Abstract:

Column generation is often used to solve models with stronger linear-programming relaxations. From the dual standpoint, column-generation processes can be viewed as cutting plane algorithms. In this paper, we present conditions under which it is possible to restrict the dual space, but still preserve the strength of the primal model and recover an optimal primal solution. We derive a family of dual cuts that are valid for the space of dual optimal solutions of the one-dimensional cutting-stock problem. These cuts correspond to extra columns in the primal model. Inserting a polynomial number of cuts of this family in the problem formulation at initialization time restricts the dual space during the entire column-generation process. Computational experiments show that this idea helps, reducing substantially the number of columns generated, the number of degenerate iterations, and the computational time.

Reviews

Required fields are marked *. Your email address will not be published.