スライド 1 - LOG OPT HOME

制約計画ソルバー SCOP
Solver for COnstraint Programming：スコープ
Pythonモジュールの使い方
SCOP.pyモジュールとは
制約計画ソルバーSCOPを，超高級言語
Pythonから直接呼び出して，求解する
ためのモジュール
すべてPythonで書かれたクラスで構成
ソースコード（すべてPythonで記述）
も公開されているので，ユーザが書き
換え可能
Pythonモジュールのクラス
問題クラス Problem
制約クラス (Constraint)



線形制約クラス Linear
2次制約クラス Quadratic
相異制約クラス Alldiff
問題クラス 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を行う．）
問題クラス Problem（２）
メソッド



addConstriant（制約オブジェクト）
制約オブジェクトを問題に追加する．
setTarget(目標値＝整数：規定値0)
ペナルティ逸脱量の合計が，ここで指定した目標値
以下になったら探索が終了する．
solve(time=制限時間：規定値600,seed=乱数の種:規定
値1):
求解する．返値は，解（変数名をキー，値を領域か
ら選ばれた値とした辞書）と逸脱した制約（制約名
をキー，逸脱量を値とした辞書）のタプル
問題クラス Problem（３）
Problemクラスは，文字列を返すメソッドが定義
されている．
print 問題のオブジェクト
変数の数，制約の数，制約の情報を画面上に出
力する．
線形制約クラス
オブジェクト生成
Linear(制約名＝文字列，weight=1:既定値）
例：con1=Linear(“L1”,100)
メソッド




addTerm(係数＝整数，変数名＝文字列，値＝数値，文
字列）
左辺の項を１つ制約に追加する．
setRhs（右辺定数＝整数）
線形制約の右辺定数を設定する．規定値は0
setDirection（制約の向き＝ ”<=“,”>=“,”=“のいずれ
か）
制約の向きを設定する．規定値は”<=“
setWeight(重み＝正数もしくは”inf”）
制約の重みを設定する．”inf”は無限大（絶対制約）を
示す．
２次制約クラス
オブジェクト生成
Quadratic(制約名＝文字列，weight=1:既定値）
例：con1=Quadratic(“Q1”,10)
メソッド




addTerm(係数，変数名1，値1，変数名2，値2）
左辺の2次の項を１つ制約に追加する．
setRhs（右辺定数＝整数）
線形制約の右辺定数を設定する．規定値は0
setDirection（制約の向き＝ ”<=“,”>=“,”=“のいずれ
か）
制約の向きを設定する．規定値は ”<=“
setWeight(重み＝正数もしくは”inf”）
制約の重みを設定する．”inf”は無限大（絶対制約）を
示す．
相異制約クラス
オブジェクト生成
Alldiff(制約名＝文字列，変数名のリスト：規定値
は空のリスト，重み=1:既定値)
例：con1=Alldiff(“all_diff”,[“A”,”B”,”C”],”inf”)
メソッド



addVariable(変数名＝文字列）
相異制約の変数を１つ制約に追加する．
addVariables(変数名リスト＝文字列のリスト）
相異制約の変数を複数同時に追加する．
setWeight(重み＝正数もしくは”inf”）
制約の重みを設定する．”inf”は無限大（絶対制約）を
示す．
仕事の割当の例
3人の作業員 A,B,C を3
つの仕事 0,1,2 に割り当
てる．
0
1
割当費用＝
A 15 20
2
30
B
7
15
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
解の表示
A0
C1
B2
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
ACB
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
仕事の割当の例（２）
５人の作業員 A,B,C,D,E を3つ
の仕事 0,1,2 に割り当てる．
仕事の必要人数＝（１，２，
２）人
0
1
2
割当費用＝
15
20
30
A
B
7
15
12
C
25
10
13
D
15
18
3
E
5
12
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による求解
solution
A1
C1
B2
E0
D2
violated constraint(s)
linear_constraint 50
50 (=20+12+10+3+5) 万円
0
1
2
A
15
20
30
B
7
15
12
C
25
10
13
D
15
18
3
E
5
12
17
仕事の割当の例（3）
５人の作業員 A,B,C,D,E を3つの仕事 0,1,2 に割り
当,必要人数は(1,2,2)人（前の例と同じ）
作業員AとCは仲が悪いので，異なる仕事に割り
振る
0
1
2
割当費用＝
15
20
30
A
B
7
15
12
C
25
10
13
D
15
18
3
E
5
12
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による求解
solution
A0
C1
B2
E1
D2
violated constraint(s)
linear_constraint 52
52 (=15+12+10+3+12) 万円
0
1
2
A
15
20
30
B
7
15
12
C
25
10
13
D
15
18
3
E
5
12
17
スタッフスケジューリング
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)
#期間は７日間（曜日）
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に変数，シフト追加
スタッフに関する制約追加
繰り返し行われる1 週間のスケジュールの中で，
スタッフは最低5日間は勤務しなければならない．
LB={}
#スタッフ制約オブジェクトを入れるための辞書作成
for i in staffs:
#スタッフに関する制約を線形制約として追加
LB[i]=scop.Linear(“LB ”+i) #制約の名前,重み(規定値=1)追加
for t in periods:
for s in shifts[1:]:
LB[i].addTerm(1,i+str(t),s)
LB[i].setRhs(5)
#線形制約左辺追加
#線形制約に右辺追加
LB[i].setDirection(">=")
#線形制約の制約向き追加
最低5日間
p.addConstraint(LB[i]) #制約オブジェクトを問題例に追加
シフトに関する制約追加
各シフトに割り当てられるスタッフの数は，
ちょうど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)]) #制約を問題例に追加
シフトに関する禁止制約追加
（１）
異なるシフトを翌日に行ってはいけない.
Forbid={} #禁止制約オブジェクトを入れるための辞書作成
for i in staffs: #禁止制約を線形制約として追加
for t in periods:
#制約の名前,重み(規定値=1)追加
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)])
#制約を問題例に追加
シフトに関する禁止制約追加
（２）
•
シフト2, 3 は，少なくとも2日間は連続で行わなければならない
Cons={}
x[Aのt-1,s]+x[Aのt+1,s]>=x[Aのt,s]
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)
2日目
シフト 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)
#一番最後の期で行われる
3日目
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)])
結果の出力
# 結果（解）の出力
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
１
２
３
期

Download Report