1. 数理最適化法 (数理計画法) による定式化とは#
1.1. 導入#
数理最適化法 (Mathematical Optimization) または数理計画法 (Mathematical Programming) による定式化とは， 以下の三要素を適切に設定することで問題を記述することである．
変数
制約条件
目的関数
1.2. 変数#
何を変数とするか容易にわかる場合もあるが， そうでない場合は制約条件や目的関数から類推するとよい． ある何かを変更することで，結果として損益などの最適化したい数値に影響が生じる場合には，その何かは変数である可能性が高いからである．
やや抽象的に言えば，因果的な関係を見出して原因となっている部分が変数になっていると考えられる． また同時に結果に対応する部分が目的関数である可能性が高い．
変数の表現方法は一意でなく，同じ問題でも異なる数理最適化の定式化になりうる． 逆に同じ問題でも様々な定式化方法があるので，変数の多様な表現方法の参考になる．
1.3. 制約条件#
制約条件とは読んで字のごとく，守らなければならない約束事である． 「最低限の需要量を満たさなければならない」「誰か一人を選ばなければならない」といったようなもので， 「～なければならない」という文で述べられる事柄が制約条件の候補となる．
中には必ずしも数理最適化の定式化として扱う必要がない制約条件や， 暗黙のルールともいうべき制約条件が定式化要件に含まれていることがある．
特に後者は人間または組織が無意識に心がけているルールであることも多く， 定式化のための要件整理で予め洗い出しておくことが肝要である．
1.4. 目的関数#
「コストを最小限にしたい」「利益を最大化したい」など目的関数は「何をしたいか」に直結するため， 変数や制約条件と比較して，何が目的関数となるか判明していることが多い． このため定式化に迷ったら，目的関数をまず定めてから，変数や制約条件を考えるとよいだろう．
考える定式化したい問題によっては目的関数自体が必要ない場合もある． そのような問題とは制約条件さえ満たせば良いという問題である． 例えば物を箱に詰める場合に「箱に詰まってさえいれば良い」という場合には， 目的関数を定める必要がない．
1.5. 求解アルゴリズムと汎用性#
数理最適化の文脈で定式化がなされると，次のように問題が記述されたことになる．
定式化の要素 |
表現したいこと |
数式 |
|---|---|---|
変数 |
決めたいこと |
\(x,y,z\) などで表記する制約条件・目的関数に含まれる文字 |
制約条件 |
守らないといけないこと |
\(A\cdot x \geq b\) などの不等式または等式 |
目的関数 |
最も価値あること |
\(\sum_{i\in I}C_i\cdot x_i\) などの数式 |
このように記述されると，元の問題の個別の特徴は抽象化されて汎用的に扱えるようになる． すると「条件付き最大化または最小化問題」を如何にして解くかという問題に帰着することになる． これによって問題記述と問題求解のタスクを明確に分割できる． つまり実務家は問題の表現に注力し，表現された問題の求解は理論家が開発するという分業体制をとることができる．
そうして開発する様々な求解アルゴリズムを備えたプログラムを汎用ソルバーという． そして汎用ソルバーは数理最適化問題の数式記述を対象とするため， 個別の問題に特化したアルゴリズムを採用しない．
例えば最短経路問題には Dijkstra 法が有効なアルゴリズムの一つであるが， これは最短経路問題 (もしくはその亜種) にしか使用できない． 実務的な問題は最短経路問題のように必ずしも純粋にある一つの問題として与えられることは少なく， また仮に与えられたとしても，問題拡張によって，それら問題に特化した個別のアルゴリズムを使用できなくなるということは珍しくない． しかし汎用ソルバーの場合にはそのようなことが生じにくい． まとめると汎用ソルバーの利点には次のような特徴がある．
問題設定に関わらず標準的なアルゴリズムが適用できる．個別のアルゴリズムを開発・保守するコストを抑えられる．
問題の変形があっても制約条件の変更など，数式レベルでの問題記述の範囲にとどめることができて，比較的対応しやすい．
1.6. 定式化の難易度#
数理最適化法を用いて問題解決する実務家は，主として問題記述 (定式化) に注力すればよい． ただ定式化によっては求解が難しくなるため，以下の事柄を意識するとよい．
定式化の複雑さ を意識して，問題クラスを可能な限り優しくする．
既によく研究されている典型的な定式化に寄せた記述を意識する．この典型的な定式化は「巡回セールスマン問題」「最大流問題」などのように，問題ごとに固有の名称が与えられていることが多く，問題の難易度がよく議論されている．
関連
用語集
引用書式