5. if-else 文と制約条件#
5.1. 導入#
if-else 文とは「もし～ならば～であり，そうでないならば～である．」ということを意図する文で，
プログラミングの基本的な制御構造の一つである．
一方で直面している問題を制約条件として文章で表現すると，
if-else 文で記述できることは何も珍しいことではなく，
数理最適化モデルの定式化の中で if-else 文は基本的な役割を果たす．
5.2. 問題背景#
if-else 文それ自体の考え方は定式化を行う上では自然なものだが，
これをプログラミング言語の文脈で捉えると，
定式化を洗練させることができなくなってしまう可能性がしばしばある．
例えば次のような文章で記述された制約条件があったとする．
もし変数 \(x\) が \(1\) 以上ならば制約式 \(Co\) として \(f(y) \leq 0\) を定義する．
これをプログラミング言語の文脈で解釈と記述を試みると次のような疑似コードになる．
1if(x >= 1){
2 Co = f(y) <= 0;
3}
しかし数理最適化では「変数」は「式」の一部として記述されなければならない．
このように「変数」を条件判定の制御構文である if 文に含ませると，
この if 文を「式」として解釈しなければならないことになる．
\(x\) は「変数」なので \(2\) という値をとる場合や \(0\) という値をとる場合について， 制約条件を満たすかどうか，そして目的関数が最適となるかを求解する役割を持っている．
今のように if 文の条件式として記述した場合には，次の曖昧さが数理最適化の文脈で発生する．
\(x \geq 1\) が変数 \(x\) に対する制約条件式として解釈されるべきものである．つまり \(x\) は \(1\) 以上の範囲をとる変数である．
\(x\) は \(1\) 未満の値も許されるが \(1\) 以上の場合に限って制約条件式 \(f(y) \leq 0\) が課される．
我々が望むものは後者の解釈であり，離接制約 なるものの典型例となっている．
5.3. 定式化の検討#
先に挙げた例を数理最適化モデルとして定式化を図ると次のようになる．
\(z\) は \(1\) または \(0\) をとる変数であり， それぞれの値に応じて \(x \geq 1\) であるか，そうでないかを対応させている． このことを \(z := [x\geq 1]\) と書いた． \([P]\) は Iverson 括弧 とよばれ，\(P\) の真偽に応じてそれぞれ \(1\) と \(0\) をとる．
\(x\geq 1\) を表す \(z=1\) であれば，\(f(y) \leq 0\) であり， 一方で \(x < 1\) を表す \(z=0\) であれば，\(f(y)\leq M\) となる． この \(M\) は Big M とよばれ，\(f(y)\) がとりえる最大の値に設定される定数である． \(M\) の定義から \(f(y)\leq M\) は \(f(y)\) がどんな値をとっても構わないことになる． つまり換言すれば，\(f(y)\) には何も課されていないことになる． \(x < 1\) については何も課したくないので，これは我々が表現したい記述になっている． 以上から次の対応があることがわかった．
重要
条件式 \(P\) に対する if 文による条件分岐は，「どの条件分岐を選択するか」という変数 \(z:=[P]\) に化ける．
さて導入した新たな変数 \(z\) は次で定めることができる．
まず \(z := [x\geq A]\) という場合を一般に考えてみると， \([x\geq A] = [x - A\geq 0]\) なので，\(x - A\) という定数だけ移動させた新たな変数 \(x^{\prime}\) をいつでも考えることができるから， 改めて \(z := [x\geq 0]\) について構成できれば十分である．
この \(z := [x\geq 0]\) は次で定式化を図る．
ここで書いた \(M\) は変数 \(x\) に対する新たな Big M である． そして \(\varepsilon\) は small ε とよばれるもので，\(x\) がとりえる最小単位に対応する．
上記の連立不等式によって \(z\) の値とこれに対応する \(x\) の範囲は次の表のようになる．
\(z\) |
\(x\) の範囲 |
|---|---|
\(1\) |
\(0\leq x \leq M - \varepsilon\) |
\(0\) |
\(-M \leq x \leq -\varepsilon\) |
この話題のより一般的な議論は 不等式制約の切り替え であり，インジケータ変数 として変数 \(z\) をより抽象的に捉えることに繋がる．
5.4. 定式化の中での制御構造#
変数を if-else 文の条件式として記述することは定式化の文脈には沿っていないことを述べた．
しかしもし条件式が「変数」ではなく「定数」であったならば，if-else 文という制御構造には一定の価値を見出すことができる．
それは例えば次のようなものである．
もし定数 \(A\) が \(1\) 以上ならば制約式 \(Co\) として \(f(y) \leq 0\) を定義する．
再びプログラミング言語の文脈で解釈と記述を試みると次のような疑似コードになる．
1if(A >= 1){
2 Co = f(y) <= 0;
3}
対して数理最適化モデルの文脈で定式化を図ると次のようになる．
これらのどちらに価値を見出すかは， 使用するモデリング言語や開発プロジェクトの様々な要因や状況などに応じて変わるだろう． 少なくとも数理最適化モデルとして，定数を用いた条件式はプログラミング言語のような記述でも許容範囲にある．
5.5. 区分定義関数について#
if-else 文は制約条件の有効無効に関係する事柄の記述以外にも「式」，もっと簡単に言えば関数の記述にも表れる．
このような関数の例として区分定義関数 (piecewise-defined function) があり， 中でも 折線関数の線形表現 は応用上頻出する基本的な例である．
これらは インジケータ変数 による 変数や関数の切り替え として捉えることができ， 数理最適化モデルの文脈で適切な取り扱いが要求されるものの一つである．
5.6. 関連#
引用書式