The Power of Semidefinite Programming Relaxations for MAX-SAT.
Carla P. GomesWillem Jan van HoeveLucian LeahuPublished in: CPAIOR (2006)
Keyphrases
- semidefinite programming
- max sat
- linear programming
- semidefinite
- lower bound
- weighted max sat
- linear program
- primal dual
- interior point methods
- quadratically constrained quadratic
- np hard
- branch and bound algorithm
- sat solvers
- optimal solution
- integer programming
- objective function
- search algorithm
- satisfiability problem
- constraint satisfaction
- upper bound
- branch and bound
- column generation
- kernel matrix
- machine learning
- dynamic programming
- tabu search
- np complete
- combinatorial optimization
- maximum margin
- special case
- particle swarm optimization
- simulated annealing
- neural network