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

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