Solver for COnstraint Programming:スコープ Pythonモジュールの使い方 制約計画ソルバー SCOP Solver for COnstraint Programming:スコープ Pythonモジュールの使い方
SCOP.pyモジュールとは 制約計画ソルバーSCOPを,超高級言語Pythonから直接呼び出して,求解するためのモジュール
Pythonモジュールのクラス 問題クラス Problem 制約クラス (Constraint) 線形制約クラス Linear 2次制約クラス Quadratic 相異制約クラス Alldiff
問題クラス Problem(1) オブジェクト生成の例(pという問題例を生成) p=Problem() メソッド addVariable(変数名 =文字列,領域=リスト) 変数を1つ問題に追加する. addVariables(変数のリスト,領域=リスト) リストに含まれる変数(複数)を一度に問題に追加する. 例:p.addVariable(“Worker A”, [“Do Job1”,”Do Job2” ]) (作業員AはJob1かJob2を行う.) 例: p.addVariables([“A”, “B”], [“Do Job1”,”Do Job2” ]) (作業員 A,B は Job1かJob2を行う.)
問題クラス Problem(2) メソッド addConstriant(制約オブジェクト) 制約オブジェクトを問題に追加する. setTarget(目標値=整数:規定値0) ペナルティ逸脱量の合計が,ここで指定した目標値以下になったら探索が終了する. solve(time=制限時間:規定値600,seed=乱数の種:規定値1): 求解する.返値は,解(変数名をキー,値を領域から選ばれた値とした辞書)と逸脱した制約(制約名をキー,逸脱量を値とした辞書)のタプル
問題クラス Problem(3) Problemクラスは,文字列を返すメソッドが定義されている. print 問題のオブジェクト 変数の数,制約の数,制約の情報を画面上に出力する.
線形制約クラス オブジェクト生成 Linear(制約名=文字列,weight=1:既定値) 例:con1=Linear(“L1”,100) メソッド addTerm(係数=整数,変数名 =文字列,値=数値,文字列) 左辺の項を1つ制約に追加する. setRhs(右辺定数=整数) 線形制約の右辺定数を設定する.規定値は0 setDirection(制約の向き = ”<=“,”>=“,”=“のいずれか) 制約の向きを設定する.規定値は”<=“ setWeight(重み=正数もしくは”inf”) 制約の重みを設定する.”inf”は無限大(絶対制約)を示す.
2次制約クラス オブジェクト生成 Quadratic(制約名=文字列,weight=1:既定値) 例:con1=Quadratic(“Q1”,10) メソッド addTerm(係数,変数名1,値1,変数名2,値2) 左辺の2次の項を1つ制約に追加する. setRhs(右辺定数=整数) 線形制約の右辺定数を設定する.規定値は0 setDirection(制約の向き = ”<=“,”>=“,”=“のいずれか) 制約の向きを設定する.規定値は ”<=“ setWeight(重み=正数もしくは”inf”) 制約の重みを設定する.”inf”は無限大(絶対制約)を示す.
相異制約クラス オブジェクト生成 Alldiff(制約名=文字列,変数名のリスト:規定値は空のリスト,重み=1:既定値) 例:con1=Alldiff(“all_diff”,[“A”,”B”,”C”],”inf”) メソッド addVariable(変数名 =文字列) 相異制約の変数を1つ制約に追加する. addVariables(変数名リスト =文字列のリスト) 相異制約の変数を複数同時に追加する. setWeight(重み=正数もしくは”inf”) 制約の重みを設定する.”inf”は無限大(絶対制約)を示す.
仕事の割当の例 割当はAlldiff制約,費用は線形制約 3人の作業員 A,B,C を3つの仕事 0,1,2 に割り当てる. 割当費用= 1 1 2 A 15 20 30 B 7 12 C 25 10 13 割当はAlldiff制約,費用は線形制約
import scop scopモジュールを読み込む p=scop.Problem() 問題オブジェクトpを生成 workers=["A","B","C"] Cost=[[15, 20, 30],[7, 15, 12],[25,10,13]] 変数の追加 p.addVariables(workers,range(3)) 相異制約オブジェクトcon1の生成 con1=scop.Alldiff("all_diff_constraint",workers,weight=”inf”) 線形制約オブジェクトcon2の生成 con2=scop.Linear("linear_constraint")
for i in range(len(workers)): for j in range(3): 線形制約に左辺の項を追加 con2.addTerm(Cost[i][j],workers[i],j) con2.setRhs(0) 右辺定数の設定 con2.setDirection(“<=”) 制約の方向の決定 相異制約を問題に追加 p.addConstraint(con1) 線形制約を問題に追加 p.addConstraint(con2) 求解(時間制限3秒) sol,violated=p.solve(time=3)
実行結果 print "solution“ for x in sol: 結果(解)の辞書を表示 print x,sol[x] print "violated constraint(s)" for v in violated:結果(破られた制約)の辞書を表示 print v,violated[v] 実行結果 solution 解の表示 A 0 C 1 B 2 violated constraint(s) 逸脱した制約の表示 linear_constraint 37
問題情報の出力 print p とすると... number of variables = 3 number of constraints= 2 variable A:[0, 1, 2] variable B:[0, 1, 2] variable C:[0, 1, 2] Alldiff: all_diff_constraint: weight=inf A C B Linear: linear_constraint: weight=1 15*x[A:0] 20*x[A:1] 30*x[A:2] 7*x[B:0] 15*x[B:1] 12*x[B:2] 25*x[C:0] 10*x[C:1] 13*x[C:2] <=0
仕事の割当の例(2) 5人の作業員 A,B,C,D,E を3つの仕事 0,1,2 に割り当てる. 仕事の必要人数=(1,2,2)人 割当費用= 1 2 A 15 20 30 B 7 12 C 25 10 13 D 18 3 E 5 17
import scop p=scop.Problem() workers=["A","B","C","D","E"] Cost=[[15, 20, 30],[7, 15, 12],[25,10,13],[15,18,3],[5,12,17]] LB=[1,2,2] p.addVariables(workers,range(3)) LB_Constraint={} for j in range(3): LB_Constraint[j]=scop.Linear("LB_constraint"+str(j),"inf") for i in range(len(workers)): LB_Constraint[j].addTerm(1,workers[i],j) LB_Constraint[j].setRhs(LB[j]) LB_Constraint[j].setDirection(">=") p.addConstraint(LB_Constraint[j])
con1=scop.Linear("linear_constraint") for i in range(len(workers)): for j in range(3): con1.addTerm(Cost[i][j],workers[i],j) p.addConstraint(con1) sol,violated=p.solve(time=1) print "solution" for x in sol: print x,sol[x] print "violated constraint(s)" for v in violated: print v,violated[v]
SCOPによる求解 20 12 10 3 5 solution A 1 C 1 B 2 E 0 D 2 violated constraint(s) linear_constraint 50 1 2 A 15 20 30 B 7 12 C 25 10 13 D 18 3 E 5 17 50 (=20+12+10+3+5) 万円
仕事の割当の例(3) 5人の作業員 A,B,C,D,E を3つの仕事 0,1,2 に割り当,必要人数は(1,2,2)人(前の例と同じ) 作業員AとCは仲が悪いので,異なる仕事に割り振る 割当費用= 1 2 A 15 20 30 B 7 12 C 25 10 13 D 18 3 E 5 17
作業員A,Cが同じ仕事をしない 制約の記述 作業員 A とCを同じ仕事に割り当てることを禁止する2次制約 (重みは 100) con2=scop.Quadratic("quadratic_constraint",100) for j in range(3): con2.addTerm(1,"A",j,"C",j) p.addConstraint(con2)
SCOPによる求解 15 12 10 3 solution A 0 C 1 B 2 E 1 D 2 violated constraint(s) linear_constraint 52 1 2 A 15 20 30 B 7 12 C 25 10 13 D 18 3 E 5 17 52 (=15+12+10+3+12) 万円
スタッフスケジューリング 1 シフトは8 時間,3 シフトの交代制 4 人のスタッフは,1 日の高々1 つのシフトしか行うことができない. 繰り返し行われる1 週間のスケジュールの中で,スタッフは最低5 日間は勤務しなければならない. 各シフトに割り当てられるスタッフの数は,ちょうど1 人でなければならない. 異なるシフトを翌日に行ってはいけない.(異なるシフトに移るときには,必ず休日を入れる.) シフト2, 3 は,少なくとも2 日間は連続で行わなければならない. この例題はカーネギーメロン大のJohn Hooker の2009 年の講演の例を改訂したものである
変数の追加 import scop #scopをインポート p=scop.Problem() #pと言う問題例オブジェクトを作成 periods=range(7) #期間は7日間(曜日) shifts=range(4) #3種類のシフト1, 2, 3と休みを表す0 staffs=["A","B","C","D"] #4人のスタッフ variables=[] #変数を入れるためのリスト for i in staffs: for t in periods: variables.append(i+str(t)) #変数にスタッフ i と曜日 p.addVariables(variables,shifts) #問題例pに変数,シフト追加
スタッフに関する制約追加 繰り返し行われる1 週間のスケジュールの中で, スタッフは最低5日間は勤務しなければならない. 最低5日間 繰り返し行われる1 週間のスケジュールの中で, スタッフは最低5日間は勤務しなければならない. LB={} #スタッフ制約オブジェクトを入れるための辞書作成 for i in staffs: #スタッフに関する制約を線形制約として追加 LB[i]=scop.Linear(“LB ”+i) for t in periods: for s in shifts[1:]: LB[i].addTerm(1,i+str(t),s) #線形制約左辺追加 LB[i].setRhs(5) #線形制約に右辺追加 LB[i].setDirection(">=") #線形制約の制約向き追加 p.addConstraint(LB[i]) #制約オブジェクトを問題例に追加 #制約の名前,重み(規定値=1)追加 最低5日間
シフトに関する制約追加 各シフトに割り当てられるスタッフの数は, ちょうど1 人でなければならない 各シフトに割り当てられるスタッフの数は, ちょうど1 人でなければならない UB={} #シフト制約オブジェクトを入れるための辞書作成 for t in periods: #スタッフに関する制約を線形制約として追加 for s in shifts[1:]: UB[(t,s)]=scop.Linear("UB"+str(t)+str(s)) #制約の名前,重み(規定値=1)追加 for i in staffs: UB[(t,s)].addTerm(1,i+str(t),s) #線形制約左辺追加 UB[(t,s)].setRhs(1) #線形制約右辺追加 UB[(t,s)].setDirection("<=")#線形制約の制約向き追加 p.addConstraint(UB[(t,s)]) #制約を問題例に追加
シフトに関する禁止制約追加(1) 異なるシフトを翌日に行ってはいけない. Forbid={} #禁止制約オブジェクトを入れるための辞書作成 for i in staffs: #禁止制約を線形制約として追加 for t in periods: for s in shifts[1:]: Forbid[(i,t,s)]=scop.Linear("Forbid"+i+str(t)+str(s)) Forbid[(i,t,s)].addTerm(1,i+str(t),s) #先行のシフトを右辺に追加 for k in shifts[1:]: #後続(翌日)のシフトを右辺に追加 if k!=s: #先行と後続(翌日)シフトが異なる時のみ追加 if t==periods[-1]: #先行シフトが一番最後の期に行われた時 Forbid[(i,t,s)].addTerm(1,i+str(0),k) #後続シフトは一番最初の期 else: #それ以外の時はt+1期に後のシフトを行う Forbid[(i,t,s)].addTerm(1,i+str(t+1),k) Forbid[(i,t,s)].setRhs(1) #線形制約右辺追加 Forbid[(i,t,s)].setDirection("<=") #線形制約の制約向き追加 p.addConstraint(Forbid[(i,t,s)]) #制約を問題例に追加 #制約の名前,重み(規定値=1)追加
シフトに関する禁止制約追加(2) x[Aのt-1,s]+x[Aのt+1,s]>=x[Aのt,s] シフト2, 3 は,少なくとも2日間は連続で行わなければならない Cons={} for i in staffs: for t in periods: for s in shifts[2:]: #シフト2と3に対して Cons[(i,t)]=scop.Linear("Cons"+i+str(t)) Cons[(i,t)].addTerm(-1,i+str(t),s) #1日目のシフトを右辺に追加 if t==0: #一番最初の期の時,先行シフトは一番最後の期で行われる Cons[(i,t)].addTerm(1,i+str(periods[-1]),s) else: #それ以外の時,先行シフトはt-1期で行われる Cons[(i,t)].addTerm(1,i+str(t-1),s) if t==periods[-1]: #一番最後の期の時,後続シフトは Cons[(i,t)].addTerm(1,i+str(0),s) #一番最後の期で行われる else: #それ以外の時,後続シフトはt+1期で行われる Cons[(i,t)].addTerm(1,i+str(t+1),s) Cons[(i,t)].setRhs(0) Cons[(i,t)].setDirection(">=") p.addConstraint(Cons[(i,t)]) x[Aのt-1,s]+x[Aのt+1,s]>=x[Aのt,s] 2日目シフト 3日目シフト
結果の出力 sol,violated=p.solve(time=1) print "solution" for x in sol: # 結果(解)の出力 sol,violated=p.solve(time=1) print "solution" for x in sol: print x,sol[x] # 結果(破られた制約)の出力 print "violated constraint(s)" for v in violated: print v,violated[v]
結果の出力 A1 3 A0 0 A3 3 A2 3 A5 2 A4 0 A6 2 B4 1 B5 0 B6 3 B0 3 B1 0 B2 1 B3 1 C3 0 C2 2 C1 2 C0 2 C6 0 C5 3 C4 3 D6 1 D4 2 D5 0 D2 0 D3 2 D0 1 D1 1 violated constraint(s) スタッフA スタッフB スタッフC スタッフD シフト 1 2 3 期