| Texto completo | |
| Autor(es): |
Cavalcante, Victor F.
;
de Souza, Cid C.
;
Chen, B
;
Paterson, M
;
Zhang, G
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Lecture Notes in Computer Science; v. 4614, p. 2-pg., 2007-01-01. |
| Resumo | |
In this paper we propose an algorithm for the vertex separator problem (VSP) based on Lagrangian Relaxation and on cutting planes derived from valid inequalities presented in [3]. The procedure is used as a preprocessing for the branch-and-cut (B&C) algorithm implemented for VSP in [12], aiming to generate an initial pool of cutting planes and a strong primal bound for the latter. Computational experiments show that the exact method obtained in that way outperforms the pure B&C algorithm recently introduced by de Souza and Balas in [12]. Besides, we show that the Lagrangian phase is a very effective heuristic for the VSP, often producing optimal solutions extremely fast. (AU) | |
| Processo FAPESP: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa PRONEX - Temático |