Using the unconstrained quadratic program to model and solve Max 2-SAT problems
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.
- Solving the weighted MAX-SAT problem using the dynamic convexized method
- Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
- Linear programs for constraint satisfaction problems
- Solving the maximum edge weight clique problem via unconstrained quadratic programming
- Exact Max-SAT solvers for over-constrained problems
- An effective modeling and solution approach for the generalized independent set problem
- A new approach for modeling and solving set packing problems
- The unconstrained binary quadratic programming problem: a survey
- Applications and computational advances for solving the QUBO model
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
- Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation
- Solving the maximum edge weight clique problem via unconstrained quadratic programming
This page was built for publication: Using the unconstrained quadratic program to model and solve Max 2-SAT problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2505314)
