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

Slides:



Advertisements
Similar presentations
Excel ソルバー練習 *ツール → アドイン → ソルバーアド インにチェックを入れて、ソルバー を使えるようにしてから、作業を行 うこと。
Advertisements

クエリ作成方法 ユーザグループ: ZZUSGI 001(固定) インフォセット: ZZIxxyy クエリ: ZZQxxyy xx = 2 桁のユーザ ID yy = 01 ~ 通し番号.
復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
(Rubyistのための) 超音速:ML入門
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
JavaScript プログラミング入門 2006/11/10 神津.
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 M2 平石 拓
タスクスケジューリング    .
プログラミング言語としてのR 情報知能学科 白井 英俊.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
スレッドの同期と、スレッドの使用例 スレッドの同期 Lockオブジェクト: lockオブジェクトの生成
最短路問題をGurobiで解こう! 流通最適化工学 補助資料.
アルゴリズムとプログラミング (Algorithms and Programming)
実行時のメモリ構造(1) Jasminの基礎とフレーム内動作
Lightweight Language Weekend ls-lRシェル
最適化ソルバーのための Python言語入門
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
Ruby勉強会(第1回) 2006/06/29 竹内豪.
Bottle/Pythonによる Webアプリ入門
理由:文字数より要素数の多い配列を用いた時に,文字列の最後を示すため
アルゴリズムとデータ構造 2011年6月13日
理由:文字数より要素数の多い配列を用いた時に,文字列の最後を示すため
条件式 (Conditional Expressions)
模擬国内予選2014 Problem C 壊れた暗号生成器
1章前半.
第20章 Flyweight ~同じものを共有して無駄をなくす~
関数 関数とスタック.
ピカチュウによる オブジェクト指向入門 (新版)
テキストボックス、チェックボックス×2、コマンドボタンを配置する。 コマンドボタンに機能を与える
第6回独習Javaゼミ 第6章 セクション4~6 発表者 直江 宗紀.
第7回 条件による繰り返し.
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
11.6 ランダムアクセスファイル 11.7 StreamTokenizerクラス
プログラミング演習 バージョン1 担当教員:綴木 馴.
第9章 例外処理,パッケージ 9.1 例外処理 9.2 ガーベッジコレクション.
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 D1 平石 拓 2005/10/18
プログラミング言語入門.
アルゴリズムとプログラミング (Algorithms and Programming)
画像処理プログラムの説明.
第7回 条件による繰り返し.
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
メタ解法設計者のための Python超入門
7.4 intanceof 演算子 7.5~7.9パッケージ 2003/11/28 紺野憲一
独習Javaゼミ第10回 セクション1~3 発表者 直江 宗紀.
スケジューリング最適化システム OptSeq II Pythonモジュールの使い方 補助資料:OptSeq II によるスケジューリング入門 トライアルバージョン
第4回 線形計画 2000年11月 第4回 線形計画.
PHP 概要 担当 岡村耕二 月曜日 2限 平成22年度 情報科学III (理系コア科目・2年生)
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
コーパス言語学 ~バッチ処理~ 2013.10. 28.
疑似乱数, モンテカルロ法によるシミュレーション
コンパイラ 2011年10月20日
ファイルの読み込み #!/usr/bin/env perl #Perlスクリプトの指定 open(FILE, "food.txt");
統計ソフトウエアRの基礎.
アルゴリズムとプログラミング (Algorithms and Programming)
復習 2次元配列 4列 j = 0 j = 1 j = 2 j = 3 i = 0 i = 1 i = 2 3行
制約最適化モジュール SCOP   東京海洋大学 久保幹雄.
計算機プログラミングI 第3回 プリミティブ値 クラスメソッド クラス変数 式と演算 変数の利用
アルゴリズムとデータ構造 2012年6月11日
地域情報学 C言語プログラミング 第4回 while文、do~while文、switch文、 2次元配列、ポインタ 2017年11月10日
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
プログラミング基礎演習 第4回.
プログラミング 4 文字列.
PROGRAMMING IN HASKELL
情報処理Ⅱ 2005年11月25日(金).
情報処理Ⅱ 2006年10月20日(金).
分岐(If-Else, Else if, Switch) ループ(While, For, Do-while)
情報処理Ⅱ 第8回:2003年12月9日(火).
計算機プログラミングI 第2回 2002年10月17日(木) 履習登録 複習 ライブラリの利用 (2.6-7) 式・値・代入 (2.6-8)
Presentation transcript:

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 期