Using the unconstrained quadratic program to model and solve Max 2-SAT problems

Using the unconstrained quadratic program to model and solve Max 2-SAT problems

0.00 Avg rating0 Votes
Article ID: iaor20061425
Country: United Kingdom
Volume: 1
Issue: 1/2
Start Page Number: 89
End Page Number: 100
Publication Date: Jan 2005
Journal: International Journal of Production Research
Authors: , , ,
Keywords: tabu search
Abstract:

Satisfiability (SAT) and Max-SAT problems have been the object of considerable research effort over the past few decades. They remain a very important research area today due to their computational challenge and application importance. In this paper, we investigate the use of penalty functions to recast SAT problems into the modelling framework offered by the unconstrained quadratic binary program. Computational experience is presented, illustrating how promising this approach is for Max 2-SAT problems.

Reviews

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