実行可能領域とは？わかりやすく解説

五つの線形制約が与えられた問題の例（青線で表しており、これは非負条件の制約も含まれている。）。整数制約が無い場合の実行可能領域は青い線で囲まれた領域となるが、整数制約が加わると赤い点が実行可能領域となる。

実行可能領域（じっこうかのうりょういき、許容領域、実行可能集合、解空間、英: feasible region, feasible set, solution space）とは、数理最適化および計算機科学において最適化問題に与えられた不等式、等式、整数といった制約条件を満たすすべての解の集合を指す^[1]。これは最適解の候補を探索する前の初期の集合を表す。

例として、関数 $x^{2}+y^{4}$

有界な実行可能集合（上）と非有界の実行可能集合（下）。下記の実行可能集合は右側にいくらでも存在する。

実行可能集合は有界・非有界のいずれかとなる。制約が {x ≥ 0, y ≥ 0} のときの実行可能集合は各変数の値がいくらでも大きく取り得るため、非有界となる。一方、制約が {x ≥ 0, y ≥ 0, x + 2y ≤ 4} の場合での実行可能集合は各制約によって変数の取り得る範囲が制限されるため、有界となる。

n変数における線形計画問題において実行可能集合が有界となる必要条件は制約の数が少なくとも n + 1 個以上存在しなければならない。

実行可能集合が非有界の場合、最適解が存在しない場合があり、これは目的関数に依存して決まる。例として、実行可能集合が {x ≥ 0, y ≥ 0} のときに関数 x + y を最大化する場合は x、y を任意に増大したとしても実行可能集合を満たすため、最適解が存在しないが、関数 x + y を最小化する場合は最適解（(x, y) = (0, 0) である。）が存在する。

候補解

候補解^{[注釈 1]}とは、最適化や探索アルゴリズム、（計算機科学などの）他の数学の分野において問題の実行可能領域内の要素を表す^[2]。候補解は最適解である必要がなく、与えられた制約をすべて満たす解自体を指し、すなわち、実行可能解の集合となる。最適化問題に対するいくつかの解法では実行可能解の部分集合である候補解を限定していくことで最適解を求めており、候補解を限定しつつ、それ以外の解は候補解から除外することを行っている。

実行可能な候補解が取り除かれる前の全体の空間は次の名称で呼ばれる:実行可能領域（feasible region）、実行可能集合（feasible set）、探索空間（search space）、解空間（solution space）^[2]。制約充足性（英語版）ではこれらの実行可能集合の中から解を一つ求めることを指す。

遺伝的アルゴリズム

遺伝的アルゴリズムでは、候補解は集団の中の個体に該当する^[3]。

微積分

微積分において最適解を求めるために一階微分判定法（英語版）により求める: このとき、一次の導関数がゼロとなる方程式を解くことで確かめられ、この方程式の解を候補解と呼ぶ。候補解の中には最適解とならないものも存在し、最大値を求めたいときに最小値が求まってしまう場合や、最大値・最小値でなく鞍点や変曲点が求まってしまう場合である。鞍点や変曲点では関数は局所的に関数の増減が停止されるため求まる場合がある。この場合二階微分判定法（英語版）により最適解かを判定することができる。さらに候補解が局所最適解であるが大域的最適解出ない場合が挙げられる。

単項式 $x^{n},$

線形計画問題において与えられた制約を満たし、これらの変数がとり得る領域を表した実行可能領域（feasible region）を表したものである。二変数の問題において実行可能領域が有界の場合は凸単純多角形として表される。実行可能点を逐次生成するアルゴリズムでは、候補解として各々最適解であるかを判定する。

線形計画問題に対する単体法では初期解として実行可能多面体の頂点を選択し、最適性の条件を満たすかを確認する。もし最適解でなければ、新たな解として隣接する頂点を新たに生成する。この手続きは現在の解が最適性の条件を満たすまで続けられる。