3.8.12. スパースなモデルの書き方

多次元の添字を使うことによる，疎なモデルの書き方をみていきます． 疎なモデルとして扱うことにより，無駄な変数や制約式が減り，より大きな問題を解くことができるようになったり， 高速化が期待できます．

まずは，簡単な輸送問題を例に考えてみましょう．

  • 倉庫 d と顧客 c が複数ある

  • 倉庫には取扱上限 upper が存在する

  • 顧客には需要量 lower が存在する

  • 輸送コスト cost がかかる

  • 総輸送コストを少なくしたい

この問題を単純に PySIMPLE で実装すると次のようになります．:

d = Element(value=uppervalue.keys())  # 倉庫
c = Element(value=lowervalue.keys())  # 顧客

# 倉庫から顧客への輸送コスト
cost = Parameter(index=(d,c), value=costvalue)
upper = Parameter(index=d, value=uppervalue)  # 倉庫取扱量上限
lower = Parameter(index=c, value=lowervalue)  # 顧客需要量下限
z = Variable(index=(d,c), lb=0)  # 倉庫から顧客への輸送量

prb = Problem()
prb += Sum(z[d,c], c) <= upper[d], '倉庫取扱量上限'
prb += Sum(z[d,c], d) >= lower[c], '顧客需要量下限'
prb += Sum(cost[d,c]*z[d,c]), '総輸送コスト'  # 目的関数
prb.solve()

ここで輸送コストは単位あたりの輸送費とし，(倉庫，顧客) ごとに決まるとします． そのため入力データ costvalue は以下のようになります．:

costvalue = {('d1', 'c1'): 30,
             ('d1', 'c2'): 20,
             ('d1', 'c3'): 9999,
             ('d1', 'c4'): 9999,
             ('d2', 'c1'): 25,
              :
}

9999 としているのは実際には輸送が発生しない経路に対するダミーの値です． 大きな値を入力しておくことで輸送が発生し辛くしています．

このように現実問題ではすべての輸送経路を考慮する必要はなく， 実際に輸送する経路はごく一部であるケースも多いでしょう． このような場合，すべての経路を用意しておくことは変数・制約式の数を無駄に増やしてしまうため， 大きな問題が解けなかったり，速度が遅くなってしまいます．

そこで必要最小限の経路のみを定義することにより効率的なモデルを記述することができます． PySIMPLE では倉庫から顧客への二次元の添字 dc を用いることで疎なモデルを表現することができます．:

# 倉庫と顧客の疎な添字
dc = Element(value=costvalue.keys())

# 倉庫から顧客への輸送コスト
cost = Parameter(index=dc, value=costvalue)
upper = Parameter(index=dc(0), value=uppervalue)  # 倉庫取扱量上限
lower = Parameter(index=dc(1), value=lowervalue)  # 顧客需要量下限
z = Variable(index=dc, lb=0)  # 倉庫から顧客への輸送量

prb = Problem()
prb += Sum(z[dc], dc(1)) <= upper[dc(0)], '倉庫取扱量上限'
prb += Sum(z[dc], dc(0)) >= lower[dc(1)], '顧客需要量下限'
prb += Sum(cost[dc]*z[dc]), '総輸送コスト'  # 目的関数
prb.solve()

添字 (d,c) の代わりに dc を用いることで経路のある部分だけを表現することができました． 倉庫 d や顧客 c の一方のみを指定したい場合は dc(0)，dc(1) と記述します． 次元は 0 始まりであることに注意しましょう． また，costavalue は必要部分だけ記述すればよいので次のようになります．:

costvalue = {('d1', 'c1'): 30,
             ('d1', 'c2'): 20,
             ('d2', 'c1'): 25,
              :
}

輸送のありえる経路が全ての組合せの 20% だった場合，変数の 8 割が削減されたことになります．

疎なモデルを用いて効率的なモデルを記述する方法は特にネットワーク系の問題で威力を発揮します． 他にも例えばスケジューリング問題では考慮する必要のないマスをあらかじめ除いておくこともできます．