When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems.
Pierre GillibertJulius JonusasMichael KompatscherAntoine MottetMichael PinskerPublished in: CoRR (2020)
Keyphrases
- constraint satisfaction problems
- symmetry breaking
- constraint satisfaction
- global constraints
- graph coloring problems
- constraint programming
- random instances
- constraint propagation
- np complete
- symmetry breaking constraints
- combinatorial problems
- search space
- arc consistency
- constraint solving
- constraint networks
- non binary
- np hard
- graph coloring
- constraint problems
- solving constraint satisfaction problems
- disjunctive temporal
- computational problems
- finite domain
- product configuration
- sat problem
- forward checking
- constraint optimization
- backtracking search
- soft constraints
- finding optimal solutions
- phase transition
- heuristic search
- pseudo boolean optimization