The approximability of non-Boolean satisfiability problems and restricted integer programming.
Maria J. SernaLuca TrevisanFatos XhafaPublished in: Theor. Comput. Sci. (2005)
Keyphrases
- integer programming
- satisfiability problem
- conjunctive normal form
- np complete
- np hard
- temporal logic
- approximation algorithms
- davis putnam logemann loveland
- search algorithm
- linear programming
- sat problem
- phase transition
- ai planning
- column generation
- constraint programming
- cutting plane
- sat instances
- pspace complete
- lagrangian relaxation
- boolean functions
- solving hard
- integer program
- finite domain
- stochastic local search
- cutting plane algorithm
- max sat
- model checking
- set partitioning
- integer programming formulations
- mazurkiewicz traces
- special case