2020-10-12

Model Building in Mathematical Programming: 9.3 〜 9.4

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

9.3 Special ordered sets of variables

ここでは、special ordered sets type 1 (SOS1) と special oredered sets type 2 (SOS2) という特殊な変数の組について解説している。SOS

SOS1
- ちょうど1つだけ非ゼロとなるような変数の組
SOS2
- たかだか2つの変数だけが非ゼロで、その2つの変数は隣り合っていなければいけない

SOS2 は、まさに区分線形近似ででてきたもの。つまり、MIPの範囲まで広げれば、非凸な関数も区分線形近似できる。

SOSの使用例としては、施設配置問題（候補のうち1つだけが値を持つ）、Capacity Extension (容量拡張？ある量を超えると追加のコストがかかるような場合に、追加コストの状況を選択する）、非線形関数（区分線形近似）などがある。ちなみに区分線形近似は、非連続な関数に対しても使える。

9.4 Extra conditions applied to linear programming models

LPに追加の条件が課せられた場合に、MIPとして定式化できることがある。ここでは、いくつかの例を紹介している

Disjunctive constraints
- いわゆる or 条件。前述の通り、 indicator variables によって、複雑な論理条件を記述できる
Non-convex regions
- or を表現できるので、下図のような非凸な領域も表現できる。
  非凸な例
Limitting the number of variables in a solution
- 以下のような制約を課せば、正となる変数の個数に制限をつけられる
  $\displaystyle \delta _ 1 + \delta _ 2 + \dots + \delta _ n \leq k.$
Sequentially dependent decisions
- 前期の状態によって今期の判断に制限がかかるような条件は、前期の状態を表す変数と今期の判断を表す変数の組合せで表現できる
Economies of scale
- コストが上にサチるような状況では、（コストを下げたいという意味で）目的関数が非凸だが、MIPであれば区分線形近似できる
Discrete capacity extensions
- 容量が段階的に増えるような条件も、indicator variable をつかって表現できる
Maximax objectives
- minimax と違い、 maximax はLPでは表現できないが、MIPであればor条件を使って表現できる。

2020-09-16

Model Building in Mathematical Programming: 9.2

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

9.2 Logical conditions and 0–1 variables

9.1 で、 0-1変数を使って 'if - then' を表せることがわかった。本章では、それを組み合わせてより複雑な論理式を記述できることが示されている。具体的には、まず各条件に対応する indicator variable をつくっておき、それらの間に制約を入れる。具体的には以下の様になる。

論理式	indicator variables による表現
$X _ 1 \vee X _ 2$	$\delta _ 1 + \delta _ 2 \geq 1$
$X _ 1 \cdot X _ 2$	$\delta _ 1 = 1,\ \delta _ 2 = 1$
$\sim X _ 1$	$\delta _ 1 = 0$
$X _ 1 \to X _ 2$	$\delta _ 1 - \delta _ 2 \leq 0$
$X _ 1 \leftrightarrow X _ 2$	$\delta _ 1 - \delta _ 2 = 0$

ここで、それぞれの記号の意味は、

記号	意味
$\vee$	or (A or B or both)
$\cdot$	and
$\sim$	not
$\to$	implies (if ... then)
$\leftrightarrow$	if and only if

こういうのはパズルっぽいので好きなんだけど、プログラムで自動化できそうな気がするし、条件式を記述しているだけだよと solver に伝えてあげたほうが、解きやすそう（計算量を落とせそう）な気がなんとなくする。他人が indicator variable を使って記述した複雑な論理式を読み解くなんて絶対にやりたくない。論理式をそのまま取り扱ってくれる solver ってあるんだろうか。気になる。

宿題: 12.12 Logical design

NORゲート（NOR は NOT OR ですね）を用いて論理回路を設計する問題。入力と出力が与えられて、それを満たす回路を出力する。まさに論理式を記述してみよう、という問題。パズルみたいで面白かった。本当に頭の体操という感じ。

colab.research.google.com

2020-08-31

Model Building in Mathematical Programming: 9.1

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

そのまま進めると Chapter 8 ですが、どうやらお話章のようなので、そこは割愛して Chapter 9 へ。

宿題: 12.21 Agricultural pricing

政府が乳製品の価格を調整する問題。生乳の生産量が決まっている中で、ミルク（加工乳？）やチーズ、バターにどういう価格付けをするとよいか、というお話。これまでの問題と違って、内容はとてもシンプルだが、目的関数が非線形になる。各製品の単価を $x _ i$ 、需要（消費量）を $d _ i$ とおくと、収益は $\sum _ i d _ i x _ i$ となるので。

そこで、 Chapter 7 で学んだように、目的関数を区分線形な形に変形して解く。区分線形な形にするには、分離可能（separable）な形式、つまり、目的関数が単変数関数の和になるように書き直しておかなければいけない。逆に分離可能になっていれば、分割する点を指定して区分線形な形には機械的に書き直すことができる。今回は↓みたいな感じで実装した。

ただ、分割する点をどうやって決めるか、あるいは変数の上限と下限をどう設定するかについてはなにか指針が必要そうだ。実際の案件では、例えば現在の値の1.5倍までにしましょう、みたいに適当に決められそうな気がするが、教科書の問題を解くときは、他の制約式等から得られる論理的な上限を指定する必要がありそうなんだけど、論理的な上限は本当に大きくなってしまう可能性があるので、ちょっと怖い。

def linearize(
    single_variable_func: callable,
    points: List[Number],
    prefix: str='',
    x: Union[pulp.LpVariable, str]='x',
    y: Union[pulp.LpVariable, str]='y'
) -> Tuple[pulp.LpVariable, pulp.LpVariable, pulp.LpVariable, List[pulp.LpConstraint]]:
    '''
    非線形な単変数関数を区分線形近似する

    Arguments:
        single_variable_func (callable): 近似対象の単変数関数
        points (List[Number]): 分割する点
        prefix (str): 新規に作られる変数のプレフィックス
        x Union[pulp.LpVariable, str]: 変数 x（関数の入力）。文字列が与えられた場合は新たに生成する。
        y Union[pulp.LpVariable, str]: 変数 y（関数の出力）。文字列が与えられた場合は新たに生成する。

　Returns:
      x, y, weights, constraints (Tuple[pulp.LpVariable, pulp.LpVariable, pulp.LpVariable, List[pulp.LpConstraint]]): 変数x, 変数y, 各分割点の重み, 追加すべき制約式
    '''

    values = [single_variable_func(p) for p in points]
    # 分割点から最大値と最小値を求める
    min_x, max_x = min(points), max(points)
    min_y, max_y = min(values), max(values)

    if isinstance(x, str):
        x = pulp.LpVariable(f'{prefix}-x', min_x, max_x)
    if isinstance(y, str):
        y = pulp.LpVariable(f'{prefix}-y', min_y, max_y)

    # 各分割点の重み
    weights = pulp.LpVariable.matrix(f'{prefix}-w', points, 0, 1)
    constraints = [
        x == pulp.lpSum(p*w for p, w in zip(points, weights)),  # x と weights の関係
        y == pulp.lpSum(v*w for v, w in zip(values, weights)),  # y と weights の関係
        pulp.lpSum(weights) == 1  # weights の正規化 (総和が1)
    ]

    return x, y, weights, constraints

回答の Colab は以下の通り。未完成...、というかバグっていて動かない。時間見つけてデバグしないと。。

colab.research.google.com

Chapter 9 Building integer programming models I

これまではあくまで連続変数の線型計画法を扱っていたが、ここでようやく整数計画問題に入る。

9.1 The uses of discrete variables

整数変数の利用用途には主に3つある。

indivisible (discrete) quantities: そもそも整数の値が出てくるような場合に使う
decision variables: 決定変数。何らかの施策をするかしないか決めるような場合に使う
indicator variables: if-then のような条件式を表現するのに使う

例えば、 $x \geq 0$ を連続変数、 $\delta$ を 0-1 変数とした時、 $M$ を $x$ の上限として、

$x > 0 \to \delta = 1$

という条件式は、

$x - M\delta \leq 0$

と書き直せる。

この章では、特に 3. indicator variables について大きく取り上げている。というのも、 indicator variables を使いこなせるか否かが、複雑な条件を定式化できるかを決めるからだと思う。

この論理式の書き換えは非常に混乱しやすいので、以下にまとめてみる（多分あっているはず...）。前提として、 $m,\ M$ はそれぞれ $x$ の下限値と上限値。

(下限値と右辺値が曖昧になっていたため、テーブルを書き直しました。 10/12)

	if-then	formulation
1	$x > 0 \to \delta = 1$	$x - M\delta \leq 0$
2	$x \geq 0 \to \delta = 1$	$x + \epsilon - M\delta \leq 0$
3	$x\ \lt \ 0 \to \delta = 1$	$x - m\delta \geq 0$
4	$x \leq 0 \to \delta = 1$	$x + \epsilon - m\delta \geq 0$
5	$\delta = 1 \to x \geq 0$	$x - m(1 - \delta) \geq 0$
6	$\delta = 1 \to x > 0$	$x + \epsilon - m(1 - \delta) \geq 0$
7	$\delta = 1 \to x \leq 0$	$x - M(\delta - 1) \leq 0$
8	$\delta = 1 \to x\ \lt \ 0$	$x + \epsilon - M(\delta - 1) \geq 0$

ここで $\epsilon$ は十分小さい数で、制約式では等号なしの不等号を使えないために必要になる。また、上の表は、 $x$ の代わりに $\sum_{i}a _ {i}x _ {i}$ のような数式であっても成り立つ。

どうでもいいんだけど、上の式の < は全角の＜を使ってる。はてなブログで TeX の < ってどうやって書くのが正解なんだろ。エスケープできればいいだけなんだけどわからん。

TODO

12.21 の Colab をきれいに書き直して最後まで解く
宿題: 12.12 Logical design

2020-08-04

Model Building in Mathematical Programming: Chapter 7

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

Chapter 7 Non-linear models

ここでは、非線形問題をどうやって線形な問題に変形するか、関数の凸性等について学んだ

7.1 Typical applications

目的関数が線形の場合、スケールによるメリットやデメリットを表現できない。例えば、目的関数が利益だった場合、

目的関数が線形である == 生産量が少なくても多くても、1単位あたりの利益は同じ

という意味だ。現実的には、生産量が多くなるほど1単位あたりのコストが下がったり、逆にリソースの取り合いが発生してコストが上がったりする。

価格弾力性 $E _ {x}$ は以下の式で定義される

$E _ {x} = \frac{\rm 需要の変化量}{\rm 価格の変化量}$

これがある範囲で一定だと思うと、適正な価格は $p(x) = kx^{-1/E_x}$ という形となるので、目的関数には、 $p(x)x = kx^{1-1/E_x}$ のような項が入ってくることになる。

他の例だと、2つ以上の原料を混ぜ合わせて新しいものをつくる混合問題で、硬さなどの指標が必ずしも各原料の割合に比例するわけではない場合や、地理情報を入れる場合に、多項式の項が出てきたりする。

7.2 Local and global optima

ここでは、凸性の定義などを確認した。凸であることがとても大事だというお話だ。

7.3 Separable programming

ここは短いけれども結構面白かった。まず、 separable (分離可能）とは、1変数の関数の和の形であらわせる関数のこと。例えば $x ^ 2 _ 1 + 2 x _ 2$ は separable だが、 $x_1 x_2 + x_2 / (1 + x _ 1)$ は separable ではない。

separable だと、非線形な項があったとしても、該当する変数を適当に分割して、区分線形の形にして解くことができる。

区分線形の形にするのは、凸だとかんたんだけど、非凸だと途端に面倒になって、整数計画法がでてきたりするので嫌だ。

ちなみに、非線形である とか 凸である とかいう話は目的関数だけでなく、制約式の方も含んだ話のはず。

7.4 Converting a problem to a separable

$x _ 1 x _ 2$ みたいな項があったとしても、実は変数を追加することで、 separable な形に変形することができる。具体的には

$u_1 = x_1 + x_ 2 \\ u_2 = x_1 - x_2$

みたいな変数を追加して、 $x _ i$ を置き換える。この時全ての $x _ i$ を置換する必要はない (上式を成約に入れておけば十分)。変数が3つ以上に増えても、同様の方法が使える。ただし変数が多くなるので注意。

TODO

宿題: 12.21 Agricultural pricing をとく

2020-08-04

Model Building in Mathematical Programming: 6.4〜6.5

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

Chapter 6

6.4 Further investigations using a model

ここまでの解析では、

同時に1つの変数のみを動かす
動かす範囲には限度がある

という制限があったが、Parametric Programming を使うとこの制限を超えてモデルを解析できるらしい。かんたんな例だとイメージしやすい。例えば 96時間研磨の時間を増やすには、48時間分の労働が必要、といった場合には $\theta ( 96, 48 )$ みたいな方向に制約右辺を動かせば良い。

6.5 Presentation of the solutions

レポートライターなるプログラムがあるよ。

宿題 12.15 Tariff rates (power generation)

電力の需要を推定しつつ、発電量を調整する問題。 Tariff をどう訳すべきなのかがわからなかった。起動時のみかかるコストなどもあり、現実的な問題で面白かった。

colab.research.google.com

2020-07-18

Model Building in Mathematical Programming: 6.1 〜 6.3

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

Optimization Night #3 等に現をうかしていたため、2周分まとめての更新です。

Chapter 6

6.1 Validating a model

モデルの検証ちゃんとやりましょうというお話。とっても大事。モデルは大きく分けて3つある。

Infeasible models
- 実行可能解が存在しないような場合、たいてい間違っている。なぜなら、数理最適化って今人手でやっている仕事を置き換えることが多いから。いま人手でやっているのは最適とは限らないが実行可能解のはず。定式化が間違っている可能性が高い。
- ちなみに、違反している制約を列挙するのは簡単だが、その原因を見つけるのは数式からだけだととても難しい。なぜなら、infeasibleになるのは制約1つではなく制約の組み合わせに依って発生するから。
- だからこそ、制約を聞きつつ、過去データ（人手でやってきた記録）を入手しておくのがとても大事。過去データを入力してみて、違反している制約がないか確認する。
unbounded models
- 今度はいくらでも解を良くできてしまう場合。だいたいの場合、制約を追加し忘れている。
- ソルバーがある程度頑張ったところで解を出力してくれるので、その解を見ながら、抜けている制約を検討する。結構極端な値になるので、制約を見つけるのは簡単なことが多そう。
solvable models
- 最適解がえられたとしても油断してはいけない。現実的な解がえられているか見極める必要がある。
- ただ、ひとまず最適解がえられていれば、それをもとに結果がおかしくないか検証して、抜けている制約をあぶり出したりできるのでうれしい。

梅谷先生の資料のように、モデルはイテレーションを回しながら作り上げていくのだ。

6.2 Economic interpretations

ここでは具体例を通じて双対問題の解説をしつつ用語を整理している。

reduced costs: 被役費用。最適解近傍で、変数の値を微少量動かしたときに、最適解の値がどれくらいかわるか
shadow price: 制約を微少量動かしたときに、最適解がどれくらいかわるか

双対問題や双対変数に具体的な解釈を与えるのはいいが、一般性があるわけでもないので、微妙だと思うんだけどどうだろう。この章はちゃんと理解できているか微妙なので、もう一度読む。

6.3 Sensitivity analysis and the stability of a model

6.3.1 Right-hand side ranges

いわゆる感度分析。制約を動かした時、一定の範囲内であれば、 shadow price にしたがって最適値が変化する。一方、一定の範囲を超えてしまうと、それが成り立たなくなる。

なぜかといえば、下図のように有効な制約が変わるから。LPは一般的に複数の制約の交点が解になっている。制約を徐々に動かしていく（例えば図のABをA'B'に動かすイメージ）と、その制約の組が変わる（図のDやCEに到達する）ことがあって、それ以降は shadow price に従わなくなる。

f:id:ohtaman:20200718052140p:plain — shadow price が有効な範囲

6.3.2 Objective ranges

制約ではなくて目的関数にあらわれる係数をかえるとどうなるか、という話。下図でいうと、目的関数の等高線PQの傾きを変える。ただ、具体的な応用例があまりイメージできなかった。予測値とかを使っていてブレる可能性がある場合にどれくらい安定的かとか考えるときに使うのかな？

f:id:ohtaman:20200718052856p:plain

6.3.3 Ranges on interior coefficients

もちろん制約式の中の係数も変化できるけど、それほど有用ではないっぽい。ほんとかな。

6.3.4 marginal rates of substitution

制約を動かしたときに、変数がどう動くかを見るのも重要。ちょっとややこしいので、輪読会の中でもこんがらがっていたので整理。

考えるのは以下のLPで、式(6.45)の右辺 4 を少し動かしたときに、最適解の $x _ 1$ や $x _ 2$ はどう変化するか。

f:id:ohtaman:20200718055714p:plain

この問題の実行可能領域は下図の通りになっていて、式(6.45)を変化させるのは、(0,4) と A を結ぶ直線を動かすことに対応している。

f:id:ohtaman:20200718055948p:plain

最適解は A なので、 $x _ 1$ や $x _ 2$ がどう変化するかというのは、つまりA がどう動くかというはなしで、この場合は式(6.46)の表す直線（図でいうと A と (2, 1) を結ぶ直線）の上を動くことになる。具体的には、 $x _ 1$ が -1 だけ動いて $x _ 2$ が +2 動くことになる。

これは marginal rates of substitution と呼ばれる量らしい。現実問題だと、例えばある原材料の供給量が増えたり減ったりしたときに、製造計画をどう変えるべきか、という話に対応するので、とても重要。

6.3.5

結局、現実的な問題だと、最適な解よりも（状況の変化に対して）安定な解が求められることが多い。そうですよね。

TODO

宿題: 12.15

2020-07-03

機械学習系の国際会議に参加したい

機械学習系の国際会議

COVID-19 の影響でいろいろなイベントがオンライン化していています。しかもオンライン化に伴い参加費も抑えられていることが多く、いままでなかなか参加できなかった機械学習系の国際会議にも簡単に参加できるようになっているので、せっかくなのでまとめてみました。

各会議の特徴はこちらのQiita記事とかが参考になるかと思います。

Conference	Shchedule	Pricing (for non students)
ACL	JUL 5-10	$175
COLT	JUL 9 - 12	$50
ICML	JUL 12 - 18	$100
KDD	AUG 23 - 27	〜 8/14 $200 - $250 8/15〜 $250 - $300
RecSys	SEP 22 - 26
EMNLP	NOV 16 - 20
NeurIPS	DEC 5 - 12
IJCAI	JAN 2021
AAAI	FEB 2021
ICLR	MAY 4 - 8 2021
CVPR	JUN 21 - 24 2021