Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/53689
Type: Artigo de periódico
Title: A Relax-and-Cut algorithm for the set partitioning problem
Author: Cavalcante, VF
de Souza, CC
Lucena, A
Abstract: Relax-and-Cut algorithms offer an alternative to strengthen Lagrangian relaxation bounds. The main idea behind these algorithms is to dynamically select and dualize inequalities (cuts) within a Lagrangian relaxation framework. This paper proposes a Relax-and-Cut algorithm for the Set Partitioning Problem. Computational tests are reported for benchmark instances from the literature. For Set Partitioning instances with integrality gaps, a variant of the classical Lagrangian relaxation is often used in the literature. It introduces a knapsack constraint to the standard formulation of the problem. Our results indicate that the proposed Relax-and-Cut algorithm outperforms the latter approach in terms of lower bound quality. Furthermore, it turns out to be very competitive in terms of CPU time. Decisive in achieving that performance was the implementation of dominance rules to manage inequalities in the cut pool. The Relax-and-Cut framework proposed here could also be used as a preprocessing tool for Linear Integer Programming solvers. Computational experiments demonstrated that the combined use of our framework and XPRESS improved the performance of that Linear Integer Programming solver for the test sets used in this study. (c) 2006 Elsevier Ltd. All rights reserved.
Subject: Lagrangian relaxation
cutting planes
set partitioning
Relax-and-Cut algorithms
Country: Inglaterra
Editor: Pergamon-elsevier Science Ltd
Rights: fechado
Identifier DOI: 10.1016/j.cor.2006.10.009
Date Issue: 2008
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000251294600014.pdf242.64 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.