最適化におけるスパース性を考慮したモデリングについて

最適化モデルを作成するときに、スパースな定式化を意識することにより、モデリングや前処理にかかる時間やメモリ使用量を大幅に改善できる場合がある。

これは、例えば、疎グラフにおいては、隣接行列でデータを持つよりも隣接リストなどでデータを持った方がオーダーレベルで時間やメモリ使用量が改善するのと同様である。
特に整数計画問題などとしてモデリングする場合は、変数の作成やメモリ確保の点で定数倍が大きいため、時には絶大な効果を発揮する。さらに、モデリングの仕方によっては宣言する必要のある制約が減少する可能性もあるため、モデリングや前処理がボトルネックとなっているような場合は、真っ先に検討する必要がある部分だと考える。

以下、gurobipyとpandasを例に、簡単な例を挙げてみる。

例えば、3頂点のグラフに対して、次のようなDataFrameで隣接行列が与えられている場合を考える。

import pandas as pd
df = pd.DataFrame([[0, 1, 1], [1, 0, 0], [0, 1, 0]])
print(df)
# 出力結果
#    0  1  2
# 0  0  1  1
# 1  1  0  0
# 2  0  1  0

このようなグラフ上に変数を定義したい場合に、変数で定義し、後からその変数を0で固定するというのが密な定式化である。

from itertools import product
import gurobipy as gp

model = gp.Model()
V = df.index
x = model.addVars(product(V, V), vtype="C", name="x")

for i, j in product(V, V):
    # 辺がない場合は0
    if df.loc[i, j] < 0.5:
        model.addConstr(x[i, j] == 0)

このような定式化は、変数の数がグラフのスパース性にかかわらずとなるため、基本的に避けるべきであり、変数を上に定義するべきである。
例えば次のようにstackメソッドを用いることで、をMultiIndexとして取り出すことができる。

ser = df.stack()
E = ser[ser > 0.5].index
print(E)
# 出力結果
# MultiIndex([(0, 1),
#             (0, 2),
#             (1, 0),
#             (2, 1)],
#            )

x = model.addVars(E, vtype="C", name="x")

さらに、gurobipy-pandasを使用すれば、変数の線形結合などを求めたいときに、pandasの集計関数を使えるようになり、便利になる。

import gurobipy_pandas as gppd

x = gppd.add_vars(model, E, name="x", vtype="C")
model.update()
print(x)
# 出力結果
# 0  1    <gurobi.Var x[0,1]>
#    2    <gurobi.Var x[0,2]>
# 1  0    <gurobi.Var x[1,0]>
# 2  1    <gurobi.Var x[2,1]>
# Name: x, dtype: object