constraint satisfaction
constraint satisfaction
(application)The Simplex method is one well known technique for solvingnumerical constraints.
The search difficulty of constraint satisfaction problems canbe determined on average from knowledge of easily computedstructural properties of the problems. In fact, hardinstances of NP-complete problems are concentrated near anabrupt transition between under- and over-constrainedproblems. This transition is analogous to phase transitionsin physical systems and offers a way to estimate the likelydifficulty of a constraint problem before attempting to solveit with search.
Phase transitions in search (TadHogg, XEROX PARC).