数理計画法

数理計画法#

  • 読み: すうりけいかくほう

  • 英名:

一定のルール(決めごと)の範囲内においてできるだけ良いやり方を,数理モデルと計算機の力を借りて導く手法.配送場所が決まっているとき,できるだけ手際のよい運び方を求める(配送計画),必要なエネルギーをできるだけ低コスト・低環境負荷で生産するための機器の運転方法を求める(運転計画),職場の制約を満たし,皆ができるだけ納得する勤務表を求める(シフトスケジューリング),工作機械やマンパワーの制約の下,リードタイム最小のスケジュールを立てる(プロジェクトスケジューリング),過不足のない営業拠点数と配置を求める(施設配置問題),長さの決まっている材料から無駄のない製品の切り出し方を求める(カッティングストック問題)など,実務界のほぼあらゆる場所において適用事例が存在する.「できるだけ何々である解を求める」という部分をクローズアップして「(数理)最適化」とも呼ばれる.ただ,シフトスケジューリングなど,応用例によっては「最適」の意味が数学的に定まらない場合も多く,「最適」の尺度を変化させると多種多様な解が出力されるので「最適化」を決して「コスト削減のみを意図する手法」といった排他的な意味に捉えるべきではない.

数理計画法における計算機の利用方法は特徴的である.個別の問題に特化したソフトウエアをその都度開発するのではなく,問題を数式表現(数理モデル)に帰着させて,汎用ソフトウエア(最適化ソルバー)によって解を求める.その場合,導こうとしている「やり方」は変数,「ルール」はそれら変数を用いた等式・不等式群(総称して制約式)で表現される.どんなやり方が良いかは「目的関数」とよばれる関数を一つ定義して,この値の大小で表現する.最適化ソルバーはこのように数式で表現された問題を解くためのアルゴリズム(計算手順)を計算機上に実装したソフトウエアであり,数理モデルを入力して答え(変数の値)を出力する.問題を数式で表現して汎用ソルバーを使うという方法は一見迂遠に見えるが,問題の記述と解き方を分離し,汎用化した問題の解法に帰着することによって,扱おうとしている問題の難易度を的確に見積もって「標準化」された方法を選択することに他ならない.過去50年以上にわたる研究成果の積み上げが最適化ソルバーを通じて低コストで享受できる,難しい問題に複数の最適化ソルバー(アルゴリズム)でアタックを試みることができる,といったメリットは大きい.

ただ,実務の問題を汎用的な数理モデルに変換するプロセスは容易に想像できるように数理計画法の応用における最大の障壁となっている.この障壁も問題を数式に近い形で表現するためのモデリング言語などの支援ツールや適用事例の積み上げによって解消されつつあるものの,「問題の数式表現が一意ではない」・「数理モデルで表現できることとソルバーで解けることは等価ではない」・「問題によっては厳密解法が存在しない」など,この分野特有の事情が実務家の行く手を阻む場合もある.アルゴリズム研究はアカデミックな関心から研究事例が多いが, Nuorium Optimizer のような商用の汎用ソルバーの実装事例とそれを支える実務への応用はまだ十分であるとは言えない.マルチコア CPU の普及,洗練された分枝限定法,メタヒューリスティクスなど,近年の計算機環境やアルゴリズムのブレークスルーによって広がった可能性を生かすべく,実務家と研究者のより盛んな連携が望まれる.