組合せ最適化エンジンWCSPの仕組みと実装
野々部宏司（法政大学）

数理システムユーザーコンファレンス2015（2015年11月20日）

概要


研究の背景・目的・方法

WCSPソルバー


重み付き制約充足問題（Weighted Constraint Satisfaction Problem）
アルゴリズムの概要

適用事例


国際コンペティション

最適化アプローチによる問題解決（最適化ソリューション）
問題・課題
モデリング
データ設定
最適化モデル
最適化計算（近似）最適解
解釈・分析・検証
結論・意思決定モデル・データの変更・修正

モデルの世界最適化アプローチによる問題解決（最適化ソリューション）
問題・課題
モデリング
データ設定
最適化モデル
最適化計算（近似）最適解
解釈・分析・検証

どのような（現実の）問題を扱うか
どのようにモデリングするか
モデル・データの変更・修正
どのようにデータを収集するか

モデルの世界
どのように最適化計算を行うか
どのように計算結果を解釈するかどのように結論を実行に移すか…

結論・意思決定

最適化計算：問題解決・意思決定過程における１つのステップ

最適化問題
種々の制約のもと，ある与えられた関数を最小化／最大化する問題の総称
minimizesubject to

𝑓𝑓(𝒙𝒙)𝒙𝒙 ∈ 𝐹𝐹𝑓𝑓(𝑥𝑥)：目的関数

𝐹𝐹：実行可能領域

解が組合せ的構造をもつ問題（組合せ最適化問題）を想定


実社会において広く現れる問題構造

最適化の方法（１）既存のソルバーを利用


混合整数計画（Mixed Integer Programming, MIP）
線形等式・不等式制約のもとで，１次関数を最小化／最大化する問題
変数は実数もしくは整数
MIPソルバー
商用・非商用を含め多くのソフトウェアが存在

モデリング言語が提供されていることが多く，問題記述が容易



定式化の工夫が必要になることも多い

実用的に解ける問題の規模が限定的であることも多い


現実に解くべき組合せ最適化問題の多くは NP困難



厳密な最適解を効率よく計算することはおそらく不可能：P≠NP予想

最適化の方法（２）ソルバーを個別に開発


方針１：厳密な最適解を計算することを目指す

方針２：厳密性にこだわらず，近似最適解で構わないと考える

一定時間内に実用上許容可能な解が計算できればよい最適化の方法（１）既存のソルバーを利用（２）ソルバーを個別に開発


選定のポイント

最適化計算の実現にかけられる手間・時間・費用

計算時間と解の質のトレードオフ



実務的観点からの要求・要望



問題の難しさ（計算の複雑さ）解法の特徴・性質

研究目的・方法
いろいろな問題に適用可能な汎用ソルバーを開発し，実行可能なソフトウェアとして提供


対象を組合せ最適化問題（静的・確定的）に限定



実務利用を念頭

良質の解を実用的な計算時間で出力することを目指す（理論的な最適性は保証しない）
アルゴリズム設計の枠組みや指針・テンプレートの提供ではなく，実装済みのアルゴリズム（ソルバー）を提供

方法


標準問題によるアプローチ



メタヒューリスティクス

方法：標準問題によるアプローチ
いくつかの標準問題をソルバーとともに用意
１．解きたい問題のタイプに応じて標準問題を選択
２．標準問題の形に記述してソルバーを適用


標準問題の例



混合整数計画問題（Mixed Integer Programming, MIP）
重み付き制約充足問題（Weighted Constraint Satisfaction Problem , WCSP）
資源制約付きプロジェクトスケジューリング問題（Resource-Constrained Project Scheduling Problem, RCPSP）...

［参考文献］ 茨木俊秀：「問題解決エンジン」への道，応用数理，Vol.14, pp.67-70 (2004).

方法：メタヒューリスティクス
計算困難な最適化問題に対する実用的アプローチのひとつ

様々な手法の総称
多くは局所探索法（ローカルサーチ）の拡張と解釈できるアルゴリズムの「枠組み」に過ぎない➔ 設計・実装を適切に行うことが必要
近傍 𝑁𝑁(𝒙𝒙)解 𝒙𝒙

近傍解𝒙𝒙′

概要


研究の背景・目的・方法

WCSPソルバー

重み付き制約充足問題（Weighted Constraint Satisfaction Problem）
アルゴリズムの概要

適用事例


国際コンペティション

制約充足問題（CSP）


𝑛𝑛個の変数 𝑋𝑋𝑖𝑖 𝑖𝑖 = 1, 2, … , 𝑛𝑛𝑋𝑋𝑖𝑖 がとり得る値の集合 𝐷𝐷𝑖𝑖 (𝑖𝑖 = 1, 2, … , 𝑛𝑛) ―有限離散集合を仮定
𝑚𝑚個の制約 𝐶𝐶𝑘𝑘 𝑘𝑘 = 1, 2, … , 𝑚𝑚

すべての制約を満たすように
各変数 𝑿𝑿𝒊𝒊 に値 𝒋𝒋 ∈ 𝑫𝑫𝒊𝒊 を１つずつ割当てることが目的
1,0-1変数 𝑥𝑥𝑖𝑖𝑖𝑖 = �0,解（割当て）𝑋𝑋𝑖𝑖 = 𝑗𝑗
𝑖𝑖 = 1, 2, … , 𝑛𝑛, 𝑗𝑗∈𝐷𝐷𝑖𝑖
𝑋𝑋𝑖𝑖 ≠ 𝑗𝑗

𝒙𝒙 = (𝑥𝑥𝑖𝑖𝑖𝑖 | 𝑖𝑖 = 1, 2, … , 𝑛𝑛, 𝑗𝑗∈𝐷𝐷𝑖𝑖 )

s.t.



∑ 𝑥𝑥𝑖𝑖𝑖𝑖 = 1, 𝑖𝑖 = 1,2, … , 𝑛𝑛

𝑗𝑗∈𝐷𝐷𝑖𝑖

例： 𝑛𝑛 = 4，𝐷𝐷1 = 𝐷𝐷2 = 𝐷𝐷3 = 𝐷𝐷4 = {1, 2, 3}
𝒙𝒙 = 0,1,0 1,0,0 0,1,0 0,0,1← (𝑋𝑋1 , 𝑋𝑋2 , 𝑋𝑋3 , 𝑋𝑋4 ) = (2,1,2,3)

すべての制約を満たす解 𝒙𝒙 が存在するとは限らない
存在するとしても，見つけることは計算困難重み付きCSP（WCSP）
それぞれの制約 𝐶𝐶𝑘𝑘 について違反度に応じたペナルティ 𝑝𝑝𝑘𝑘 (𝒙𝒙)（制約を満たすとき 0）

重要度に応じた重み 𝑤𝑤𝑘𝑘 ≥ 0

ペナルティの加重和 𝑝𝑝 𝒙𝒙 = ∑ 𝑤𝑤𝑘𝑘 𝑝𝑝𝑘𝑘 𝒙𝒙 を最小化





𝑘𝑘

絶対制約を満たしたうえで，考慮制約の違反度を最小化
目的関数 𝑓𝑓(𝒙𝒙) を最小化する場合ペナルティ関数 𝑝𝑝𝑘𝑘 𝒙𝒙 ≔ 𝑓𝑓 𝒙𝒙 − 𝐿𝐿𝐿𝐿 の考慮制約（𝐿𝐿𝐿𝐿：𝑓𝑓(𝒙𝒙) の下界値）

いろいろなタイプの割当て問題を定式化可能

MIPなどと比べ，より簡潔に，より自然な形で制約を記述可能

人為変数（本来の決定変数ではない変数）の導入を回避➔ 効率的な最適化計算

代表的な制約・ペナルティ関数


0-1変数 𝑥𝑥𝑖𝑖𝑖𝑖 に関する線形または２次等式・不等式
「𝑔𝑔 𝒙𝒙 ≤ 𝑏𝑏」の形の不等式制約に対してはペナルティ := max 0, 𝑔𝑔 𝑥𝑥 − 𝑏𝑏

（参考）

２次関数 ∑∑∑∑𝑎𝑎𝑖𝑖1 𝑗𝑗1 𝑖𝑖2 𝑗𝑗2 𝑥𝑥𝑖𝑖1 𝑗𝑗1 𝑥𝑥𝑖𝑖2 𝑗𝑗2 を目的関数として最小化する場合
𝑖𝑖1 𝑗𝑗1 𝑖𝑖2 𝑗𝑗2各項に対して，

重み 𝑤𝑤𝑘𝑘 ≔ 𝑎𝑎𝑖𝑖1 𝑗𝑗1 𝑖𝑖2 𝑗𝑗2 の線形考慮制約「𝑥𝑥𝑖𝑖1 𝑗𝑗1 + 𝑥𝑥𝑖𝑖2 𝑗𝑗2 ≤ 1」を追加することでも記述可能

代表的な制約・ペナルティ関数


0-1変数 𝑥𝑥𝑖𝑖𝑖𝑖 に関する線形または２次等式・不等式


「𝑔𝑔 𝒙𝒙 ≤ 𝑏𝑏」の形の不等式制約に対してはペナルティ := max 0, 𝑔𝑔 𝑥𝑥 − 𝑏𝑏

all-different 制約「与えられた変数集合 𝑉𝑉 に含まれる変数はすべて異なる値をとらなくてはならない」


ペナルティ := 𝑉𝑉 − 𝑉𝑉 に含まれる変数がとっている値の種類数「制約を定義」=「ペナルティ関数を定義」


個々のペナルティ関数を単独で最小化することは容易であると仮定

例：ナーススケジューリング問題


各ナースの毎日のシフトを決定



制約




シフト拘束制約 適正人数のナースを確保
ナース拘束制約 ナースの労動負荷や勤務希望を考慮

WCSPへの定式化


変数：（ナース，日にち）の各組に対応



領域： シフトの集合

WCSPソルバーの概要


基本的な枠組みはタブーサーチ（局所探索法の拡張）


近傍内の最良解に移動（改悪解への移動もあり得る）近傍解のすべてを移動先の候補とはしない＝ 近傍内に移動禁止の（「タブー」な）領域がある

×

近傍 𝑁𝑁(𝒙𝒙)

解 𝒙𝒙

近傍解
𝒙𝒙′

［参考文献］ K. Nonobe and T. Ibaraki: An improved tabu search method for the weighted constraint satisfaction
problem, INFOR 39, pp.131–151 (2001).

WCSPソルバーの概要


基本的な枠組みはタブーサーチ（局所探索法の拡張）


近傍内の最良解に移動（改悪解への移動もあり得る）
近傍解のすべてを移動先の候補とはしない＝ 近傍内に移動禁止の（「タブー」な）領域がある

基本要素
探索空間

解（割当て）集合全体

近傍

ある１つの変数の値を変更することで得られる解の集合

タブーリスト

解移動において値を変更した変数をしばらくの間保持リスト内の変数の値は変更不可

初期解

ランダム割当てを欲張り法で改善［参考文献］ K. Nonobe and T. Ibaraki: An improved tabu search method for the weighted constraint satisfaction
problem, INFOR 39, pp.131–151 (2001).

WCSPソルバーの概要：特長・特徴
近傍解評価のための補助メモリ利用
探索の高速化

近傍探索領域の限定
効果的な探索プログラム・パラメータのユーザ定義制約

動的調整

追加の仕組み利便性／探索の高性能化

拡張性

近傍解評価のための補助メモリ利用
𝒙𝒙：現在の解𝒙𝒙 𝑋𝑋𝑖𝑖 ← 𝑗𝑗 ：𝑋𝑋𝑖𝑖 の値を 𝑗𝑗 に変更することで得られる近傍解例：

𝒙𝒙= 0,1,0 1,0,0 0,1,0 0,0,1

𝒙𝒙 𝑋𝑋3 ← 3 = (0,1,0|1,0,0|0,0,1|0,0,1)

近傍解の評価

近傍 𝑁𝑁(𝒙𝒙)𝑋𝑋𝑖𝑖, 𝑗𝑗 (∈ 𝐷𝐷𝑖𝑖 ) の組それぞれに対して，𝑋𝑋𝑖𝑖 の値を 𝑗𝑗 に変更したときのペナルティ変化量∆𝑝𝑝 𝒙𝒙, 𝑖𝑖, 𝑗𝑗 ≔ 𝑝𝑝 𝒙𝒙 𝑋𝑋𝑖𝑖 ← 𝑗𝑗を事前に計算・保持− 𝑝𝑝 𝒙𝒙➔ 定数時間で近傍解を１つ評価することが可能


解の移動ごとに情報の更新が必要

解 𝒙𝒙
近傍解𝒙𝒙 𝑋𝑋𝑖𝑖 ← 𝑗𝑗

ペナルティ変化量の保持

例：𝒙𝒙 = (0,1,0|1,0,0|0,1,0|0,0,1)
1∆𝑝𝑝(𝒙𝒙, ⋅, ⋅)4𝑋𝑋1203130𝑋𝑋22−23103𝑋𝑋3203151𝑋𝑋4221 𝑖𝑖,0𝑗𝑗) =0 𝑝𝑝 𝒙𝒙
0 𝑋𝑋 00− 𝑝𝑝 0𝒙𝒙 00∆𝑝𝑝1ペナルティ変化量(𝒙𝒙, ⋅, ⋅) 3 0 ∆𝑝𝑝(𝒙𝒙,𝑖𝑖 ← 𝑗𝑗∆𝑝𝑝2(𝒙𝒙, ⋅, ⋅) 0 0 0 0 −4 −2 0 0 0 0 0= � 𝑤𝑤 𝑝𝑝 𝒙𝒙 𝑋𝑋 ← 𝑗𝑗 − � 𝑤𝑤 𝑝𝑝 𝒙𝒙∆𝑝𝑝3(𝒙𝒙, ⋅, ⋅) 0 0 0 0 0 𝑘𝑘 0 𝑘𝑘 𝑘𝑘2 𝑖𝑖 0 1 𝑘𝑘 2 𝑘𝑘 𝑘𝑘1∆𝑝𝑝4(𝒙𝒙, ⋅, ⋅) 1 0 0 0 0 0 1 0 0 −1 0
= � 𝑤𝑤𝑘𝑘 𝑝𝑝𝑘𝑘 𝒙𝒙 𝑋𝑋𝑖𝑖 ← 𝑗𝑗 − 𝑝𝑝𝑘𝑘 𝒙𝒙∆𝑝𝑝5(𝒙𝒙, ⋅, ⋅) 0 0 0 0 2 𝑘𝑘 0 0 0 0 0 1∆𝑝𝑝6(𝒙𝒙, ⋅, ⋅) 0 0 2 0 =0 �2𝑤𝑤 ∆𝑝𝑝0 (𝒙𝒙, 𝑖𝑖,0𝑗𝑗) 4 0 0
𝑘𝑘𝑘𝑘𝑘𝑘30000000

ペナルティ変化量の保持

例：𝒙𝒙 = (0,1,0|1,0,0|0,1,0|0,0,1)→ (0,1,0|𝟎𝟎, 𝟏𝟏, 0|0,1,0|0,0,1)
1∆𝑝𝑝(𝒙𝒙, ⋅, ⋅)4∆𝑝𝑝1(𝒙𝒙, ⋅, ⋅) 3
∆𝑝𝑝2(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝3(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝4(𝒙𝒙, ⋅, ⋅) 1
∆𝑝𝑝5(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝6(𝒙𝒙, ⋅, ⋅)

𝑋𝑋12

3

103

00

1
0𝑋𝑋2
2

3

1−203−4−22003

105

101202𝑋𝑋4232010−1122𝑋𝑋32

140ペナルティ変化量の更新


例：𝒙𝒙 = (0,1,0|1,0,0|0,1,0|0,0,1)→ (0,1,0|𝟎𝟎, 𝟏𝟏, 0|0,1,0|0,0,1)
1∆𝑝𝑝(𝒙𝒙, ⋅, ⋅)4∆𝑝𝑝1(𝒙𝒙, ⋅, ⋅) 3
∆𝑝𝑝2(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝3(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝4(𝒙𝒙, ⋅, ⋅) 1
∆𝑝𝑝5(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝6(𝒙𝒙, ⋅, ⋅)

𝑋𝑋12

3

1

0

300

1
0𝑋𝑋2
2

3

1−20

3−4−2200

3

10

5

10

1202𝑋𝑋4
2

320

1

0−1

122𝑋𝑋32140近傍探索領域の限定

すべての（タブーでない）近傍解をチェックすることは非効果的「多くの計算時間を要する」ことだけが問題ではない

タブーサーチは「（タブーでない）最良の近傍解への移動」が基本
ペナルティにほとんど影響を与えない「軽微な」修正ばかりが繰り返され，「山を越える」改善が起こりにくい

現在の解が満たしていない制約の少なくとも１つについてペナルティ値を減少させるような解移動のみを候補とする
近傍 𝑁𝑁(𝒙𝒙)

解 𝒙𝒙

タブー

近傍探索領域の限定

違反制約

例：𝒙𝒙 = (0,1,0|1,0,0|0,1,0|0,0,1)
1∆𝑝𝑝(𝒙𝒙, ⋅, ⋅)4∆𝑝𝑝1(𝒙𝒙, ⋅, ⋅) 3
∆𝑝𝑝2(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝3(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝4(𝒙𝒙, ⋅, ⋅) 1
∆𝑝𝑝5(𝒙𝒙, ⋅, ⋅)∆𝑝𝑝6(𝒙𝒙, ⋅, ⋅)𝑋𝑋12

3

10300

10𝑋𝑋2231−203−4−22003105

101202𝑋𝑋4232010−1122𝑋𝑋32

140

パラメータの自動調整 (1)

タブー期間（tabu tenure）
タブーリストにより，変数の値の変更が禁止される期間


タブー期間が短い場合


緻密な探索（集中化）



偏った探索

➔ 探索履歴から判断し，タブー期間増

タブー期間が長い場合


解の循環防止，探索の多様化



過剰な禁止

近傍 𝑁𝑁(𝒙𝒙)

解 𝒙𝒙

タブー

➔ 特別選択規則（aspiration criteria）により判断し，タブー期間減

パラメータの自動調整 (2)ペナルティ重みペナルティ関数 𝑝𝑝(𝒙𝒙) = ∑ 𝑤𝑤𝑘𝑘 𝑝𝑝𝑘𝑘 𝒙𝒙 を𝑘𝑘

そのまま近傍解の評価関数として用いる探索は非効果的

近傍解の良し悪しが重みの大きな制約に強く依存
その他の制約は軽視される傾向➔ 重みの大きな制約を満たす解に探索が制限

近傍解の評価には 𝑓𝑓 𝒙𝒙 = ∑ 𝑣𝑣𝑘𝑘 𝑝𝑝𝑘𝑘 𝒙𝒙 を使用


0 < 𝑣𝑣𝑘𝑘 ≤ 𝑤𝑤𝑘𝑘

𝑣𝑣𝑘𝑘 の値を自動調整

𝑘𝑘𝑝𝑝 𝒙𝒙
𝑓𝑓 𝒙𝒙

パラメータの自動調整 (2)近傍解の評価には 𝑓𝑓 𝒙𝒙 = ∑ 𝑣𝑣𝑘𝑘 𝑝𝑝𝑘𝑘 𝒙𝒙 を使用
𝑘𝑘

𝑣𝑣𝑘𝑘 の値の自動調整

ラグランジュ緩和法における劣勾配法のアイデアを利用
𝒙𝒙∗ ：前回の 𝑣𝑣𝑘𝑘 調整後に得られた，「𝑓𝑓 𝒙𝒙 最小化」の意味での最良解𝑝𝑝𝑘𝑘 𝒙𝒙∗ > 0 である制約に対しては，𝑣𝑣𝑘𝑘 を増加
𝑈𝑈𝑈𝑈 − 𝑓𝑓(𝒙𝒙∗)∗)𝑝𝑝(𝒙𝒙∗ 2 𝑘𝑘
𝑘𝑘 𝑝𝑝𝑘𝑘 (𝒙𝒙 )𝑣𝑣𝑘𝑘 ≔ min 𝑤𝑤𝑘𝑘 , 𝑣𝑣𝑘𝑘 + ∑𝑓𝑓(𝒙𝒙∗ ) ≥ 𝑈𝑈𝑈𝑈 の場合は，すべての 𝑣𝑣𝑘𝑘 を減少

𝑝𝑝 𝒙𝒙
𝑓𝑓 𝒙𝒙

暫定値（上界値）
𝑈𝑈𝑈𝑈
𝒙𝒙∗ソルバーの概要
最適化ソルバー
C++クラス・ライブラリ
制約クラス（抽象クラス）

ユーザ

制約
all-diff

インタフェース

２次制約（メタヒューリスティクス）

線形制約

最適化エンジン…

ユーザ定義制約の追加「制約を定義」=「ペナルティ関数を定義」
実装上は，以下の関数を用意

与えられた解 𝒙𝒙 に対して，ペナルティ𝑝𝑝𝑘𝑘 (𝒙𝒙) を計算し，ペナルティ変化量 ∆𝑝𝑝𝑘𝑘 𝒙𝒙, 𝑖𝑖, 𝑗𝑗 を列挙（非零のみ）制約に関与している（＝ペナルティ計算時に値を参照する必要のある）
0-1変数を列挙

概要


研究の背景・目的・方法

WCSPソルバー

重み付き制約充足問題（Weighted Constraint Satisfaction Problem）
アルゴリズムの概要

適用事例


国際コンペティション

適用事例




Numerical Optimizer（旧NUOPT） の一機能として多くの問題に適用
国際コンペティションInternational Timetabling Competition 2007 (ITC2007)

International Nurse Rostering Competition 2010 (INRC2010)…

適用例：時間割作成
ITC2007 (International Timetabling Competition)
トラック１（試験時間割） ３位


トラック２（履修登録に基づいた授業時間割） ２位




試験数：200～1000
ピリオド数：20～80, 教室数：1～50
学生数：5000～16000
授業数： 200～400
ピリオド数：45, 教室数：5～20
学生数：300～1000

トラック３（カリキュラムに基づいた授業時間割） ３位


教科数： 150～450
ピリオド数：25～45, 教室数：5～20

計算時間：約５～10分［参考文献］茨木俊秀，熱田光紀，野々部宏司：汎用ソルバによる時間割作成―国際コンペティションITC2007に参加して―，スケジューリング・シンポジウム2008講演論文集，pp.173－176 (2008)．

適用例：ナーススケジューリング
INRC2010 (International Nurse Rostering Competition)

３つのトラック：sprint, medium, long

ナース数：10 (sprint), 30～31 (medium), 49～50 (long)日数：28

シフト数：4～5 (sprint), 5～6 (medium), 6 (long)

計算時間：10秒 (sprint), 10分 (medium), 10時間 (long)

制約数： 約1800～3600 (sprint)
約3300～11,500 (medium)
約7200～21,500 (long)［参考文献］野々部宏司：メタヒューリスティクスを用いた制約最適化ソルバーのナーススケジューリング問題への適用，
電気学会研究会資料，システム研究会，ST-10-6，pp.27－31 (2010)．

INRC2010：問題概要
シフト拘束制約：絶対制約

各日，各シフトについて，指定された人数のナースを過不足なく確保

ナース拘束制約：考慮制約（各制約に重み）制約の有無，上下限値，週末の定義はナースによって異なる

各シフトについて，スケジュール期間中の割当て回数に上下限

連続勤務日数／連続休暇日数に上下限

完全休暇ではない週末の連続数に上限



同じ週末に含まれる日には同じシフト



夜勤終了後，2日間の休暇日



望ましくないシフトの並びを禁止（夜勤の翌日に日勤など）



いくつかの日に，割当て指定シフト／割当て禁止シフト

考慮制約違反に対するペナルティの加重和を最小化

INRC2010：コンペティション結果

https://www.kuleuven-kulak.be/nrpcompetition/competitor-ranking

まとめ

実務利用を念頭に置いた汎用ソルバーの開発


WCSPに対するメタヒューリスティックアルゴリズム

多数の適用事例