実行可能領域

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

3変数における線形計画問題の有界な実行可能領域は凸多面体となる。

実行可能領域（じっこうかのうりょういき、許容領域、実行可能集合、解空間、テンプレート:Lang-en-short）とは、数理最適化および計算機科学において最適化問題に与えられた不等式、等式、整数といった制約条件を満たすすべての解の集合を指す。これは最適解の候補を探索する前の初期の集合を表す。

例として、関数 $x^2+y^4$ の最小化問題について考える。ただし、各変数 $x$、$y$ は制約条件として、$1\le x\le 10$、$5\le y\le 12.$ が課せられているとする。このときの実行可能集合は $x$ が1以上10以下、$y$ は5以上12以下の値からなる組 (x, y) の集合である。問題の実行可能集合と目的関数は異なっており、上記の例では目的関数は $x^2+y^4$ を指す。

多くの問題において一つあるいは複数の変数が非負の値をとるという制約が与えられる。すべての変数に整数条件が与えられた整数計画問題における実行可能集合は整数（その部分集合）からなる。線形計画問題における実行可能領域は多次元空間において超平面と頂点を持つ凸多面体となる。

テンプレート:仮リンクについては実行可能領域内の点を求めることを指す。

凸実行可能集合

凸実行可能集合とは実行可能集合の任意の2点を結ぶ線分内における点もまた必ず実行可能集合の要素となるような集合である。凸実行可能集合は線形計画問題といった多くの問題で用いられており、もし最適化問題の目的関数が凸関数でこれを最小化する際に実行可能集合が凸集合となる場合は局所最適解がかならず大域的最適解となるため、問題を解くのが容易であるとされる。

実行可能集合が空の場合

最適化問題の制約を満たすような点が存在しない場合、実行可能領域は空となる。このような場合を実行不可能（実行不能）と呼ぶ。

有界・非有界の実行可能集合

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

実行可能集合は有界・非有界のいずれかとなる。制約が {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) である。）が存在する。

候補解

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

実行可能な候補解が取り除かれる前の全体の空間は次の名称で呼ばれる:実行可能領域（feasible region）、実行可能集合（feasible set）、探索空間（search space）、解空間（solution space）。テンプレート:仮リンクではこれらの実行可能集合の中から解を一つ求めることを指す。

遺伝的アルゴリズム

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

微積分

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

単項式 $x^n,$ のテンプレート:仮リンクを導出する際にテンプレート:仮リンクを用いると、候補解 $\frac{1}{n+1}{x}^{n+1}+C.$ が得られる。これは $n=-1.$ を除いて正確な解となる。

線形計画法

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

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