Article ID: | iaor20023463 |
Country: | Netherlands |
Volume: | 7 |
Issue: | 6 |
Start Page Number: | 551 |
End Page Number: | 564 |
Publication Date: | Nov 2001 |
Journal: | Journal of Heuristics |
Authors: | Wilson John M., French Alan P., Robinson Andrew C. |
Keywords: | programming: branch and bound |
The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.