Using a hybrid genetic-algorithm/branch and bound approach to solve feasibility and optimization integer programming problems

Using a hybrid genetic-algorithm/branch and bound approach to solve feasibility and optimization integer programming problems

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.