整数計画法による定式化テクニックをまとめたい

自分用． 定式化するとき同じことを無限回調べてる気がするのでまとめる． 随時更新．

全人類が読むべき参考文献

安直に「ILP 定式化」とかで調べると素晴らしい資料が無限個見つかる． 特にお世話になっているものは以下．

• 組合せ最適化入門：線形計画から整数計画まで from Shunji Umetani
  www.slideshare.net
• 整数計画法による定式化入門（藤江哲也, オペレーションズ・リサーチ 4月号 2012年 Vol.57 No.4）
• 組合せ最適化入門：線形計画から整数計画まで（梅谷俊治, 自然言語処理 2014 年 9 月 Vol.21 No.5）
• 9 Mixed integer optimization — MOSEK Modeling Cookbook 3.2.2

整数線形計画問題（ILP: Integer Linear Programming problem）

変数が整数に制約された線形計画問題． 簡単のために変数がすべて0か1の二値だとすると，こんな感じ：

maximizesubject to∑n=1Ncn⋅xn∑n=1Nan,m⋅xn≤bmxn∈{0,1}(m=1,…,M)(n=1,…,N)$\begin{array}{clll}& \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& {\displaystyle \sum _{n=1}^N{c}_n\cdot x_n}& \\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& {\displaystyle \sum _{n=1}^N{a}_{n,m}\cdot x_n\le b_m}& (m=1,\dots ,M)\\ & & x_n\in \{0,1\}& (n=1,\dots ,N)\end{array}$

式中の cn$c_n$ とか an,m$a_{n,m}$ とか bm$b_m$ は定数． 求める変数 xn$x_n$ が整数（今回は0か1）なのと，目的関数と制約式がともに変数 xn$x_n$ に対して線形なことに注意する． maximizeはminimizeでもいいし，不等号の向きは逆でもいいし，等式制約があってもいい． 連続変数も含む場合は混合整数線形計画問題（MILP: Mixed-Integer Linear Programming problem）と呼ぶ．

何か解きたい最適化問題があったとして，とにかく上記の整数線形計画問題として表現できれば， CPLEXなどのつよつよ数理計画ソルバにぶん投げることでポンっと最適解を得ることができる．

具体例：ナップサック問題

我々は小学生なので，遠足に持っていくおやつを決めなければならない． おやつ候補は全部で N$N$ 個あり，各おやつ n∈{1,…,N}$n\in \{1,\dots ,N\}$ は満足度 sn>0$s_n>0$ と値段 pn>0$p_n>0$ を持っている． 我々は貪欲な小学生なので，せっかくなら満足度の総和が最大になるようなおやつを選別して遠足に持参したい． しかし，我々は小学生なので，選択したおやつの総計は，先生が決めた予算である B$B$ 円以下に収めなければならない． どのようにおやつを選べば，予算内で満足度を最大化できるだろうか．．．

簡単のため，各おやつを一個ずつしか選べないとすると， 予算内で満足度を最大化するようなおやつの（部分）集合 S⊆{1,…,N}$S\subseteq \{1,\dots ,N\}$ を求める問題になる：

maximizesubject to∑n∈Ssn∑n∈Spn≤BS⊆{1,…,N}$\begin{array}{clll}& \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& {\displaystyle \sum _{n\in S}{s}_n}& \\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& {\displaystyle \sum _{n\in S}{p}_n\le B}& \\ & & S\subseteq \{1,\dots ,N\}& \end{array}$

上記の最適化問題を，等価な整数線形計画問題として書き直してみる． 変数 xn∈{0,1}$x_n\in \{0,1\}$ が「おやつ n$n$ を選んだかどうか（n∈S$n\in S$）」を表す変数だと思うと， 満足度の総和は ∑Nn=1sn⋅xn$\sum _{n=1}^N{s}_n\cdot x_n$ ，値段の総計は ∑Nn=1pn⋅xn$\sum _{n=1}^N{p}_n\cdot x_n$ というように表現できる． そんな感じで，以下のように定式化できる：

maximizesubject to∑n=1Nsn⋅xn∑n=1Npn⋅xn≤Bxn∈{0,1}(n=1,…,N)$\begin{array}{clll}& \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& {\displaystyle \sum _{n=1}^N{s}_n\cdot x_n}& \\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& {\displaystyle \sum _{n=1}^N{p}_n\cdot x_n\le B}& \\ & & x_n\in \{0,1\}& (n=1,\dots ,N)\end{array}$

やったぁ．簡単ですね． 複数個選びたかったら変数 xn$x_n$ の値域を自然数全体とかに拡張してあげればよいはず．

ILPでモデリングする醍醐味

上記のILP問題を解けば，めでたく最適解が，つまり，予算内で満足度を最大化するおやつ集合が得られる．

しかし，我々は小学生なので，「うまい棒とビッグカツは役割が被るのでどっちか片方でいい」とか 「蒲焼さん太郎を選ぶなら酢だこさん太郎も選ぶだろ」とか「バナナはおやつにry」とか文句を言う可能性がある．

そういった制約も，うまいことモデリングして線形制約式として表現できれば，結局は整数線形計画問題として扱うことができて， やっぱりCPLEXに祈りを捧げるだけで最適解が得られるということになる． よかったね．

この「うまいことモデリングして線形制約式として表現」という部分について， 頻繁に使われるような典型テクと思しきものを，いちいち調べずに済むようまとめておこう， というのが本記事の主旨である（前置きの御託がなげぇ）．

制約でよく使うやつ

論理関係

二値変数 xn∈{0,1}$x_n\in \{0,1\}$ について， xn=0$x_n=0$ が偽，xn=1$x_n=1$ が真を表すようなブール変数だと思うことにして，変数間の論理関係についての制約を線形不等式で表現する． モデリングに込めたい大抵のお気持ちはこれで表現できる（気がする）．

例えば，「うまい棒とビッグカツは役割が被るのでどっちか片方でいい」とか「蒲焼さん太郎を選ぶなら酢だこさん太郎も選ぶだろ」とかは，それぞれ以下の制約で書ける：

xうまい棒+xビッグカツ≤1x蒲焼さん太郎≤x酢だこさん太郎$$\begin{gathered} x_{\text{うまい棒}}+x_{\text{ビッグカツ}}\le 1 \\ {x}_{\text{蒲焼さん太郎}}\le x_{\text{酢だこさん太郎}} \end{gathered}$$

うまい棒とビッグカツの両方を選ぶと xうまい棒+xビッグカツ=2$x_{\text{うまい棒}}+x_{\text{ビッグカツ}}=2$ となり制約に反するので，同時に選ぶことはできない． また，蒲焼さん太郎を選ぶ（x蒲焼さん太郎=1$x_{\text{蒲焼さん太郎}}=1$）と制約式は 1≤x酢だこさん太郎$1\le x_{\text{酢だこさん太郎}}$ になって，酢だこさん太郎も同時に選ぶことになる．

以下では，二値変数 xn∈{0,1}$x_n\in \{0,1\}$ に対する論理演算をいくつか考える． 演算結果を表す補助変数を z∈{0,1}$z\in \{0,1\}$ として，線形不等式で論理演算を表現すると，次のようになる：

AND

2つの変数 xi,xj∈{0,1}$x_i,x_j\in \{0,1\}$ に対するAND演算 xi∧xj$x_i\wedge x_j$ は，

xi∧xj=z⟺⎧⎩⎨xi+xj−z≤1−xi+z≤0−xj+z≤0⟺0≤x1+x2−2⋅z≤1$x_i\wedge x_j=z⟺\{\begin{array}{l}{x}_i+x_j-z\le 1\\ -x_i+z\le 0\\ -x_j+z\le 0\end{array}⟺0\le x_1+x_2-2\cdot z\le 1$

これを2つ以上の場合に一般化すると，

x1∧⋯∧xN=z⟺0≤∑Nn=1xn−N⋅z≤N−1$x_1\wedge \cdots \wedge x_N=z⟺0\le \sum _{n=1}^N{x}_n-N\cdot z\le N-1$

OR

2つの変数 xi,xj∈{0,1}$x_i,x_j\in \{0,1\}$ に対するOR演算 xi∨xj$x_i\vee x_j$ は，

xi∨xj=z⟺⎧⎩⎨xi+xj−z≥0xi−z≤0xj−z≤0⟺0≤−x1−x2+2⋅z≤1$x_i\vee x_j=z⟺\{\begin{array}{l}{x}_i+x_j-z\ge 0\\ x_i-z\le 0\\ x_j-z\le 0\end{array}⟺0\le -x_1-x_2+2\cdot z\le 1$

これを2つ以上の場合に一般化すると，

x1∨⋯∨xN=z⟺0≤N⋅z−∑Nn=1xn≤N−1$x_1\vee \cdots \vee x_N=z⟺0\le N\cdot z-\sum _{n=1}^N{x}_n\le N-1$

XOR

2つの変数 xi,xj∈{0,1}$x_i,x_j\in \{0,1\}$ に対するXOR演算 xi⊕xj$x_i\oplus x_j$ は，

xi⊕xj=z⟺⎧⎩⎨⎪⎪⎪⎪⎪⎪xi+xj−z≥0xi−xj−z≤0−xi+xj−z≤0xi+xj+z≤2$x_i\oplus x_j=z⟺\{\begin{array}{l}{x}_i+x_j-z\ge 0\\ x_i-x_j-z\le 0\\ -x_i+x_j-z\le 0\\ x_i+x_j+z\le 2\end{array}$

これもANDやORと同様に一本の不等式で書けるかはよくわからない．．．

離接制約

変数 xn∈R$x_n\in \mathbb{R}$ に対して，次のような制約を表現したいとする：

∑Nn=1an,1⋅xn≤b1∨∑Nn=1an,2⋅xn≤b2$\sum _{n=1}^N{a}_{n,1}\cdot x_n\le b_1\vee \sum _{n=1}^N{a}_{n,2}\cdot x_n\le b_2$

こういうときは大抵，Big-M制約と呼ばれる制約を使って表現する． 補助変数として二値変数 z∈{0,1}$z\in \{0,1\}$ を導入すると，次のように表現できる：

∑Nn=1an,1⋅xn−b1≤M1⋅(1−z)∑Nn=1an,2⋅xn−b2≤M2⋅z$$\begin{gathered} \sum _{n=1}^N{a}_{n,1}\cdot x_n-b_1\le M_1\cdot (1-z) \\ \sum _{n=1}^N{a}_{n,2}\cdot x_n-b_2\le M_2\cdot z \end{gathered}$$

ここで M1,M2$M_1,M_2$ は条件 Mm≥maxxn∑Nn=1an,m⋅xn−bm$M_m\ge \underset{x_n}{max}\sum _{n=1}^N{a}_{n,m}\cdot x_n-b_m$ を満たす定数． 定数 M1,M2$M_1,M_2$ が条件を満たしていれば，必ずどちらか片方の制約は変数 xn$x_n$ に関わらず成立するようになる（冗長というらしい）．

クソデカ定数 M$M$ はなるべく小さい値にしてあげないとソルバが不安定になる（解くのに時間がかかる）ので注意が必要． というか可能ならばBig-M制約はなるべく使わない方がいいらしい．．．

絶対値

変数 xn∈R$x_n\in \mathbb{R}$ に対して，次の制約を満たす変数 y≥0$y\ge 0$ を導入したいとする：

y=|∑Nn=1cn⋅xn|$y=|\sum _{n=1}^N{c}_n\cdot x_n|$

これもやっぱり，補助変数として二値変数 z∈{0,1}$z\in \{0,1\}$ を導入し， M$M$ を条件 M≥maxxn|∑Nn=1cn⋅xn|$M\ge \underset{x_n}{max}|\sum _{n=1}^N{c}_n\cdot x_n|$ を満たす定数として，Big-M制約で表現できる：

y+−y−=∑Nn=1cn⋅xny++y−=yy+≤M⋅zy−≤M⋅(1−z)$$\begin{gathered} y^{+}-y^{-}=\sum _{n=1}^N{c}_n\cdot x_n \\ {y}^{+}+y^{-}=y \\ {y}^{+}\le M\cdot z \\ {y}^{-}\le M\cdot (1-z) \end{gathered}$$

ここで y+,y−≥0$y^{+},y^{-}\ge 0$ は非負の補助変数で，それぞれ ∑Nn=1cn⋅xn$\sum _{n=1}^N{c}_n\cdot x_n$ の正の部分と負の部分を表している． 補助変数 z$z$ は，絶対値の中身が正なら z=1$z=1$ になり，負なら z=0$z=0$ になる．

絶対値が入っていても，単に不等式制約 |∑Nn=1an,m⋅xn|≤bm$|\sum _{n=1}^N{a}_{n,m}\cdot x_n|\le b_m$ を表現したいだけなら，クソデカ定数を使わなくても事足りる：

|∑Nn=1an,m⋅xn|≤bm⟺−bm≤∑Nn=1an,m⋅xn≤bm$|\sum _{n=1}^N{a}_{n,m}\cdot x_n|\le b_m⟺-b_m\le \sum _{n=1}^N{a}_{n,m}\cdot x_n\le b_m$

これはまぁ，絶対値の定義を考えると当たり前だった．．．

目的関数のためによく使うやつ

max-min型目的関数

変数 xn∈R$x_n\in \mathbb{R}$ に対して，次のような目的関数を最大化したいとする：

maximizemin{c1⋅x1,…,cN⋅xN}$\begin{array}{cll}& \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& min\{c_1\cdot x_1,\dots ,c_N\cdot x_N\}\end{array}$

ぱっと見た感じ非線形っぽいけど，補助変数 y∈R$y\in \mathbb{R}$ を導入して線形不等式で書き直せる：

maximizesubject toyy≤cn⋅xn(n=1,…,N)$\begin{array}{clll}& \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& y& \\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& y\le c_n\cdot x_n& (n=1,\dots ,N)\end{array}$

制約式は任意の n∈{1,…,N}$n\in \{1,\dots ,N\}$ に対して y≤cn⋅xn$y\le c_n\cdot x_n$ となることを意味していて， 言い換えると変数 y$y$ の上限は c1⋅x1,…,cN⋅xN$c_1\cdot x_1,\dots ,c_N\cdot x_N$ の最小値になるよ〜と解釈できる． 変数 y$y$ は目的関数として最大化されるので，結果的に上限の値，つまり c1⋅x1,…,cN⋅xN$c_1\cdot x_1,\dots ,c_N\cdot x_N$ の最小値に張り付いてくれる．

絶対値

変数 xn∈R$x_n\in \mathbb{R}$ に対して，次のような目的関数を最小化したいとする：

minimize∑n=1N|cn⋅xn|$\begin{array}{cll}& \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& {\displaystyle \sum _{n=1}^N|c_n\cdot x_n|}\end{array}$

誤差項みたいなやつの最小化とか，ℓ1${\ell }_1$-ノルムとかを使いたいと思うとこの形は避けられない（気がする）．

絶対値が |cn⋅xn|=max{cn⋅xn,−cn⋅xn}$|c_n\cdot x_n|=max\{c_n\cdot x_n,-c_n\cdot x_n\}$ と表現できることを思い出すと， やっぱり補助変数 yn≥0$y_n\ge 0$ を導入して線形不等式で書き直せる：

minimizesubject to∑n=1Nynyn≥cn⋅xnyn≥−cn⋅xn(n=1,…,N)(n=1,…,N)$\begin{array}{clll}& \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}& {\displaystyle \sum _{n=1}^N{y}_n}& \\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& y_n\ge c_n\cdot x_n& (n=1,\dots ,N)\\ & & y_n\ge -c_n\cdot x_n& (n=1,\dots ,N)\end{array}$

各 yn$y_n$ は最小化されるので，制約式で cn⋅xn$c_n\cdot x_n$ か −cn⋅xn$-c_n\cdot x_n$ のどちらか大きい方の値，つまり max{cn⋅xn,−cn⋅xn}=|cn⋅xn|$max\{c_n\cdot x_n,-c_n\cdot x_n\}=|c_n\cdot x_n|$ に張り付くことになる．

いかがでしたか？？？？？

目的関数はどっちかというと線形計画法のテクニックじゃったな．．．