【しっかり学ぶ数理最適化】4.1~4.1.2(続き)

2025年度後期輪読会#8（2025/12/04） しっかり学ぶ数理最適化 4.1~4.1.2 整数計画と組み合わせ最適化 京大理学部 B2 ALAWIK Abdourrahman 0

アジェンダ ◼ 整数計画問題の定式化 ◼ 整数計画の応用例 ◼ 論理的な制約条件 1

アジェンダ ◼ 整数計画問題の定式化 ◼ 整数計画の応用例 ◼ 論理的な制約条件 2

4.1 整数計画問題の定式化 整数（線形）計画問題（Integer Programming; IP）の標準形： 𝑛 最大化 条件 ෍ 𝑐𝑗 𝑥𝑗 𝑗=1 σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , 𝑥𝑗 ∈ ℤ+ 𝑖 = 1, … , 𝑚 𝑗 = 1, … , 𝑛 つまり、線形計画問題において全ての変数が整数変数であるという制約を付け加えたもの また、一部の変数を実変数でもう一部が整数変数を整数変数の時、混合整数計画問題という 3

組み合わせ最適化問題 組み合わせ最適化問題：解の集合は組み合わせ的な構造を持つ 例：集合、順序、割当、グラフ、論理値、整数… 整数を用いて制約状態や切り替えるスイッチも表せるので、全ての組み合わせ最適化問題は整数 計画問題に定式化できる： 特にに yes/noの決定や離散的な状態の切り替えを２値変数（𝑥𝑖 ∈ {0,1}）で表すことが多い 逆に、整数計画問題は線形計画問題よりはるかに難しいので、離散的な値を取る変数を決定した い時は実数値で最適解を求めて、それを丸めたものを整数値の解だとみなした方が良いことが多 例：自動車や機器部品の生産数を決定する問題 4

アジェンダ ◼ 整数計画問題の定式化 ◼ 整数計画の応用例 ◼ 論理的な制約条件 5

4.1.1 整数計画問題の応用例 整数計画問題の応用例を５つ紹介する： 1. 雑誌購読計画問題 2. 文書要約問題 3. 商品推薦問題 4. コミュニティ検出問題 5. 線形順序付け問題 6

雑誌購読計画問題 限られた予算の下で、需要に応えた購読計画を決定したい。 予算を 𝐵、 雑誌の集合を 𝑁 = {1, … , 𝑛}、雑誌 𝑗 の購読額を𝑓𝑗 、需要率を 𝑑𝑗 （例えば前年度の閲覧 数） ２値変数 𝑥𝑗 ∈ {0,1}：雑誌 𝑗 を購読する場合 1、しない場合 0 最大化 ෍ 𝑑𝑗 𝑥𝑗 𝑗∈𝑁 条件 ෍ f𝑗 𝑥𝑗 ≤ 𝐵 𝑗∈𝑁 𝑥𝑗 ∈ 0,1 , 𝑗∈𝑁 これはナップサック問題と呼ばれる NP困難だが、銅的計画法や分岐限定法 7

雑誌購読計画問題 続 しかし、このままだと計画が一部の分野に偏ってしまう可能性が高い → 分野ごとの従属率の最小値を最大化する 分野の集合を 𝑀 = {1, … , 𝑚}、分野 𝑖 が含む雑誌の集合を 𝑁𝑖 ⊂ 𝑁、その需要を 𝐷𝑖 = σ𝑗∈𝑁𝑖 𝑑𝑗 σ𝑗∈𝑁 𝑑𝑗 𝑥𝑗 分野ごとの充足率（ 𝑖 𝐷𝑖 ）の最小値 𝑧 を最大化したい 最大化 𝑧 条件 ෍ f𝑗 𝑥𝑗 ≤ 𝐵 𝑗∈𝑁 ෍ 𝑑𝑗 𝑥𝑗 ≥ 𝐷𝑖 𝑧 𝑗∈𝑁 （混合計画） 𝑥𝑗 ∈ 0,1 , 0≤𝑧≤1 𝑗∈𝑁 8

雑誌購読計画問題 続々 とある大学の付属図書館で計算した例 9

文書要約問題 １つもしくは複数の文書（同一トピック）が与えられており、大事な文をいくつか取り出すこと で要約したい 10

文書要約問題 続々 まずは似た内容の分を含まない単一文書の要約を考える m個の概念とn個の文があって、要約長 L 内で要約を生成したい 概念 i の重要度を 𝑤𝑖 (> 0)、文 j の長さを 𝑙𝑗 、 文 j が概念 i を含む時は 𝑎𝑖𝑗 = 1、そうでない時は 𝑎𝑖𝑗 = 0 とする 文 j に含まれる概念の重要度の合計：𝑝𝑗 = σ𝑚 𝑖=1 𝑤𝑖 𝑎𝑖𝑗 文 j を含む時は 𝑥𝑗 = 1 含まない時は 𝑥𝑗 = 0 として、ナップサック問題に帰着する： 𝑛 最大化 ෍ 𝑝𝑗 𝑥𝑗 𝑗=1 𝑛 条件 ෍ 𝑙𝑗 𝑥𝑗 ≤ 𝐿 𝑗=1 𝑥𝑗 ∈ 0,1 , 𝑗∈𝑁 11

文書要約問題 続々々 しかし、複数文書の要約の際、似た内容の文がいくつかの文書に含まれている可能性がある 既存の概念を含んだ文を付け加えたら目的関数が改善しないようにしたい m 個の変数 𝑧𝑖 を導入し、概念 i を含む文が含まれていれば𝑧𝑖 = 1、そうでなければ𝑧𝑖 = 0 𝑚 最大化 ෍ 𝑤𝑖 𝑧𝑖 𝑛 条件 𝑖=1 ෍ 𝑙𝑗 𝑥𝑗 ≤ 𝐿 𝑗=1 𝑛 ෍ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑧𝑖 . 𝑖 = 1, … , 𝑚, 𝑗=1 𝑥𝑗 ∈ 0,1 , 𝑧𝑗 ∈ 0,1 , （ナップサック制約付き）最大被覆問題 NP困難 𝑗 = 1, … , 𝑛 𝑖 = 1, … , 𝑚 12

商品推薦問題 各顧客に推薦する商品を、予算額の下で、偏りを防ぎながら、期待利益を最大化するよう決定する 顧客の集合を𝑀 = {1, . . , 𝑚}、商品の集合を𝑁 = {1, … , 𝑛}、予算額をB 顧客 i に商品 j を推薦することで生じる期待利益を 𝑝𝑖𝑗 、期待費用を 𝑐𝑖𝑗 型よりが生じないよう、顧客 i に推薦する商品の数を K、商品 j の期待利益を 𝑞𝑗 以上と制約 顧客 i に商品 j を推薦するときは𝑥𝑖𝑗 = 1、しないときは𝑥𝑖𝑗 = 0 とする 13

商品推薦問題 続 最大化 ෍ ෍ 𝑝𝑖𝑗 𝑥𝑖𝑗 𝑖∈𝑀 𝑗∈𝑁 条件 ෍ ෍ 𝑐𝑖𝑗 𝑥𝑖𝑗 ≤ 𝐵 𝑖∈𝑀 𝑗∈𝑁 ෍ 𝑥𝑖𝑗 = 𝐾 𝑖∈𝑀 𝑗∈𝑁 ෍ 𝑝𝑖𝑗 𝑥𝑖𝑗 ≥ 𝑞𝑗 𝑗∈𝑁 𝑖∈𝑀 𝑥𝑖𝑗 ∈ 0,1 , 𝑗 ∈ 𝑁, 𝑖 ∈ 𝑀 NP 困難 14

コミュニティ検出問題 コミュニティ：内の要素が密な関係を持ち、外の要素とは疎な関係を持つ部分ネットワーク ネットワークをコミュニティーに分割したい 15

コミュニティ検出問題 続 グラフ G=(V,E)：頂点の集合 V と辺の集合 𝐸 ⊂ 𝑉 × 𝑉 で定める 辺 𝑒 = (𝑢, 𝑣) の方向を考慮する時は有向グラフと言い、しない時は無効グラフ（𝑒 = {𝑢, 𝑣}と表す） 以降、無向グラフを考え、 𝑢, 𝑣 ∈ 𝐸 の時は 𝑎𝑢𝑣 = 1 とし、そうでない時は 𝑎𝑢𝑣 = 0 とする 頂 v に繋がっている辺の数（vの次数）を𝑑𝑣 で表す k個のコミュニティ（）𝑉1 , … , 𝑉𝑘 に V を分割した時に、𝑣 ∈ 𝑉𝑖 に対し、𝜎𝑣 = 𝑖 とおく 分割 C の良さを表す関数：モジュラリティを次のように定義する 1 𝑑𝑣 𝑑𝑢 𝑄 𝐶 = ෍ ෍ 𝑎𝑢𝑣 − 𝛿 (𝜎𝑢 , 𝜎𝑣 ) 2𝑚 2𝑚 𝑢∈𝑉 𝑣∈𝑉 ただし、m は E の要素の数、δをクロネッカーのデルタとする： 1 𝜎𝑢 = 𝜎𝑣 𝛿 𝜎𝑢 , 𝜎𝑣 = ቊ 0 𝜎𝑢 ≠ 𝜎𝑣 𝑄 𝐶 は「コミュニティ内の頂点同士をつなぐ辺の割合」－「ランダムに辺をつないだ場合の期待値」 16

コミュニティ検出問題 続々 Q(C)を最大にする分割 C を求めたい 𝑑 𝑑 2𝑚 𝑞𝑢𝑣 = 𝑎𝑢𝑣 − 𝑢 𝑣 とし、 変数 𝑥𝑢𝑣 を uとv が同じコミュニティーに入っているときは1、そうでないときは0とする (𝑢 < 𝑣) 同値関係になるため、𝑥𝑢𝑣 = 𝑥𝑣𝑤 なら 𝑥𝑢𝑤 = 1 でないといけないので、𝑥𝑢𝑣 + 𝑥𝑣𝑤 − 𝑥𝑢𝑤 ≤ 1 を課す これもNP困難 17

線形順序付け問題 投票者はいくつかの候補者の組を一対一で比較する 投票の結果を反映した候補の順位を決定したい 候補を頂点にした重み付き有向グラフ 𝐺 = (𝑉, 𝐸) で表す 辺 (𝑢, 𝑣) の重み 𝑐𝑢𝑣 は「uの方がvよりもよい」と投票した人の人数 頂点を左から右に一列に並べて、左側から右側に向かう辺の重みの合計を最大化したい 18

線形順序付け問題 続 変数：𝑥𝑢𝑣 𝑢, 𝑣 ∈ 𝑉, 𝑢 ≠ 𝑣 候補 𝑢 が候補 𝑣 よりも上位ならば 1、そうでなければ 0 全順序になるため、𝑢 ≠ 𝑣 に対し 𝑥𝑢𝑣 = 1 xor 𝑥𝑣𝑢 = 1、つまり 𝑥𝑢𝑣 + 𝑥𝑣𝑢 = 1 及び、𝑥𝑢𝑣 = 𝑥𝑣𝑤 = 1 ならば 𝑥𝑤𝑢 = 0、つまり 𝑥𝑢𝑣 + 𝑥𝑣𝑤 + 𝑥𝑤𝑢 ≤ 2 が必要 整数計画問題： 最大化 ෍ ෍ 𝑐𝑢𝑣 𝑥𝑢𝑣 𝑢∈𝑉 𝑣∈𝑉,𝑣≠𝑢 条件 𝑥𝑢𝑣 + 𝑥𝑣𝑢 = 1 𝑢, 𝑣 ∈ 𝑉, 𝑢 ≠ 𝑣 𝑥𝑢𝑣 + 𝑥𝑣𝑤 + 𝑥𝑤𝑢 ≤ 2 𝑢, 𝑣, 𝑤 ∈ 𝑉, 𝑢 ≠ 𝑣, 𝑣 ≠ 𝑤, 𝑤 ≠ 𝑢 𝑥𝑢𝑣 ∈ 0,1 , 𝑢, 𝑣 ∈ 𝑉, 𝑢 ≠ 𝑣 大事な応用： 経済学：産業連関表（industry transaction matrix）・投入産出表（input-output matrix） 考古学：出土品の年代順の推定 スポーツ：チームのランキング NP 困難 19

アジェンダ ◼ 整数計画問題の定式化 ◼ 整数計画の応用例 ◼ 論理的な制約条件 20

理論的な制約条件 現実問題では、実務上の要求から制約条件を追加されることが多い ナップサック問題を例にいくつかの理論的な制約条件を紹介 21

ナップサック問題 ナップサック問題：𝑛個の荷物と、それぞれの重さ 𝑤𝑗 と価値 𝑝𝑗 が与えられ、詰め込める重さの 上限 𝐶 > 0 の袋に、価値の合計を最大にする荷物の詰め合わせを決定したい 各荷物 𝑗 に対し、変数 𝑥𝑗 を、荷物 j を詰めるならば 1、そうでなければ 0 とする 整数計画問題： 最大化 σ𝑗∈𝑁 𝑝𝑗 𝑥𝑗 条件 σ𝑗∈𝑁 𝑤𝑗 𝑥𝑗 ≤ 𝐶 𝑥𝑗 ∈ 0,1 , 𝑗 = 1, … , 𝑛 また、複数の制約条件を課す時（つまり 𝑤𝑗 → 𝑤𝑗𝑖 、 𝐶 → 𝐶 𝑖 ）、多次元ナップサック問題という 応用：投資計画、ポートフォリオ最適化… 22

ナップサック問題の理論的な制約条件の例 1. 詰め込める荷物の数は高々 𝐾 個： 𝑛 ෍ 𝑥𝑗 ≤ 𝐾 𝑗=1 2. 荷物 𝑗1 , 𝑗2 の少なくとも一方を詰め込む： 𝑥𝑗1 + 𝑥𝑗2 ≥ 1 3. 荷物 𝑗1 を積み込むならば荷物 𝑗2 も詰め込む： 𝑥𝑗1 ≤ 𝑥𝑗2 4. 詰め込む荷物の数は 0 または 2： 𝑛 ෍ 𝑥_𝑗 = 2𝑦, 𝑦 ∈ {0,1} 𝑗=1 もしくは（実現可能解全体の凸包より）： +𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 ≤ 2 −𝑥1 + 𝑥2 + ⋯ + 𝑥𝑛 ≥ 0 +𝑥1 − 𝑥2 + ⋯ + 𝑥𝑛 ≥ 0 … +𝑥1 + 𝑥2 + ⋯ − 𝑥𝑛 ≥ 0 23