Métodos duales y algoritmos híbridos para problemas de "set partitioning".

Título inglés	Dual methods and hybrid algorithms for Set Partitioning problems.
Título español	Métodos duales y algoritmos híbridos para problemas de "set partitioning".
Autor/es	Barceló Bugeda, Jaime ; Fernández Areizaga, Elena
Organización	Dep. Estad. Inv. Oper. Fac. Informàt. Univ. Politèc. Catalunya, Barcelona, España
Revista	0213-8204
Publicación	1990, 5 (1): 35-59, 15 Ref.
Tipo de documento	articulo
Idioma	Español
Resumen español	En este artículo estudiamos la utilización de métodos duales en el diseño de algoritmos híbridos para la resolución de problemas de "Set Partitioning" (SP). Las técnicas duales resultan de gran interés para resolver problemas con estructura combinatoria no sólo porque generan cotas inferiores sino porque, además, su utilización junto con heurísticas y procedimientos de generación de desigualdades en el diseño de algoritmos híbridos permite evaluar la calidad de las cotas superiores obtenidas. Los métodos duales estudiados son la relajación subrogada, la relajación lagrangiana y una variante del método BISA de refuerzo dual. Asimismo, presentamos los resultados obtenidos con estas técnicas en un algoritmo híbrido para (SP).
Resumen inglés	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.
Clasificación UNESCO	120707
Palabras clave español	Programación entera ; Método dual
Código Z-Math	Zbl 0692.90071
Acceso al artículo completo