整数計画法による定式化テクニックをまとめたい
自分用. 定式化するとき同じことを無限回調べてる気がするのでまとめる. 随時更新.
- 全人類が読むべき参考文献
- 整数線形計画問題(ILP: Integer Linear Programming problem)
- 制約でよく使うやつ
- 目的関数のためによく使うやつ
- いかがでしたか?????
全人類が読むべき参考文献
安直に「ILP 定式化」とかで調べると素晴らしい資料が無限個見つかる. 特にお世話になっているものは以下.
- 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の二値だとすると,こんな感じ:
式中の とか とか は定数. 求める変数 が整数(今回は0か1)なのと,目的関数と制約式がともに変数 に対して線形なことに注意する. maximizeはminimizeでもいいし,不等号の向きは逆でもいいし,等式制約があってもいい. 連続変数も含む場合は混合整数線形計画問題(MILP: Mixed-Integer Linear Programming problem)と呼ぶ.
何か解きたい最適化問題があったとして,とにかく上記の整数線形計画問題として表現できれば, CPLEXなどのつよつよ数理計画ソルバにぶん投げることでポンっと最適解を得ることができる.
具体例:ナップサック問題
我々は小学生なので,遠足に持っていくおやつを決めなければならない. おやつ候補は全部で 個あり,各おやつ は満足度 と値段 を持っている. 我々は貪欲な小学生なので,せっかくなら満足度の総和が最大になるようなおやつを選別して遠足に持参したい. しかし,我々は小学生なので,選択したおやつの総計は,先生が決めた予算である 円以下に収めなければならない. どのようにおやつを選べば,予算内で満足度を最大化できるだろうか...
簡単のため,各おやつを一個ずつしか選べないとすると, 予算内で満足度を最大化するようなおやつの(部分)集合 を求める問題になる:
上記の最適化問題を,等価な整数線形計画問題として書き直してみる. 変数 が「おやつ を選んだかどうか()」を表す変数だと思うと, 満足度の総和は ,値段の総計は というように表現できる. そんな感じで,以下のように定式化できる:
やったぁ.簡単ですね. 複数個選びたかったら変数 の値域を自然数全体とかに拡張してあげればよいはず.
ILPでモデリングする醍醐味
上記のILP問題を解けば,めでたく最適解が,つまり,予算内で満足度を最大化するおやつ集合が得られる.
しかし,我々は小学生なので,「うまい棒とビッグカツは役割が被るのでどっちか片方でいい」とか 「蒲焼さん太郎を選ぶなら酢だこさん太郎も選ぶだろ」とか「バナナはおやつにry」とか文句を言う可能性がある.
そういった制約も,うまいことモデリングして線形制約式として表現できれば,結局は整数線形計画問題として扱うことができて, やっぱりCPLEXに祈りを捧げるだけで最適解が得られるということになる. よかったね.
この「うまいことモデリングして線形制約式として表現」という部分について, 頻繁に使われるような典型テクと思しきものを,いちいち調べずに済むようまとめておこう, というのが本記事の主旨である(前置きの御託がなげぇ).
制約でよく使うやつ
論理関係
二値変数 について, が偽, が真を表すようなブール変数だと思うことにして,変数間の論理関係についての制約を線形不等式で表現する. モデリングに込めたい大抵のお気持ちはこれで表現できる(気がする).
例えば,「うまい棒とビッグカツは役割が被るのでどっちか片方でいい」とか「蒲焼さん太郎を選ぶなら酢だこさん太郎も選ぶだろ」とかは,それぞれ以下の制約で書ける:
うまい棒とビッグカツの両方を選ぶと となり制約に反するので,同時に選ぶことはできない.
また,蒲焼さん太郎を選ぶ()と制約式は になって,酢だこさん太郎も同時に選ぶことになる.
以下では,二値変数 に対する論理演算をいくつか考える. 演算結果を表す補助変数を として,線形不等式で論理演算を表現すると,次のようになる:
AND
2つの変数 に対するAND演算 は,
これを2つ以上の場合に一般化すると,
OR
2つの変数 に対するOR演算 は,
これを2つ以上の場合に一般化すると,
XOR
2つの変数 に対するXOR演算 は,
これもANDやORと同様に一本の不等式で書けるかはよくわからない...
離接制約
変数 に対して,次のような制約を表現したいとする:
こういうときは大抵,Big-M制約と呼ばれる制約を使って表現する. 補助変数として二値変数 を導入すると,次のように表現できる:
ここで は条件 を満たす定数.
定数 が条件を満たしていれば,必ずどちらか片方の制約は変数 に関わらず成立するようになる(冗長というらしい).
クソデカ定数 はなるべく小さい値にしてあげないとソルバが不安定になる(解くのに時間がかかる)ので注意が必要. というか可能ならばBig-M制約はなるべく使わない方がいいらしい...
絶対値
変数 に対して,次の制約を満たす変数 を導入したいとする:
これもやっぱり,補助変数として二値変数 を導入し, を条件 を満たす定数として,Big-M制約で表現できる:
ここで は非負の補助変数で,それぞれ の正の部分と負の部分を表している.
補助変数 は,絶対値の中身が正なら になり,負なら になる.
絶対値が入っていても,単に不等式制約 を表現したいだけなら,クソデカ定数を使わなくても事足りる:
これはまぁ,絶対値の定義を考えると当たり前だった...
目的関数のためによく使うやつ
max-min型目的関数
変数 に対して,次のような目的関数を最大化したいとする:
ぱっと見た感じ非線形っぽいけど,補助変数 を導入して線形不等式で書き直せる:
制約式は任意の に対して となることを意味していて,
言い換えると変数 の上限は の最小値になるよ〜と解釈できる.
変数 は目的関数として最大化されるので,結果的に上限の値,つまり の最小値に張り付いてくれる.
絶対値
変数 に対して,次のような目的関数を最小化したいとする:
誤差項みたいなやつの最小化とか,-ノルムとかを使いたいと思うとこの形は避けられない(気がする).
絶対値が と表現できることを思い出すと, やっぱり補助変数 を導入して線形不等式で書き直せる:
各 は最小化されるので,制約式で か のどちらか大きい方の値,つまり に張り付くことになる.
いかがでしたか?????
目的関数はどっちかというと線形計画法のテクニックじゃったな...