設計、割り当て、スケジューリング等、実社会には様々な問題が存在する。それらの問題に対し、設計結果や割り当て結果は「解」と呼ばれる。例えば、与えられた制約にしたがって配置設計を行えという問題に対しては、制約を満たした配置結果が解（実行可能解）に当たる。 例えば配置設計問題に対しては、様々な配置結果が考えられる。その中には良いものもあれば悪いものもある。もちろん、設計を行うにあたっては、良い配置結果を得たい。したがって、良い配置結果を得るためには、どうすれば良いのだろうかという研究が行われてきた。 残念ながら、実応用上の多くの配置設計問題では（例えばLSIのレイアウト設計問題など）、最良の配置結果を「組み立てるようなやり方で」構成する方法が存在せず、実際に全ての配置結果を構成してみて、その中で一番良いものを選ぶといったようなやり方でしか最良の配置結果を求めることができない。しかし、問題の規模が大きくなると、考えられる配置結果の数が爆発的に増大するため（組合せ爆発と呼ばれる）、規模の大きな問題に対しては、全ての配置結果を調べることは不可能となる。これは、最も良い配置結果を求めることは不可能であるということを意味している。