実行結果

制約計画ソルバー 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
2
A
15
20
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
A
15
20
30
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
A
15
20
30
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

Download Report