分枝限定法
第二の手続きは、 S {\displaystyle S} の1つの部分集合 S i {\displaystyle S_{i}} の f ( x ) {\displaystyle f(x)} の最小値の上限と下限を計算する手続きである。これを限定法 (bounding) と呼ぶ。
分枝限定法の鍵となるのは、あるノード(候補集合) A {\displaystyle A} の下限が別のノード B {\displaystyle B} の上限より大きければ、A は探索するまでもなく捨ててよいという考え方である。この工程を刈り込み (pruning) と呼び、一般に大域変数 m {\displaystyle m} にそれまでに調べた部分の最小の上限値を保持するような実装で実現する。下限が m {\displaystyle m} より大きいノードは捨てることができる。