A Hybrid Genetic / Branch and Bound Algorithm for Integer Programming

An approach to combine a genetic algorithm with traditional linear programming based branch and bound for integer programming is described in this paper. Branch and bound provides a systematic search procedure for pure integer programming problems and a genetic approach offers the possibility of rapid movement towards a useful solution. Hence the two approaches look worthy of combination as a way to solve certain {0,1} integer programming problems. The approach has been tested out on satisfiability problems and computational results look promising in certain aspects of speed and solution quality.