実行可能解（許容解）とは
Feasible Solution / 許容解
最適化問題や制約充足問題において、与えられた全ての制約条件を満たす解
概要
実行可能解とは、数理最適化や制約充足問題において、問題に課された全ての制約条件(等式制約・不等式制約など)を満たす変数の値の組を指す。実行可能解全体が作る集合を「実行可能領域(feasible region)」と呼ぶ。 最適化問題を解く際は、まず制約を満たす実行可能解を1つ以上見つけ(実行可能性の判定)、その上で目的関数を最小化(または最大化)する実行可能解、すなわち最適解を探索する、という2段階で捉えられることが多い。 制約を1つでも満たさない解は「実行不可能解(infeasible solution)」と呼ばれ、実行可能領域が空(実行可能解を1つも持たない)問題は「実行不可能(infeasible)」と呼ばれる。 組合せ最適化問題では、実行可能解を求めること自体がNP困難となることもあり、その場合は制約伝播やバックトラック探索などの手法で実行可能解を探索する。
比較
- NP問題 — 組合せ最適化問題では、実行可能解を1つ求めること自体がNP困難となる場合がある