Solver for COnstraint Programming：スコープ Pythonモジュールの使い方

Presentation on theme: "Solver for COnstraint Programming：スコープ Pythonモジュールの使い方"— Presentation transcript:

1 Solver for COnstraint Programming：スコープ Pythonモジュールの使い方
制約計画ソルバー SCOP　 Solver for COnstraint Programming：スコープ Pythonモジュールの使い方

2 SCOP.pyモジュールとは 制約計画ソルバーSCOPを，超高級言語Pythonから直接呼び出して，求解するためのモジュール

3 Pythonモジュールのクラス 問題クラス Problem 制約クラス (Constraint) 線形制約クラス Linear
2次制約クラス Quadratic 相異制約クラス Alldiff

4 問題クラス Problem（１） オブジェクト生成の例（pという問題例を生成） p=Problem() メソッド
addVariable(変数名 ＝文字列，領域＝リスト） 変数を１つ問題に追加する． addVariables（変数のリスト，領域＝リスト） リストに含まれる変数（複数）を一度に問題に追加する． 例：p.addVariable(“Worker A”, [“Do Job1”,”Do Job2” ]) （作業員AはJob1かJob2を行う．） 例: p.addVariables([“A”, “B”], [“Do Job1”,”Do Job2” ]) （作業員 A,B は Job1かJob2を行う．）

5 問題クラス Problem（２） メソッド addConstriant（制約オブジェクト） 制約オブジェクトを問題に追加する．
setTarget(目標値＝整数：規定値0) ペナルティ逸脱量の合計が，ここで指定した目標値以下になったら探索が終了する． solve(time=制限時間：規定値600,seed=乱数の種:規定値1): 求解する．返値は，解（変数名をキー，値を領域から選ばれた値とした辞書）と逸脱した制約（制約名をキー，逸脱量を値とした辞書）のタプル

6 問題クラス Problem（３） Problemクラスは，文字列を返すメソッドが定義されている．
print 問題のオブジェクト 変数の数，制約の数，制約の情報を画面上に出力する．

7 線形制約クラス オブジェクト生成 Linear(制約名＝文字列，weight=1:既定値） 例：con1=Linear(“L1”,100)
メソッド addTerm(係数＝整数，変数名 ＝文字列，値＝数値，文字列） 左辺の項を１つ制約に追加する． setRhs（右辺定数＝整数） 線形制約の右辺定数を設定する．規定値は0 setDirection（制約の向き ＝ ”<=“,”>=“,”=“のいずれか） 制約の向きを設定する．規定値は”<=“ setWeight(重み＝正数もしくは”inf”） 制約の重みを設定する．”inf”は無限大（絶対制約）を示す．

8 ２次制約クラス オブジェクト生成 Quadratic(制約名＝文字列，weight=1:既定値） 例：con1=Quadratic(“Q1”,10) メソッド addTerm(係数，変数名1，値1，変数名2，値2） 左辺の2次の項を１つ制約に追加する． setRhs（右辺定数＝整数） 線形制約の右辺定数を設定する．規定値は0 setDirection（制約の向き ＝ ”<=“,”>=“,”=“のいずれか） 制約の向きを設定する．規定値は ”<=“ setWeight(重み＝正数もしくは”inf”） 制約の重みを設定する．”inf”は無限大（絶対制約）を示す．

9 相異制約クラス オブジェクト生成 Alldiff(制約名＝文字列，変数名のリスト：規定値は空のリスト，重み=1:既定値) 例：con1=Alldiff(“all_diff”,[“A”,”B”,”C”],”inf”) メソッド addVariable(変数名 ＝文字列） 相異制約の変数を１つ制約に追加する． addVariables(変数名リスト ＝文字列のリスト） 相異制約の変数を複数同時に追加する． setWeight(重み＝正数もしくは”inf”） 制約の重みを設定する．”inf”は無限大（絶対制約）を示す．

10 仕事の割当の例 割当はAlldiff制約，費用は線形制約 3人の作業員 A,B,C を3つの仕事 0,1,2 に割り当てる． 割当費用＝ 1
1 2 A 15 20 30 B 7 12 C 25 10 13 割当はAlldiff制約，費用は線形制約

11 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")

12 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)

13 実行結果 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

14 問題情報の出力 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

15 仕事の割当の例（２） ５人の作業員 A,B,C,D,E を3つの仕事 0,1,2 に割り当てる． 仕事の必要人数＝（１，２，２）人
割当費用＝ 1 2 A 15 20 30 B 7 12 C 25 10 13 D 18 3 E 5 17

16 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])

17 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]

18 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 (= ) 万円

19 仕事の割当の例（3） ５人の作業員 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

20 作業員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)

21 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 (= ) 万円

22 スタッフスケジューリング 1 シフトは8 時間，3 シフトの交代制 4 人のスタッフは，1 日の高々1 つのシフトしか行うことができない．
繰り返し行われる1 週間のスケジュールの中で，スタッフは最低5 日間は勤務しなければならない． 各シフトに割り当てられるスタッフの数は，ちょうど1 人でなければならない． 異なるシフトを翌日に行ってはいけない.（異なるシフトに移るときには，必ず休日を入れる．） シフト2, 3 は，少なくとも2 日間は連続で行わなければならない． この例題はカーネギーメロン大のJohn Hooker の2009 年の講演の例を改訂したものである

23 変数の追加 import scop #scopをインポート p=scop.Problem() #pと言う問題例オブジェクトを作成
periods=range(7) 　　#期間は７日間（曜日） shifts=range(4) 　　　#３種類のシフト1, 2, 3と休みを表す0 staffs=["A","B","C","D"]　 　　#４人のスタッフ variables=[] 　　　　 #変数を入れるためのリスト for i in staffs: for t in periods:　　　　　　　　　　　 variables.append(i+str(t)) #変数にスタッフ i と曜日 p.addVariables(variables,shifts)　#問題例pに変数，シフト追加　

24 スタッフに関する制約追加 繰り返し行われる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日間

25 シフトに関する制約追加 各シフトに割り当てられるスタッフの数は， ちょうど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)]) #制約を問題例に追加

26 シフトに関する禁止制約追加（１） 異なるシフトを翌日に行ってはいけない. 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)追加

27 シフトに関する禁止制約追加（２） 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日目シフト

28 結果の出力 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]

29 結果の出力 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 シフト １ ２ ３ 期