【しっかり学ぶ数理最適化】4.4.3~4.5.2

しっかり学ぶ数理最適化 4.4.3-4.5.2 工学部B3 野村隆晃 0

アジェンダ ◼ 整数計画ソルバーの利用 ◼ 近似解法について 1

アジェンダ ◼ 整数計画ソルバーの利用 ◼ Proximal Policy Optimization 2

問題の定式化の手法 解きたい整数計画問題のsolverでの表現方法が複数あり、一長一短 LP (Liner Programing方式) maximize obj: 2 x1 + 3 x2 subject to c1: 2 x1 + x2 <= 10 c2: 3 x1 + 6 x3 <= 40 bounds x1 >= 0 x2 >= 0 general x1 x2 end MPS (Mathematical Programing System) NAME sample ROWS N obj L c1 L c2 COLUMNS INTSTART 'MARKER' 'INTORG' x1 obj -2 c1 2 x1 c2 3 x2 obj -3 c1 1 x2 c2 6 INTEND 'MARKER' 'INTEND' RHS RHS c1 10 c2 40 BOUNDS PL Bound x1 PL Bound x2 ENDATA 3

アジェンダ ◼ 整数計画ソルバーの利用 ◼ 近似解法 4

近似解法の性能評価 ある最小化問題Qに対するインスタンスI ∈ Qに対してのアルゴリズムAの性能評価 として、近似比率rを導入 (最適値との比率を定数倍で抑える) 今から紹介するビンパッキング問題に対する近似解法NF法とFF法は2-近似解法 5

Next Fit algorithm 各ワゴンに貪欲に詰めて、ワゴンが埋まったら次のワゴンへ詰める方法 1. 𝑖 = 0, 𝑗 = 0として𝑊𝑖 = 0 𝑖 = 0,1, ⋯ , 𝑛 として初期化 2. 𝑊𝑖 + 𝑤𝑗 < 𝐶ならば𝑊𝑖 = 𝑊𝑖 + 𝑤𝑗 , 𝑗 = 𝑗 + 1、収まらないなら𝑖 = 𝑖 + 1 3. j > nになるまで継続 𝑊𝑖 + 𝑊𝑖+1 > 𝐶より、𝑖 = 1,2, … , 𝐴 𝐼 − 1に対して、 𝑊1 + 𝑊2 + 𝑊2 + 𝑊3 + ⋯ + 𝑊𝐴 𝐼 −1 + 𝑊𝐴 𝐼 > 𝐶 𝐴 𝐼 − 1 左辺は2 σ𝑛𝑗=1(𝑤𝑗 ) − 𝑊1 − 𝑊𝐴 𝐼 なので 𝑛 𝐶 ⋅ 𝐴 𝐼 − 1 + 𝑊1 + 𝑊𝐴 𝐼 < ෍ 𝑤𝑗 ≤ 𝐶 ⋅ 𝑂𝑃𝑇 𝐼 2 𝑗=1 6

First Fit algorithm NF法同様に貪欲法だが、無駄を減らした手法 1. 𝑗 = 1として𝑊𝑖 = 0 𝑖 = 0,1, ⋯ , 𝑛 として初期化 2. 𝑾𝒊 + 𝒘𝒋 < 𝑪を満たす最小の𝒊に対して𝑊𝑖 = 𝑊𝑖 + 𝑤𝑗 , 𝑗 = 𝑗 + 1を行う 3. j > nになるまで継続 𝐶 arg𝑚𝑖𝑛 𝑊𝑖 の箱を除いて、すべての箱において𝑊𝑖 ≤ 2 (容量を半分以上使っていない箱は一つのみ) 𝐴 𝐼 𝑛 𝑖=1 𝑗=1 𝐶 𝐴 𝐼 −1 < ෍ 𝑊𝑖 − min 𝑊𝑖 < ෍ 𝑤𝑗 ≤ 𝐶 ⋅ 𝑂𝑃𝑇 𝐼 𝑖=1,…,𝐴 𝐼 2 7

First Fit Decreasing 法 3 重さを降順に並べてからFF法を適用すれば2 近似法になる. 2 FFDでの最適値を𝐴 𝐼 として𝑘 = A(I) とする。 3 𝑊k > CΤ2の場合は、FFDの性質より𝑊𝑗 > CΤ2 (j = 1,2, ⋯ , k − 1)であるため、OPT(I) > 2Τ3A(I) 𝑊k < CΤ2の場合は、 𝑊𝑗 > CΤ2 (j = k, k + 1, ⋯ , A(I))であり、重さの降順で荷物を入れてるため、 j = k, k + 1, ⋯ , A(I)では、すべてのコンテナに2個以上の荷物 j = k, k + 1, ⋯ , A(I)の荷物をj = 1,2, ⋯ , k − 1に移動すれば n C ⋅ OPT(I) > ෍ j=1 𝑤𝑗 > C(k − 1) よりOPT(I) < 3Τ2 A(I) 8