Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem
Armbruster M, Fügenschuh M, Helmberg C, Jetchev N, Martin A (2006)
Publication Language: English
Publication Type: Book chapter / Article in edited volumes
Publication year: 2006
Publisher: Springer, Berlin
Edited Volumes: Proceedings of 6th European Conference, EvoCOP 2006, Budapest, Hungary, April 10-12, 2006
Series: Lecture Notes in Computer Science
Book Volume: 3906
Pages Range: 1-12
Conference Proceedings Title: Proceedings of 6th European Conference, {EvoCOP} 2006, Budapest, Hungary, April 10-12, 2006
DOI: 10.1007/11730095_1
Abstract
We develop a primal heuristic based on a genetic algorithm for the minimum graph bisection problem and incorporate it in a branch-and-cut framework. The problem concerns partitioning the nodes of a weighted graph into two subsets such that the total weight of each set is within some lower and upper bounds. The objective is to minimize the total cost of the edges between both subsets of the partition. We formulate the problem as an integer program. In the genetic algorithm the LP-relaxation of the IP-formulation is exploited. We present several ways of using LP information and demonstrate the computational success.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Armbruster, M., Fügenschuh, M., Helmberg, C., Jetchev, N., & Martin, A. (2006). Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem. In Proceedings of 6th European Conference, EvoCOP 2006, Budapest, Hungary, April 10-12, 2006. (pp. 1-12). Springer, Berlin.
MLA:
Armbruster, Michael, et al. "Hybrid Genetic Algorithm Within Branch-and-Cut for the Minimum Graph Bisection Problem." Proceedings of 6th European Conference, EvoCOP 2006, Budapest, Hungary, April 10-12, 2006. Springer, Berlin, 2006. 1-12.
BibTeX: Download