【しっかり学ぶ数理最適化】4.4.1~4.4.2

2025年後期輪読会 数理最適化 分枝限定法と切除平面法 (4.4.1~4.4.2) 京都大学 工学部 情報学科 数理工学コース 稲葉 陽孔 1

アジェンダ ■ 概要 ■ 分枝限定法 ■ 切除平面法 2

概要 文枝限定法と切除平面法とは NP困難な組合せ最適化問題の解法アルゴリズム 文枝限定法 - 直接は解きにくい問題を小さい問題に分割(分枝操作)と、その子問題から本問題の最適解を得ら れるかの判定(限定操作)を繰り返して解アルゴリズム 切除平面法 - 緩和問題の最適化から始め、実行可能解を残しつつ緩和問題の最適解を除去していく、制約条件 を組織的に追加し続けるアルゴリズム 3

分枝限定法 アルゴリズム(整数計画問題) ・・限定操作 ・・限定操作 ・・分枝操作 整数計画問題 線形計画緩和問題 整数計画問題の制限をxj>=0(j=1,,n)に変更したもの 子問題 整数計画問題において、ある１変数の値をとる範囲の制約を追加したもの 4

分枝限定法 アルゴリズム(整数計画問題・分枝操作) 分枝操作による子問題の追加イメージ 5

分枝限定法 アルゴリズム(整数計画問題・限定操作) 以下の特性をもとに、Step４により子問題Pが暫定解より優れいている解を持ちうるか判断し、 Step５で子問題Pをこれ以上深掘り(分枝操作)して実際の問題の解を探索する必要があるか判定 6

分枝限定法 アルゴリズム(整数計画問題・探索の効率化) 分枝限定法では確かに最適解を求められるが、探索する子問題の数を抑えないと計算量が多いので、 ・冗長な変数や制約条件の削除(前処理) ・考察に基づき最適性を失わずに一部の変数を固定する(変数固定) などによって探索数を抑えようと考えられている。 また、子問題の選び方にも様々な工夫が存在する。 7

分枝限定法 アルゴリズム(整数計画問題・子問題の選び方) 深さ優先探索 最後に生成された子問題を選ぶ手法 子問題への分枝の様子を探索木で表すと、 (手法の性質上)最も深い子問題を常に解いていくことになる また、L内の子問題の数を抑えられるので記憶領域の使用量が減る 最良優先探索 子問題の最適値を推定し、その値が最大(最小化問題なら最小)となる子問題を選び続ける手法 推定値として、(子問題の)線形緩和問題の最適値を用いる また、最終的に生成される子問題の数が最小になる(→アルゴリズムの計算量が抑えられる) しかし、初期は探索木の上層にある子問題が選ばれる傾向にあり、記憶領域の使用量が多くなりがち 8

切除平面法 アルゴリズム 切除平面 元々の制約式に重みをかけたり(式１)変形させたもの(式２)で、緩和問題の解を実行解から除去するも の また、制約式は整数計画問題の妥当式(全ての実行可能解が満たす式)でないといけない (式１) (式2：フバータル・ゴモリー不等式) ※式1・式2は整数計画問題の妥当式である。 9

切除平面法 切除平面の作り方 考える問題 (スラック変数を用いて)条件を等式に変形した整数計画問題 切除したい実行可能解 線形計画緩和問題の最適基底解(x_b,x_n) 辞書となる式： 整数計画問題 線形計画緩和問題 10

切除平面法 切除平面の作り方・最適基底解の更新 xiが非負より、緩和問題の 妥当不等式として成立 (整数計画問題では)xiは整数より左辺は整数で、 整数計画問題の妥当不等式になる →切除平面として成立する 式3 この切除平面にスラック変数を導入し、式 3にするとスラック変数 x_{n+1} の等式制約(式4)に変形できる。 しかし、x_{n+1}<0になるので双対単体法で xの基底解を求める ※式4はx_Nが0なので式5となり、右辺<0よりx_{n+1}<0 式4 式5 11