実行可能な領域

数理最適化とコンピュータサイエンスでは、実行可能領域、実行可能集合、または解空間とは、最適化問題の制約を満たすすべての可能な点（選択変数の値の集合）の集合であり、不等式、等式、および整数制約が含まれる可能性があります。^{[ 1 ]}これは、候補の集合が絞り込まれる前の、問題に対する候補解の初期集合です。

例えば、関数を最小化する問題を考えてみましょう。${\displaystyle x^{2}+y^{4}}$変数に関して${\displaystyle x}$そして${\displaystyle y,}$対象${\displaystyle 1\leq x\leq 10}$そして${\displaystyle 5\leq y\leq 12.\,}$ここで、実行可能集合とは、xの値が1 以上 10 以下であり、yの値が 5 以上 12 以下であるペア ( x , y ) の集合です。この問題の実行可能集合は、最適化される基準を示す目的関数とは別個のものであり、上記の例では次のようになります。${\displaystyle x^{2}+y^{4}.}$

多くの問題において、実行可能集合は、1つ以上の変数が非負でなければならないという制約を反映しています。純粋な整数計画問題では、実行可能集合は整数の集合（またはその部分集合）です。線形計画問題では、実行可能集合は凸多面体です。これは、境界が超平面によって形成され、角が頂点である多次元空間の領域です。

制約充足とは、実行可能領域内の点を見つけるプロセスである。

凸実行可能集合とは、任意の2つの実行可能点を結ぶ線分が、実行可能集合以外の点を通らず、他の実行可能点のみを通る集合のことです。凸実行可能集合は、線形計画問題を含む多くの種類の問題で発生し、特に重要です。なぜなら、最小化すべき目的関数が凸である場合、凸実行可能集合が存在すると一般的に解決が容易になり、局所最適解が全体最適解にもなるからです。

最適化問題の制約条件が互いに矛盾する場合、すべての制約条件を満たす点は存在せず、実行可能領域は空集合となります。この場合、問題には解がなく、実行不可能であると言われます。

実行可能集合は、有界または無界となる場合があります。たとえば、制約集合 { x ≥ 0, y ≥ 0} で定義される実行可能集合は無界です。なぜなら、一部の方向には、実行可能領域内にとどまることができる距離に制限がないからです。一方、制約集合 { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} で形成される実行可能集合は有界です。なぜなら、どの方向への移動も制約によって制限されるからです。

n個の変数を持つ線形計画問題において、実行可能集合が有界であるための必要条件ではあるが十分条件ではないのは、制約の数が少なくともn + 1 であることです (上記の例で示されているように)。

実行可能領域が非有界の場合、目的関数の具体的な内容によっては最適解が存在する場合と存在しない場合があります。たとえば、実行可能領域が制約集合 { x ≥ 0, y ≥ 0} で定義されている場合、 x + yを最大化する問題には最適解が存在しません。なぜなら、どの候補解もxまたはy を増やすことで改善できるからです。しかし、問題がx + yを最小化する ことであれば、最適解が存在します (具体的には ( x , y ) = (0, 0) です)。

最適化やその他の数学の分野、および探索アルゴリズム（コンピュータサイエンスのトピック ）では、候補解は、与えられた問題の実行可能領域内の可能な解の集合のメンバーです。 ^{[ 2 ]}候補解は、問題に対する可能性の高い、または妥当な解である必要はありません。単にすべての制約を満たす集合に含まれている、つまり、実行可能な解の集合に含まれているということです。さまざまな種類の最適化問題を解くためのアルゴリズムは、候補解の集合を実行可能な解のサブセットに絞り込むことが多く、そのサブセットの点が候補解として残り、他の実行可能な解はそれ以降候補から除外されます。

実行可能な点が除外される前の、すべての候補解の空間は、実行可能領域、実行可能集合、探索空間、または解空間と呼ばれます。^{[ 2 ]}これは、問題の制約を満たすすべての可能な解の集合です。制約充足とは、実行可能集合内の点を見つけるプロセスです。

線形計画法

線形計画問題を解くためのシンプレックス法では、実行可能多面体の頂点を初期候補解として選択し、最適性を検証します。最適解として棄却された場合は、隣接する頂点を次の候補解として検討します。このプロセスは、候補解が最適解となるまで繰り返されます。