実際の最適化問題を瞬時に解くためのトレーニング

最近,実際の最適化問題に挑戦する若手(?)の研究者が増えてきたようだ.嬉しいことだが,普段からトレーニングしていないので,結構時間がかかってしまったり,モデル化がうまくいかなかったりしてトラブルことも,ままあるようだ.

モデル化の部分はアートであるが,トレーニングはできるので,その方法を書いておこう.

練習用の問題としてはベンチマーク問題があるものがよい.たとえば,OR-Lib http://people.brunel.ac.uk/~mastjjb/jeb/info.html やその類似品 http://www.di.unipi.it/optimize/ORGroup.html から適当な問題を選んでくる.

そこには実験結果を含んだ過去の論文が掲載されているので,googleで検索して論文を読む.定式化があれば,Gurobi/Pythonで書いてみて一番小さい問題例を解いてみる.

データはテキストファイルで書いてあることが多いので,読み込むにはPythonのテクが必要だ.そのまま読むと数値にならず文字列になるので,整数に変換したり,データ数が記述されているところから数値を切り出したりする必要がある.

crew schedulingの例題を読むには以下のようにする.

from collections import OrderedDict, defaultdict
fname = "csp50.txt"
f = open(fname,"r")
lines = f.readlines()
n_tasks, time_limit = map(int, lines[0].split())
print(n_tasks, time_limit)

start, finish = OrderedDict(),OrderedDict()
for t in range(1,n_tasks+1):
   start[t], finish[t] = map(int, lines[t].split())

map関数で文字列を整数化している.保管するのは辞書が良いが順序をキープしたいときには,OrderedDictを使う.既定値を指定したい補助データはdefaultdictを使えばよい.別の例題(シフト最適化の問題 )だが,作業員ができる仕事の「集合」を作業員ごとに保持するデータ構造は,空の集合(set)を既定値にした辞書(キーは作業員番号)が良い.

Jobs = defaultdict(set)
for w in range(n_workers):
   line = lines[6 + n_jobs + w].split()
   for j in line[1:]:
       Jobs[w].add(int(j))

この問題で元論文をみると極大クリークの列挙が必要にある.こういうときには,networkxを使えば簡単だ.


import networkx as nx
Cliques = []
for c in nx.find_cliques(G):
   Cliques.append( set(c) )

最適化のコードはこんな感じで,昔の論文

Algorithms for Large Scale Shift Minimisation Personnel Task Scheduling Problems M. Krishnamoorthya,, A. T. Ernstb,, D. Baatarc,

だと専用解法が必要だったものが(大きくなければ)瞬時に解ける.

from gurobipy import Model, quicksum, GRB
model = Model()
x, y ={},{}
for w in range(n_workers):
   y[w] = model.addVar(vtype="B", name=f"y[{w}]")
   for j in Jobs[w]:
       x[j,w] = model.addVar(vtype="B",name=f"x[{j}.{w}]")
model.update()
for j in range(n_jobs):
   model.addConstr( quicksum( x[j,w] for w in range(n_workers) if (j,w) in x ) == 1, name=f"job_assign[{j}]")    
for w in range(n_workers):
   for j,c in enumerate(Cliques):
       model.addConstr(  quicksum(x[j,w] for j in Jobs[w].intersection(c)) <= y[w], name=f"connection[{j},{w}]" )
model.setObjective(quicksum( y[w] for w in range(n_workers) ) ,GRB.MINIMIZE)
#model.write("shift.lp")
model.optimize()

どのくらいの規模の問題例だとどのくらい時間がかかるかを体感しておくことも重要だ.似た問題に対する経験があれば,問題とその規模を聞いたときにソルバーを使えばどのくらいで解けるかを瞬時に答えることができる.






この記事が気に入ったらサポートをしてみませんか?