Optimization hardness as transient chaos in an analog approach to constraint satisfaction
Mária Ercsey-RavaszZoltán ToroczkaiPublished in: CoRR (2012)
Keyphrases
- constraint satisfaction
- phase transition
- russian doll search
- constraint satisfaction problems
- constraint propagation
- relaxation labeling
- heuristic search
- constraint programming
- probabilistic reasoning
- arc consistency
- optimization problems
- product configuration
- optimization algorithm
- constraint relaxation
- np hard
- combinatorial optimization
- combinatorial problems
- constraint solving
- neural network
- optimization method
- np complete
- constraint optimization
- satisfiability problem
- sat solvers
- computational complexity
- multiple objectives
- soft constraints
- randomly generated
- linear programming
- constrained problems
- worst case
- backtracking algorithms
- lower bound