Métodos duales y algoritmos híbridos para problemas de "set partitioning"
- Barceló Bugeda, Jaume
- Fernández Aréizaga, Elena
ISSN: 0213-8204
Year of publication: 1990
Issue: 5
Pages: 35-59
Type: Article
More publications in: Trabajos de investigación operativa
Abstract
In this paper we study the behaviour of some Dual Methods in the design of hybrid algorithms for Set Partitioning (SP) problems. Dual techniques become very important to solve problems with a Combinatorial structure, not only because they provide lower bounds but also because employing them, along with heuristics and cutting plane procedures in the hybrid algorithms, allows evaluating the quality of upper bounds. The dual methods we have studied are surrogate and lagrangean relaxation and a variant of BISA's dual strengthening method. Computational results obtained with these techniques in a hybrid algorithm for SP problems are reported.