Using the unconstrained quadratic program to model and solve Max 2-SAT problems (Q2505314)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Using the unconstrained quadratic program to model and solve Max 2-SAT problems |
scientific article |
Statements
Using the unconstrained quadratic program to model and solve Max 2-SAT problems (English)
0 references
4 October 2006
0 references
Summary: 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.
0 references
satisfiability
0 references
metaheuristics
0 references
Tabu search
0 references
penalty functions
0 references
unconstrained quadratic program
0 references
Max 2-SAT problems
0 references
combinatorial optimisation
0 references