June 26 - 30, 2004
Saturday to Wednesday
Seattle, Washington, USA

 

 

Session:

LBP - Late Breaking Papers

Title:

Genetic Programming for Guiding Branch and Bound Search

   

Authors:

Konstantinos Kostikas
Charalambos Fragakis

   

Abstract:

We propose how Genetic Programming (GP) can be used for developing, in real time, problem-specific heuristics for Branch and Bound (B&B) search. A GP run, embedded into the B&B process, exploits the characteristics of the particular problem being solved, evolving a problem-specific heuristic expression. The evolved heuristic replaces the default one for the rest of the B&B search. The application of our method to node selection for B&B based Mixed Integer Programming is illustrated by incorporating the GP node selection heuristic generator into a B&B MIP solver. The hybrid system compares well with the unmodified solver utilizing DFS, BFS, or even the advanced Best Projection heuristic when confronted with hard MIP problems from the MIPLIB3 benchmarking suite.

Home

Program

Search

Author Index

Sponsors

Committee

Contact Us

Help