Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems |
| |
Authors: | Alan P. French Andrew C. Robinson John M. Wilson |
| |
Affiliation: | (1) Loughborough University, Loughborough, LE11 3TU, England, UK;(2) Loughborough University, Loughborough, LE11 3TU, England, UK;(3) Loughborough University, Loughborough, LE11 3TU, England, UK |
| |
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. |
| |
Keywords: | branch and bound genetic algorithm maximum satisfiability |
本文献已被 SpringerLink 等数据库收录! |
|