Ctrl+K

頻出する式構造

4. 頻出する式構造#

4.1. 説明#

数理最適化の定式化は線形な定式化が望ましい． つまりその場合には目的関数と制約条件式は線形な式になる． 線形式は変数の一次結合であり，次のような形をしている．

(4.3)#\[A\cdot x + B\cdot y\]

これを総和記号でより一般的に書き下せば次のようになる．

(4.4)#\[\sum_{i\in I} A_i\cdot x_i\]

たった今書き下した一般式は特段難しい式ではないので， 線形な定式化で得られる数式の集まりはどれも簡単ではないかと思われがちである． 実際，数理最適化で線形問題の例として挙げられる定式化を見ると， 添字の種類や次元が多少増えたくらいで，このような総和が散見され，難しさを予想しにくい．

ところが実務で扱う問題を計算機で解けるところまで定式化しようとすると， 確かに線形な定式化の範囲だが，上記に述べたような単純さは次第に消えていく． このためそういった定式化を目にすると，背景が見えず難解に見えてくる．

だがよく見ると頻出する式構造には，記述に意図があることに気付くことになる． そのようなものの中で頻出する式構造の候補を次に挙げる．

これらは数式として特徴的な形を伴って表れるため，各々について理解を深めることで， 式構造を読み解けるようになっていく．

4.1.1. 疎な記述#

\(x_{i,j,k,l,\ldots}\) というように，添字の数が増えてくると， この変数 \(x\) の添字が属する集合として次の直積集合を仮定してしまうことがある．

(4.5)#\[(i,j,k,l,\ldots) \in I\times J\times K\times L\times \cdots\]

このような直積構造の集合の要素数は，仮にそれぞれの集合の大きさを \(O(n)\) 程度とすれば， \(k\) 個の直積に対して \(O(n^k)\) だけあることになり， 変数の数がそれだけ存在することになる．これは次の二つの意味で全く現実的ではない．

  • 計算量としての非現実性

    例えば \(10\) 万変数は \(10^5\) であるから，\(k=2\) だとしても \(n=10^3=1000\) 程度で \(10\) 万変数を超えることになる． このように直積集合のすべての要素を用いて問題を記述することを「密な記述」という．

  • 定式化としての非現実性

    例えば何らかの配送経路を考えた場合に，「密な記述」の場合には， 非常に遠くに離れた拠点間の経路まですべての可能性を考慮することになる． 実運用を想定すれば，あまりに離れた拠点間の経路まで考えることは現実的ではない．

しばしば現実世界は局所的なやりとりで閉じていて，尚且つロスの少ないシステムになっている． このような定性的な性質の対極にあるのが「密な記述」となる．

対して「疎な記述」というものがあり，例えば次のような総和を書いたりする． 但し \([(i, j) \in IJ]\) は Iverson 括弧 である．

(4.6)#\[y_j := \sum_{i\in I} x_{(i,j)} [(i, j) \in IJ]\]

これは添字 \(i\) で和をとるのだが，(必ずしも直積集合ではない) 二次元集合 \(IJ\) の要素についてのみ和をとることを表している． 例えば一次元集合 \(I:=\{1,2\}\) と \(J:=\{1,2,3\}\) があり，二次元集合 \(IJ\) が次だったとする．

(4.7)#\[IJ := \{(1,2), (1,3), (2,1) \}\]

\(IJ\) は直積集合 \(I\times J\) ではない \(2\) 次元集合である． 先の配送経路の例であれば，実際に運用している拠点間の経路のみを書き出した集合に対応するものである．

この場合に変数の数は冪で増えていない． \(x_{i,j}\) が直積集合で書いた場合だとし，\(|I|\cdot|J|=2\times 3=6\) だけ変数があるのに対して， \(x_{(i,j)}\) は直積集合で書いていない疎な集合の場合で \(|IJ|=3\) と半分になっている． この違いは問題が大規模になるほど顕著になってくるため，「疎な記述」は問題規模に対してスケールする定式化であるといえる．

以上を式構造という観点でまとめると次のようになる．

  • 添字が属する集合は直積集合ではなく，疎な多次元の集合を記述する．

  • 総和をとる添字には「疎な多次元集合に属する下で和をとれ」という条件を記述する．

式の構造が理解できれば，後はこれらを実際のモデリング言語ではどのように記述すればよいかが理解できればよい．

4.1.2. 目的関数による制約条件式の代用#

目的関数の最大化または最小化を想定することで，制約条件式を削減できる場合がある． 制約条件式を削減することでも問題の求解難易度を減らすことができるため，非常に有用な検討事項となる．

例えばバイナリ変数どうしの AND を表す \(z:=z_1\land z_2\) について次の制約条件式があったとする．

(4.8)#\[2z \leq z_1 + z_2 \leq 1 + z\]

この場合にもし \(2z \leq z_1 + z_2\) だけしか制約条件式として課さなかった場合には， \((z_1,z_2)=(1,1)\) のみ \(z\) として \(0\) と \(1\) でどちらをとってもよくなる． 想定としてはこの場合は \(1\) をとってほしい．

さてこのような前提で更に \(z\) を用いた目的関数があって， 次の最適化を考えたとする．

(4.9)#\[\mathrm{Maximize:}~ z\]

すると \(z\) は「\(0\) と \(1\) のどちらを選べばよいか」という場合について， 「制約条件式が許すならば \(1\) をとる」ということになる． よって \(z_1 + z_2 \leq 1 + z\) を課すことなく，AND として機能することになる． つまり制約条件式を削減できることになり，求解難易度を減らすことに繋がる．

一見，必要と思われる制約条件式がもしモデルに記述されていなかったとしても， このようなことを意図して，式構造を決定している可能性があるというわけである．

4.2. 関連#

目次