Model Building in Mathematical Programming: Chapter 1, Chapter 2

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

Chapter 1

1.1 The concept of a model

ここでは「モデル」という言葉のコンセプトについて議論。数理最適化もしくはオペレーションズ・リサーチの文脈では抽象的な数理モデルを指すことが多い。機械学習や物理学の文脈でも「モデル」という言葉がでてきて、それぞれなんとなくイメージしている抽象度が違いそうなので、コミュニケーションの際には注意が必要そう。京都大学のページにもあるとおり、数理最適化は

問題のポイントを整理して数学モデルを作成する．
モデルの特性を考慮した適切な方法（アルゴリズム）を用いて解を求める．
得られた解をもとに現実の問題の解決策を実施する．

というステップを踏むことになるので、「モデル」のコンセプトを理解して「アルゴリズム」と区別するのはとても大事。

あまり本筋とは関係ないですが、本書ではオペレーションズ・リサーチのことを operations research ではなく operational research と書いてあります。 Wikipedia によると、 operational research はイギリス英語らしい。

Chapter 2

2.1 Algorithms and packages

既存のパッケージ（Gurobiなどのソルバー）は長年の研究の成果を泥臭く実装していて、素人に手を出せるようなものではないので、むやみにアルゴリズムを実装したりせず、既存のパッケージを利用しましょう。昔 cbc (Coin-or branch and cut) という数理最適化ソルバーのコードを読み解こうとしたのを思い出しました。

既存のパッケージの多くは、以下のような典型的な制約を簡単に記述する機能が備わっていて、そういった機能を使うと効率的に計算してくれることがあるので、できるだけ使ったほうが良さそうです。（最近のパッケージでは自動的に判定して効率的な計算をしてくれるものもあるようです。）

Simple bounding constraints:
- $L \leq x \leq U$
Ranged constraints:
- $\sum a_j x_j \leq b1, \sum a_j x_j \geq b2$
Generalized upper bounding constraints:
- $x_1 + x_2 + \cdots + x_n \leq M$

あとは適切な初期解を与えるのも計算時間の短縮に効果的。また、Sensitivity Analysis (感度分析) についてもふれていて、少し議論ができて楽しかったです。

2.2 Practical considerations

既存のパッケージには、計算結果（途中結果を含む）を保存する機能がついていることが多いので、それを活用しましょう。数値を少しだけ変えた問題を解く際に初期値として使うこともできるし、計算リソース等の関係で、途中で計算をやめて再開したいケースもある。コメントもあったけど、このあたりは機械学習周りと感覚が似ている。（というか機械学習がそもそも数理最適化問題の一種なので当然といえば当然かも）

2.4 Constraint programming

ここでは CP (Constraint programming) と IP (Integer Programming)との関係についても触れています。個人的に CP に興味があるけど全く触ったことがなかったし、イメージもよくわからなかったので、とても助かった。 CPとIPは、もともと別の文脈で発展していて、コミュニティも別だったりするけど、同じ問題を解けたり解けなかったりするので面白い。CPの方が少ない実行可能解を見つけるのは得意だが、巡回セールスマン問題のような大量の実行可能解から最適なものを見つけるのは苦手なんだそうです。また、CPでは、以下のようなglobalな制約を記述できるので、見通しが良くなりそう。(IPとして記述できるけど、変数が増えたり定式化が複雑になったりして大変そう)

${\rm all\_different}(x_1, x_2, \dots, x_n)$
- $x _ i$ がすべて違う値
$\neq$
- 普遍と左辺が異なる値
${\rm card_m}(x_1, x_2,\dots,x_n|v)$
- cardinality. ちょうど $m$ 個の値が $v$
${\rm cumulative}((t_1, t_2,\dots,t_n), (D_1, D_2,\dots,D_n), (C_1,C_2,\dots,C_n), C)$
- 時刻 $t_i$ にスタートして $D_i$ の時間と $C_i$ のリソースを消費するジョブが $n$ 個あった時に、利用リソースが常に $C$ を超えない
${\rm circuit}(x_1,x_2,\dots,x_n)$
- $(x_1,x_2,\dots,x_n)$ が順列になっている
${\rm element}(j, (x_1, x_2,\dots,x_n), z)$
- $z$ が $(x_1, x_2,\dots,x_n)$ の $j$ 番目の要素と等しい
$(x_1, x_2,\dots,x_n) >_{lex} (y_1, y_2,\dots,y_n)$
- 集合同士の大小関係 (ある $r \leq n$ があって、 $x _ 1 = y _ 1,\dots,x _ {r-1} = y _ {r-1},x _ r>y _ r$ の場合に true)

TODO

12.1 Food manufacture 1 を解く
2.1 に出てくる REDUCE, PRESOLVE, ANALYSE がそれぞれ何を指しているのか確認する