Ctrl+K

インジケータ変数

1. インジケータ変数#

1.1. 説明#

インジケータ変数もしくは標識変数とは「二値状態を判別するための変数」である． 二値状態としては状態の on/off や真偽の true/false，コインの表裏など様々である．

これら二値状態を記述できるため，インジケータ変数は以下の数式に関して， 制御構文 (if 文や for 文など) の記述を用いずに数理最適化の文脈で線形な定式化に帰着させることができる．

  • AND (\(\land\)) や OR (\(\lor\)) などの論理式

  • 区分的な場合分けを伴う関数 (piecewise function)

(1.8)#\[\begin{split}f(x) = \begin{cases} f_1(x) & (x\in R_1), \\ f_2(x) & (x\in R_2), \\ \vdots & \\ f_n(x) & (x\in R_n) \end{cases}\end{split}\]

これらによって単なる二値状態の表現だけでなく，以下に挙げる数々の問題を 混合整数計画問題 （Mixed Integer Programming Problem：MILP）で表現できる．

以下ではこれらのうち，「不等式制約の切り替え」「変数や関数の切り替え」について言及する．

1.1.1. 不等式制約の切り替え#

今，不等式制約として \(g(x)\geq 0\) と \(g(x)< 0\) があって， これらをインジケータ変数 \(z\) の値で次式のように切り替える定式化の記述について考える．

(1.9)#\[z = [g(x)\geq 0]\]

ここに \([g(x)\geq 0]\) は \(g(x)\geq 0\) が真である場合に \(1\) を，偽である場合に \(0\) を意味する括弧であり， Iverson 括弧 とよばれるものである．

\(z = [g(x)\geq 0]\) を線形な制約条件式として記述するためには，以下の二つの式を連立させればよい． 但し \(M\) と \(\varepsilon\) は \(g(x)\) についての Big M および small ε である．

(1.10)#\[\begin{split}g(x) &\geq - M\cdot (1 - z), \\ -g(x) &\geq \varepsilon - M\cdot z\end{split}\]

これが確かに \(z = [g(x)\geq 0]\) を表していることは，次のように具体的に吟味することで理解できる．

  • \(z=1\) ならば，\(g(x)\geq 0\) かつ \(-g(x)\geq \varepsilon - M\) である．これらをまとめると，\(0\leq g(x)\leq M - \varepsilon\) である．これは事実上，\(0\leq g(x)\) という制約が適用される事を示している．

  • \(z=0\) ならば，\(g(x)\geq -M\) かつ \(-g(x)<0\) である．これらをまとめると，\(-M\leq g(x)\leq -\varepsilon\) である．これは事実上，\(g(x)<0\) という制約が適用される事を示している．

表にすると次のようになる．

\(z\)

\(x\) の範囲

表現したい \(x\) の範囲

\(1\)

\(0\leq g(x) \leq M - \varepsilon\)

\(g(x) \geq 0\)

\(0\)

\(-M \leq g(x) \leq -\varepsilon\)

\(g(x) < 0\)

ここで \(z=1\) の場合の \(g(x)\) の範囲が \(M\) までではなく，\(M - \varepsilon\) となっているので厳密ではない． より正確を期す場合には次のように定式化すればよい．

(1.11)#\[\begin{split}g(x) &\geq - M_-\cdot (1 - z), \\ -g(x) &\geq \varepsilon - (M_+ + \varepsilon)\cdot z\end{split}\]

この場合の \(z\) と \(x\) の範囲の対応表は次のようになる．

\(z\)

\(x\) の範囲

表現したい \(x\) の範囲

\(1\)

\(0\leq g(x) \leq M_+\)

\(g(x) \geq 0\)

\(0\)

\(-M_- \leq g(x) \leq -\varepsilon\)

\(g(x) < 0\)

これは連立させて \(\bar{z}:=1-z\) とすると次のように整理できて，より見通しの良い式が得られる．

(1.12)#\[- M_-\cdot \bar{z} \leq g(x) \leq M_+\cdot z - \varepsilon\cdot \bar{z}\]

これからまた次のような一般形が得られる．

(1.13)#\[L_1\cdot z + L_0\cdot \bar{z} \leq g(x) \leq U_1\cdot z + U_0\cdot \bar{z}\]

\(z\)

\(x\) の範囲

\(1\)

\(L_1\leq g(x) \leq U_1\)

\(0\)

\(L_0\leq g(x) \leq U_0\)

つまりインジケータ変数 \(z\) を使用すれば，\((L_1 \leq x \leq U_1) \lor (L_0 \leq x \leq U_0)\) のような不等式制約の OR が，次式で表現できる．

(1.14)#\[L_1\cdot z + L_0\cdot (1-z) \leq x \leq U_1\cdot z + U_0\cdot (1-z)\]

以上の話題は 論理式の線形表現 での 離接制約 の特殊な例である．

1.1.2. 変数や関数の切り替え#

インジケータ変数 \(z\) を用いると，不等式制約の切り替えだけでなく， 変数の値を固定したり関数を切り替えることができる． 以下はその例であり，Big M を伴った記述となる．

  • \(z\) が \(0\) ならば，非負変数 \(x\) を \(0\) に固定する場合

(1.15)#\[0\leq x\leq M \cdot z\]

  • \(z\) が \(1\) ならば，非負変数 \(x\) を \(0\) に固定する場合

(1.16)#\[0\leq x\leq M \cdot (1-z)\]

また「不等式制約の切り替え」の内容を用いると， \(z\) の値によって関数 \(f\) を切り替える事ができる． そのために十分大きなパラメータ \(M\) (Big M) を用いて， 次の記述をすればよい．

(1.17)#\[\begin{split}\begin{array}{lccccc} \mathrm{(1)} & -M\cdot (1-z) & \leq & f - A\cdot x & \leq & M\cdot (1-z) \\ \mathrm{(2)} & -M\cdot z & \leq & f - B\cdot x & \leq & M\cdot z \end{array}\end{split}\]

これで確かに表現できていることの説明は次のとおり．

  • \(z=1\) ならば，\(f\) は (1) により \(A\cdot x\) に固定され，(2) は事実上有効ではない．

  • \(z=0\) ならば，\(f\) は (2) により \(B\cdot x\) に固定され，(1) の制約は効いていない．

つまり次の関数が記述できた．

(1.18)#\[\begin{split}f_z(x) = \begin{cases} A\cdot x & (z = 1), \\ B\cdot x & (z = 0) \end{cases}\end{split}\]

上記の話題に関するより高度な一般化の例は 折線関数の線形表現 である．

1.2. 応用#

1.3. 関連#

目次