何て名前だっけ?

「この最適化モデルはどんな方法で解いているのですか?」 先日、お客さまに聞かれました。

ええと普通の LP (線形計画問題) に 0-1 整数変数が入った MILP (線形な混合整数計画法)だから 分枝限定法? でもそれは解法フレームワークの名前に過ぎない。 線形性を利用して緩和問題を解くのは単体法であることも言わなければ、正確じゃない。 でも緩和問題と単体法の説明をしている場合じゃないし..と迷ったあげく、

「標準的な MIP 解法で解いてます。」

と何の情報量もない返答をしてしまいました。「あとは Web で」みたいに、 話し言葉にも適当なリンクが付けられればよいのですが。 もっと言うと昨今の混合整数計画法ソルバーは、 実行可能解を求めるのに各種ヒューリスティック解法まで取り込んでますので 「何々法に基いています」というのがますます難しくなってきています。

最近読んだ本に、病院の診療科は医者側の理屈で分類されたもので ユーザーである患者の立場に立っていない、と分類体系をまるごと見直し、 例えば外科と内科の区別を取り払って成功した話が引かれていましたが、 最適化の世界も全く同じですよね。 ばくっと「凸計画できます!」とか言われて、実務家の方がこれは役に立ちそうだ、と思えるわけはない。 では「生産計画」、「設備計画」、「スケジューリング」、「配車計画」といった名前はどうかというと、 ユーザーの意図の大枠をなぞっただけで絞り込めておらず、今度は解く側サイドが困ってしまいます。

いわゆるソフトウエアの「デザインパターン」と同じ発想なのですが、 問題を持ち込む人、数理最適化モデルを作る人、解く人の間で、ある程度難しさのイメージが共有できる 良い分類や名前はないかなあと、考え始めました。 出してみたのが次です。

• 重ねあわせ
• 保存
• マス目埋め
• 対応付け

他にもあると思いますが、実務で良く現れるのに限って絞りました。 「保存」の代表選手は最小費用流とロットサイジング。 「マス目埋め」はシフトスケジューリング。「対応付け」はレコメンド問題。 ダイエット問題からポートフォリオ最適化問題に至るまで、その他大勢は「重ねあわせ」。 それぞれのタイプに応じて、式ではなくてシンボリックな図や絵を対応付けることができるので、 当事者同士の会話が促進されます（たぶん）。 同じスケジューリング問題でも、シフトスケジューリングは「マス目埋め」だけど、 いわゆるレイバースケジューリングは「重ねあわせ」だからかなり違う、とか 列生成法は大抵の問題を「重ねあわせ」と「対応付け」に帰着してしまう手法だ、とか いわゆる MILP の再定式化で「保存」を「重ね合わせ」に帰着すると、 サイズはでかくなるが、解き易くなる、とか、最適化問題を解く側のノウハウも 蓄積できるのではないかなと思っています。

肝心の「絵」や「図」はどうした？ すみません。続きはまたこのブログで。