4. 頻出する式構造#
4.1. 導入#
数理最適化の定式化は線形な定式化が望ましい． つまりその場合には目的関数と制約条件式は線形な式になる． 線形式は変数の一次結合であり，次のような形をしている．
これを総和記号でより一般的に書き下せば次のようになる．
たった今書き下した一般式は特段難しい式ではないので， 線形な定式化で得られる数式の集まりはどれも簡単ではないかと思われがちである． 実際，数理最適化で線形問題の例として挙げられる定式化を見ると， 添字の種類や次元が多少増えたくらいで，このような総和が散見され，難しさを予想しにくい．
ところが実務で扱う問題を計算機で解けるところまで定式化しようとすると， 確かに線形な定式化の範囲だが，上記に述べたような単純さは次第に消えていく． このためそういった定式化を目にすると，背景が見えず難解に見えてくる．
だがよく見ると頻出する式構造には，記述に意図があることに気付くことになる． そのようなものの中で頻出する式構造の候補を次に挙げる．
SOS (特殊順序集合) 変数制約
疎な記述
目的関数による制約条件式の代用
これらは数式として特徴的な形を伴って表れるため，各々について理解を深めることで， 式構造を読み解けるようになっていく．
4.2. SOS (特殊順序集合) 変数制約#
SOS (Specially Ordered Set) なる集合に属する変数による制約式が定式化で頻出する． この SOS とは次に定めるもので SOS1 と SOS2 の二種類がある．
SOS1 集合
変数集合 \(S\) が与えられたとき，この集合に属する高々一つの変数だけが \(0\) でないならば，集合 \(S\) は SOS1 変数集合 (または単に SOS1) という．
SOS2 集合
順序構造を備えた変数集合 \((S,<)\) が与えられたとき，この集合に属するある隣接する二つの変数のみが，高々 \(0\) でないならば，集合 \(S\) は SOS2 変数集合 (または単に SOS2) という．
注釈
SOS1 および SOS2 に属する変数は必ずしも \(0\)-\(1\) 整数変数 (バイナリ変数) や整数変数に限らない．連続変数であってもよい．ただ応用上は \(0\)-\(1\) 整数変数をよく目にするだろう．
4.2.1. SOS1 について#
SOS1 集合 \(S_1=\{z_i\}_{i\in I}\) に属する変数がすべて \(0\)-\(1\) 整数変数であったとしよう．
すると SOS1 集合に属することから，それら変数は次の条件式が課せられていることを意味する．
これは 計数に関係する論理条件 の MOST に他ならない． また SOS1 の定義で「高々」とあるので，次の条件が課されている場合も考えられる．
これは EXACTLY に他らない． これら条件式は割当問題で頻出，もしくは必須ともいえる条件式である．
このためいくつかのモデリング言語では，SOS1 の上記の制約条件式を背景とした効率的な求解のために， その式構造を何らかの形で明示的に記述できることがある 1このような代数構造を背景としたモデリングのことを総称して「代数的数理モデリング」ということがある． 2モデリング言語 SIMPLE の場合は，選択関数がその一例である．C++SIMPLE の selection や PySIMPLE の Selection である．．
4.2.2. SOS2 について#
まず SOS2 の定義文について補足しよう．
考える順序構造を備えた変数集合 \((S,<)\) とは，各変数を比較したときそれら変数がとる値の大小とは別に， 変数自体の順序が決められたいる集合のことである．
例えば \(S=\{z_1,z_2,z_3,z_4\}\) とあったとき，この変数の添字の大小関係で順序を定義することに相当している． この場合，\(z_1\)，\(z_2\)，\(z_3\)，\(z_4\) の順になっている．
そして定義文にある「隣接」とは，順序付けられた各変数が隣同士の関係になることを述べている． 先の例だと，隣接する二つの変数とは次の三つの場合である．
SOS2 ではこれらの対の何れかが \((0,0)\) でないことを要求している．
SOS2 は SOS1 と比較して，少し応用が見えないかもしれない． SOS2 は「繋がり具合」を論理的に記述する際に頻出する． 代表的な例は区分線形関数 (折線関数の線形表現 や 不連続な区分線形関数) や セパラブルな関数 の定式化である．
4.3. 疎な記述#
\(x_{i,j,k,l,\ldots}\) というように，添字の数が増えてくると， この変数 \(x\) の添字が属する集合として次の直積集合を仮定してしまうことがある．
このような直積構造の集合の要素数は，仮にそれぞれの集合の大きさを \(O(n)\) 程度とすれば， \(k\) 個の直積に対して \(O(n^k)\) だけあることになり， 変数の数がそれだけ存在することになる．これは次の二つの意味で全く現実的ではない．
計算量としての非現実性
例えば \(10\) 万変数は \(10^5\) であるから，\(k=2\) だとしても \(n=10^3=1000\) 程度で \(10\) 万変数を超えることになる． このように直積集合のすべての要素を用いて問題を記述することを「密な記述」という．
定式化としての非現実性
例えば何らかの配送経路を考えた場合に，「密な記述」の場合には， 非常に遠くに離れた拠点間の経路まですべての可能性を考慮することになる． 実運用を想定すれば，あまりに離れた拠点間の経路まで考えることは現実的ではない．
しばしば現実世界は局所的なやりとりで閉じていて，尚且つロスの少ないシステムになっている． このような定性的な性質の対極にあるのが「密な記述」となる．
対して「疎な記述」というものがあり，例えば次のような総和を書いたりする． 但し \([(i, j) \in IJ]\) は Iverson 括弧 である．
これは添字 \(i\) で和をとるのだが，(必ずしも直積集合ではない) 二次元集合 \(IJ\) の要素についてのみ和をとることを表している． 例えば一次元集合 \(I:=\{1,2\}\) と \(J:=\{1,2,3\}\) があり，二次元集合 \(IJ\) が次だったとする．
\(IJ\) は直積集合 \(I\times J\) ではない \(2\) 次元集合である． 先の配送経路の例であれば，実際に運用している拠点間の経路のみを書き出した集合に対応するものである．
この場合に変数の数は冪で増えていない． \(x_{i,j}\) が直積集合で書いた場合だとし，\(|I|\cdot|J|=2\times 3=6\) だけ変数があるのに対して， \(x_{(i,j)}\) は直積集合で書いていない疎な集合の場合で \(|IJ|=3\) と半分になっている． この違いは問題が大規模になるほど顕著になってくるため，「疎な記述」は問題規模に対してスケールする定式化であるといえる．
以上を式構造という観点でまとめると次のようになる．
添字が属する集合は直積集合ではなく，疎な多次元の集合を記述する．
総和をとる添字には「疎な多次元集合に属する下で和をとれ」という条件を記述する．
式の構造が理解できれば，後はこれらを実際のモデリング言語ではどのように記述すればよいかが理解できればよい．
Tip
疎な集合と関連して，二つの疎な集合同士を結合する前処理が必要になることがよくある．
例えば \(IJ = \{(1,2), (1,3), (2,1) \}\) と \(JK = \{(1,1), (2,3), (3,1), (3,2) \}\) から \(J\) の要素が共通する部分を要素に持つ三つ組集合 \(IJK\) が必要になったとしよう．
この場合，求める集合は \(IJK=\{(1,2,3),(1,3,1),(1,3,2),(2,1,1)\}\) となっているが， \(IJK\) を \(IJ\) と \(JK\) の合成で構築したことを数式で 端的に記述するには，\(\cup\) や \(\cap\) および \(\times\) などでは，複雑になり過ぎる．
それ故に疎な集合の説明は自然言語のみになりがちであり，経済的でない． そのような点に問題意識を持ったならば，一つの解決策は関係代数 (relational algebra) を援用することである． ちょうど，今の合成方法は自然結合 (natural join) という二項演算 \(\bowtie\) に相当しており，次のように簡潔に記述できる．
関係代数では他にも様々な結合演算 (や選択 \(\sigma\)・射影 \(\pi\)・商 \(\div\) などの演算) が定義されており，式の整理を自然言語だけに頼らずに遂行できることがある．
4.4. 目的関数による制約条件式の代用#
目的関数の最大化または最小化を想定することで，制約条件式を削減できる場合がある． 制約条件式を削減することでも問題の求解難易度を減らすことができるため，非常に有用な検討事項となる．
例えばバイナリ変数どうしの AND を表す \(z:=z_1\land z_2\) について次の制約条件式があったとする．
この場合にもし \(2z \leq z_1 + z_2\) だけしか制約条件式として課さなかった場合には， \((z_1,z_2)=(1,1)\) のみ \(z\) として \(0\) と \(1\) でどちらをとってもよくなる． 想定としてはこの場合は \(1\) をとってほしい．
さてこのような前提で更に \(z\) を用いた目的関数があって， 次の最適化を考えたとする．
すると \(z\) は「\(0\) と \(1\) のどちらを選べばよいか」という場合について， 「制約条件式が許すならば \(1\) をとる」ということになる． よって \(z_1 + z_2 \leq 1 + z\) を課すことなく，AND として機能することになる． つまり制約条件式を削減できることになり，求解難易度を減らすことに繋がる．
一見，必要と思われる制約条件式がもしモデルに記述されていなかったとしても， このようなことを意図して，式構造を決定している可能性があるというわけである．
関連
引用書式