分枝限定法
第一は分枝操作である。場合分けにより部分問題に分割する。つまり、与えられた集合 S {\displaystyle S} に対して、 S 1 ∪ S 2 ∪ ... = S {\displaystyle S_{1}\cup S_{2}\cup \ldots =S} となるような複数の集合 S 1 , S 2 , ... {\displaystyle S_{1},S_{2},\ldots } に分割(分枝)する手続きである。 S i {\displaystyle S_{i}} における f ( x ) {\displaystyle f(x)} の最小値を v i {\displaystyle v_{i}} としたとき、 S {\displaystyle S} における f ( x ) {\displaystyle f(x)} の最小値は 構文解析に失敗 (SVG(ブラウザのプラグインで MathML を有効にすることができます): サーバー「http://localhost:6011/ja.wikipedia.org/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): \min\{v_1, v_2, \ldots\} である。この手続きを再帰的に適用することは分枝法 (branching) と呼ばれ、各ノードが S {\displaystyle S} の部分集合となるような木(探索木)になる。なお S i ∩ S j ≠ ∅ {\displaystyle S_{i}\cap S_{j}\neq \emptyset } でも良い。
この手法の効率は、ノード分割手続きと上限および下限を推定する手続きに強く依存する。他の全ての条件が同じなら、オーバーラップしない部分集合に分割するのが最もよい。
理想的には、この手続きは探索木の全てのノードが刈りこまれるか解かれたときに停止する。その時点で刈りこまれていない部分は、上限と下限が関数の大域的最小値と等しくなっている。実際には、ある所定の時間が経過すると手続きを停止することが多く、その時点では刈りこまれていない部分の最大下限値と最小上限値が大域的最小値の区間を定義している。これとは別に時間制限ではなく、アルゴリズムを何らかの誤差基準で停止させる方法もある。例えば (最大 - 最小)/(最大 + 最小)がある特定値以下になった時点で停止させる。
この手法の効率は、分枝法と限定法に使われたアルゴリズムの有効性に強く依存する。間違った選択をすると分枝が繰り返され、全く刈り込みが行われず、あまりにも細かく分割されることになる。それは定義域を総当りするのと何ら変わりないことになり、多くの場合現実的でない。あらゆる問題でうまくいく限定法アルゴリズムは存在しないし、今後見つかるとも思えない。従って、分枝法と限定法のアルゴリズムは問題毎に設計する必要がある。