0-8

Model Building in Mathematical Programming: 9.1

Optimization NightH. 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つある。

  1. indivisible (discrete) quantities: そもそも整数の値が出てくるような場合に使う
  2. decision variables: 決定変数。何らかの施策をするかしないか決めるような場合に使う
  3. 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