0-8

Model Building in Mathematical Programming: 3.2.4〜3.5

数理最適化

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

Chapter 3

3.2 Defining objectives （続き）

引き続き、目的関数について語る。

3.2.4 Ratio objectives

パフォーマンスや効率を評価するときに出てくる以下のような目的関数は、線型に書き直すことができる。DEA（包絡分析）ですね。

\frac{\sum_{j}a_jx_j}{\sum_j b_j x_j}

3.2.5 Non-existent and non-optimizable objectives

制約を満たす解がほしいだけで、最適解である必要がない場合は、目的関数なし、なんていうのもある。最近のソルバーは、目的関数なしでも動くらしい。制約を満たす「極端な」解を得ることもできるので、デバッグに有用という話は面白かった。

3.3 Defining constraints

これ以降は制約の話。各章の抽象度があっていない気がした。

  1. Productive capacity constraints
    • 生産能力に関する制約
  2. Raw material availabilities
    • 原材料の利用可能性に関する制約
  3. Marketing demands and limitations
    • 生産量に関する、需要やその他の要請から生まれる制約
  4. Material balance (continuity) constraints
    • 質量保存などの制約
  5. Quality stipulation
    • 原材料を混合する際の混合割合など、品質規定などから要求される制約

3.3.6 Hard and soft constraints

制約は実際には必ずしも制約ではない。そこで、絶対に満たさないといけない制約をHardな制約、満たさないといけないけど、場合によっては満たさなくても...みたいなものはSoftな制約と呼ぶ。 制約とはいったい。。数理最適化って、こういう学問的というよりは現実問題に目を向けているあたりが好きだったりもする。

違反量を表す変数を導入して、目的関数でペナルティをかけるのが単純な方法だが、ファジー最適化といった手法もある。そしてファジー最適化は定式化を変えることでLP問題に帰着できる。ふむふむ。

3.3.7 Chance constraints

ある一定の確率以上で制約を満たしなさい、という制約。手元の本では機会制約と訳してあった。確率的最適化手法の一種。

3.3.8 Conflicting constraints

制約同士が矛盾してしまう場合に、「できるだけ制約を満たす解を探せ」という問題になることもあって、それは Goal Programming と呼ばれている。

目的関数をどうやって設定するかというと、2種類の方法があって、後者は多少複雑だが、LPで定式化できる。

  1. 違反量の重み付き総和を最小にする
  2. 最大の違反量を最小にする

3.3.9 Redundant constraints

潜在価格 (shadow price) は、制約を少し緩めたときの、最適解への影響具合。潜在価格がゼロな制約は、最適解に影響を与えないため冗長と言える。でもデータが変わったりして冗長でなくなることもあるし、安易に取り除いてはだめ。

3.3.10 Simple and generalized upper bounds

変数の上下限や、Generalized upper bounds は、ソルバにとって有用なので、それを定義するメソッドがある場合は使ったほうが良さげ。

3.4 How to build a good model

  1. 理解しやすい定式化をしよう
    • 前回も出てきたが、補助的な変数をつかっても計算量的にはそこまで問題にならない
      • 最近のソルバは解釈性を解析してレポートしてくれる機能もあるもよう
    • わかりやすい変数名をつけよう
  2. エラーを検出しやすいように記述しよう
    • Typoとか定式化の間違い。大概の場合PRESOLVEするとunboundedとかinfeasibleになるので検出できる（ほんまかいな）
    • 数理最適化問題の、エラーにハマりにくい書き方どこかにまとまってないかな。
  3. Modal formulation というテクニックがあるが、あまり使われていない模様。なので僕は調べない。
  4. 変数の単位を揃えよう

3.5 The use of modeling language

古い本だからね〜、当時は確かにいろいろ問題があったから、modeling language をおすすめしたのはわかるけど、今は pulp かければいいんじゃない？的な話になった。

TODO

  1. 宿題（12.22 Efficiency analysis）を解く
  2. Chapter 4 を読む
    • 担当自分だ。間に合う気がしない。