| Full text | |
| Author(s): |
Cavalcante, Victor F.
;
de Souza, Cid C.
;
Chen, B
;
Paterson, M
;
Zhang, G
Total Authors: 5
|
| Document type: | Journal article |
| Source: | Lecture Notes in Computer Science; v. 4614, p. 2-pg., 2007-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |