制約プログラミング入門 - constraint.org

COM･APS研究部会第4回研究会資料
制約プログラミングは計画系
システム開発に役立つか？
2001年7月19日
（株）アイザック技術開発部
山崎雅史
[email protected]
http://www.constraint.org/
copyright(c) 2001, ISAC Inc.
内容
1.制約プログラミングの定義・特徴
2.研究・実用化の歴史
3.制約プログラミングの手法
4.事例（１）屋根パネル積載計画システム
5.事例（２）屋根パネル分割システム
6.まとめ：事例の評価と今後の方向性
copyright(c) 2001, ISAC Inc.
1.制約プログラミングの定義･特徴
copyright(c) 2001, ISAC Inc.
制約プログラミングの定義
制約とは、未知数（論理型言語の変数）の間の関
係。
問題を変数と変数間の制約で記述。
制約を充たす変数の値を求める。
例）A+B=C, D>E, X=Y
運転手Aは訪問先Bに行けない。
看護婦Cは月・水・金の日勤のみ可能。
太陽電池付きパネルは一番上にしか積めない。
copyright(c) 2001, ISAC Inc.
特徴
宣言的な記述。
制約は部分情報の表現である。
制御の流れは必ずしも固定されない。(cf.
関数型言語、Prolog)
制約はincrementalであり、additiveである。
問題の表現と問題の解決は分離される。
copyright(c) 2001, ISAC Inc.
制約プログラミングの分類
変数および制約の種類によって下位分類。
変数の領域による分類例：有限領域、整
数、有理数、実数、論理値..
制約の種類による分類例：線形／非線形..
領域が異なれば、解決可能かどうかや、適
した解決手法が異なる。（「解けた」ことの
定義自体が異なる場合もある。）
copyright(c) 2001, ISAC Inc.
領域と解法
離散・有限領域：要素を数え上げることが
できる。例）A = {1,2,3,5,6}
離散的な組み合わせ問題になる。
連続・無限だと、解法は異なる。（ex.単体法、
ニュートン法）。一般的な解き方がない場合や、
不明な場合もある。
ここでは、離散・有限領域に限定する。
copyright(c) 2001, ISAC Inc.
2.研究・実用化の歴史
copyright(c) 2001, ISAC Inc.
先駆的な研究（1980年代まで）
人工知能（AI）研究：画像のラベリングの研
究(Waltz)
対話型のグラフィックスシステム：
Sketchpad, ThingLab
論理プログラミング（Logic
Programming）：単一化（Unification）から
制約へ。
OR（Operations Research）：組み合わせ
問題
copyright(c) 2001, ISAC Inc.
研究の進展（1980年代後半）
論理プログラミングの拡張の研究の中から
制約処理系が開発される。
日本のICOTでも、いくつかの制約処理系
が開発された。(CAL, GDCC,
CuProlog, ...)
商用化へ繋がる研究はヨーロッパが中心。
（ECRC、マルセイユ大 etc.）
copyright(c) 2001, ISAC Inc.
商用化の（第一の）波
1990年あたりから、一気に制約処理系の
商用化が進む。
Charme(Bull), ILOG Solver(ILOG), CHIP
V4(Cosytec), PrologIII(PROLOGIA),
CLP(R)(IBM), CHLEO(AXIA),
DECISIONPOWER(ICL),
SNIPROLOG(Siemens Nixdorf)
copyright(c) 2001, ISAC Inc.
日本における動向(1990以降)
Charme(Bull、1989年)が日本でも販売さ
れる。Charmeは世界初の商用制約プログ
ラミングツール。
ILOG Solver(ILOG), CHIP V4(Cosytec)と
いった制約プログラミング開発ツールが相
次いで販売される。
Prolog処理系が制約解消系を備えるよう
になる。
copyright(c) 2001, ISAC Inc.
研究の進展(1990以降)
整合性維持手法の改良
制約階層、部分CSP、確率つき、Fuzzy...
ユーザー定義可能な制約のサポート
スケジューリングのような問題領域に特化
した制約の形式化および実装の研究
並列化(concurrent constraint モデル)
オブジェクト指向パラダイムとの融合
copyright(c) 2001, ISAC Inc.
実用事例の蓄積
スケジューリング、要員配置、ダイヤグラ
ム作成などの計画系のアプリケーションの
開発が中心。
フロアレイアウト設計や知的CADのような
設計支援分野も多い。
VLSI設計・検証。
企業財務・金融・分子生物情報学（DNA配
列の予測）などの事例もある。
copyright(c) 2001, ISAC Inc.
ミドルウェアとしての事例
GUIライブラリにおける部品の自動配置メ
カニズム（Packer）は、制約プログラミング
が基本にある。
宣言性・双方向性などの特徴から、スプ
レッドシートへの組込みもあった。(Delisoft
のInterval Solver)
copyright(c) 2001, ISAC Inc.
3.制約プログラミングの手法
copyright(c) 2001, ISAC Inc.
制約プログラミングの手法
論理プログラミングにおける探索と対比させなが
ら、制約プログラミングによる問題解決を担う手
法を概観する。
1.全域探索の効率化
2a.整合性維持手法(consistency technique)
2b.制約伝播手法(constraint propagation)
3.探索戦略・最適化
copyright(c) 2001, ISAC Inc.
1.探索による問題解決
大域的探索により、制約を充足するように
変数に付値していく。
完全かつ健全。
例)縦形探索による単純な生成→検査法
やバックトラック手法。
効率の問題がある。
copyright(c) 2001, ISAC Inc.
生成→検査法
最も一般的な問題解決手法。
生成した解に対して、制約を充たしている
かを検査する。
生成の後に検査をするので、矛盾の検出
は生成の後。→無駄な生成をする。
copyright(c) 2001, ISAC Inc.
検査→生成法：バックトラック
部分解について制約充足の検査を行い、
矛盾を検出したら、その先の付値は中止、
後戻りをすることで、徐々に完全な解に近
づいて行く。
矛盾の本当の原因に辿り着くまでに無駄
な探索をする可能性がある。(thrashing)
矛盾の検出は、すでに得られた部分解の
範囲についてしか行わない。
copyright(c) 2001, ISAC Inc.
2a.整合性維持手法
（consistency technique）
問題空間を常に制約に矛盾しない状態に
保持する方法
整合性検査の範囲で以下のように分類
Node Consistency（NC）：ノード（単項）整合
Arc Consistency（AC）：アーク（2項）整合
Path Consistency（パス整合）
copyright(c) 2001, ISAC Inc.
アーク整合アルゴリズム（AC）
整合性の検査は範囲が広ければ、より早く
矛盾が検出できる可能性があるが、検査
のための計算量も増大するので、トレード
オフが存在する。
NC/ACの検査を行うのが一般的
ACについては、主として計算量の観点か
ら、AC3,AC4をはじめとして、様々なアルゴ
リズムが提案されている。
copyright(c) 2001, ISAC Inc.
ACの限界
例えば、X={0,1}, Y={0,1}, Z={0,1},
X!=Y, Y!=Z, Z!=X の場合、ACでは矛盾が
検出できない。
探索による付値が行われれば直ちに矛盾
が検出できる。
制限をつけてPath Consistencyを併用する
選択もありうる。
copyright(c) 2001, ISAC Inc.
2b.制約伝播手法
（Constraint Propagation）
バックトラック可能な探索と整合性維持手
法を組み合わせることにより、効率がよく
かつ完全な解探索が可能になる。
整合性維持手法の適用の仕方から、以下
の2種に大別できる。
知的後戻り（すでに付値された変数が対
象）
先読み（これから付値される変数が対象）
copyright(c) 2001, ISAC Inc.
知的後戻り
単純なバックトラックとの相違は、矛盾の
原因となる変数の付値まで一気に戻る点
にある。(intelligent backtracking,
backjumping)
矛盾が発生した場所を記憶することで、無
駄な検査が繰り返されることを防ぐ手法も
ある。(backmarking)
copyright(c) 2001, ISAC Inc.
先読み
先読みの対象により、さらに以下のように
分類される。
Forward Checking（FC）：付値されたばか
りの変数と、その変数と関係のある、まだ
付値されていない変数の間のみ検査。
Look Ahead(LA)：まだ付値されていない変
数どうしも含めて整合性検査をやり直す。
copyright(c) 2001, ISAC Inc.
3.探索戦略・最適化
探索戦略
全域探索について、変数の選択順序、値
の選択順序を制御することにより効率化し
たり、最初に求まる制約充足解の傾向を
誘導したりすることが可能。
汎用的なヒューリスティクス。
Fast Fail Principle：矛盾が検出された場合
の枝刈りの効果が大きい変数を選択。（要
素数が少ない。制約が多い。etc.）
copyright(c) 2001, ISAC Inc.
探索制御手法
完全性が不要で全域探索にこだわらない
のであれば、様々な探索制御手法を利用
できる。
局所探索：山登り・min-conflict
局所探索の改良：random-walk, tabu
search, simulated annealing, etc.
遺伝的アルゴリズム(GA)
copyright(c) 2001, ISAC Inc.
最適化
分枝限定法(Branch & Bound)法を制約を
用いて実現する方法が一般的。
厳密な最適化と近似的な最適化。
実用的なアプリケーションの場合、目的関
数を定義することが困難な場合もある。
制約プログラミングでは、最適化処理を後
から追加することは比較的簡単。（制約の
追加＋探索制御の追加。）
copyright(c) 2001, ISAC Inc.
未知の技術
海外に比較しても、日本国内での制約プロ
グラミング技術の知名度は低い。
制約プログラミングツールは日本では苦戦。
一部の研究者、スケジューリングなどの業
務エキスパートなどしか知らない。
知っている人の評価は、実用性等の点に
ついても決して低くない。
copyright(c) 2001, ISAC Inc.
何が良くないのか？
AIブームの反動？
制約処理系の開発の中心がヨーロッパであって、
アメリカではない？
スケジューリング・要員計画は得意分野だが、解
法としては強力なライバルがある？
宣言性や論理的な完全性はネックになることも
ある？
柔軟な探索ができない？→縦形探索＋クロノロ
ジカルなバックトラックという標準的に実装される
探索方法の問題。
copyright(c) 2001, ISAC Inc.
主な自社開発事例
生産計画（継手・住宅外壁・バスコア・フィルム切断/
生産、etc.）
屋根パネル積載計画（生産・施工も含む）
屋根パネル分割（設計支援）
工事計画
配車計画
アルバイト勤務計画
運転者運行割付
生産計画パッケージエンジンOEM供給
copyright(c) 2001, ISAC Inc.
4.事例（１）
屋根パネル積載計画システム
copyright(c) 2001, ISAC Inc.
問題
屋根パネルをトラックに積載する計画。
どのように複数のトラックに分載するか。
どのような順序で積載するか。
2階
トラック１
6
5
4
1階
トラック２
3
2
1
copyright(c) 2001, ISAC Inc.
10
9
8
7
計画作成の目標①
輸送時のパネルの破損を防止し、かつ施工現場
の作業が行いやすい順序に積載する。
制約条件の例
②
①
軒先の突起は交互に
copyright(c) 2001, ISAC Inc.
棟違い下優先
制約条件の例
軒先の突起は交互に積む。
棟違い下側のパネルを上に積む。
天窓・太陽電池などの付属品付きパネル
は山の一番上。
長いパネルの下に短いパネルは置けない。
施工作業動線は短いほうがよい。
etc.
copyright(c) 2001, ISAC Inc.
計画作成の目標②
トラックの台数はできるだけ少なくしてコストを削
減する。
階混載しない＝トラック3台階混載する＝トラック2台
例）8段積み
2階：10枚
1階：6枚
copyright(c) 2001, ISAC Inc.
システム化の目的
屋根パネル積載計画を自動的に作成することに
より、省力化を図る。
人手での作業では、
熟練が必要。
時間がかかる（最大10～15分／邸）。平均5分とし
て150邸／週の計画を週一度作成するので、1人
日では作成できない。確認作業も含めると2~3日
必要。
ミスが発生する可能性がある。
copyright(c) 2001, ISAC Inc.
システム化の条件
基本的に全自動。バッチ処理。
人間は結果の確認のみ。
ＰＣ上で、一回の立案で最大150邸前後の処理
ができること。確認も含めて1日で完了。
商品のタイプの増加を考慮する。
順序決定の条件の変化に対応しやすい枠組み
が必要。
copyright(c) 2001, ISAC Inc.
開発経過・運用状況
対応製品を拡大しながら、条件の変更に対応。
第１次（1996.09～1996.10）
第２次（1996.12～1997.01）対応製品追加
第３次（1997.03～1997.04）ルール変更
第４次(1997.06～1997.07)ルール変更
第５次(1997.09～1997.10)ルール変更
第６次(1998.01～1998.02)対応製品追加
第７次(1998.11～1998.12)対応製品追加
第８次(1999.07～1999.09)ルール変更
第９次（2000.01～2000.06）対応製品追加
現在も各生産拠点で運用されている
copyright(c) 2001, ISAC Inc.
速度および品質の評価
（例）第３次開発リリース版の評価結果
邸数561（type A 34邸、B 471邸、C 52邸、D 4邸）。
トラック１台の最大積載段数は6,7,8段の３通り。
所要時間約12分/561邸：１邸あたりの所要時間は数
秒。(133MHz Pentium, 48Mbyte Memory, WindowsNT 3.51)
トラック台数に関しては99%の邸で最適解。
できれば満たしていた方が望ましい条件も95%の邸
で実現。
copyright(c) 2001, ISAC Inc.
開発のポイント
適切なモデル化
規模、制約条件、システム化条件に応じたモデル構
築→制約プログラミングについてのノウハウが必要。
フィージビリティ・スタディ→制約プログラミングではプ
ロトタイピングが容易なので、行いやすい。
実装のノウハウ
好ましい解を妥当な時間で得るためのノウハウが不
可欠。
実データを用いたチューニングにより検証・品質向上
を図る必要がある。
copyright(c) 2001, ISAC Inc.
チューニングの効果
チューニングは実装方式の検証・品質の向上の
ために不可欠。
チューニング環境整備について、お客様のご協力を
いただいている。（現在約1000邸のデータが利用可能。）
成果の例
第１次開発チューニング：解品質が約8%向上。
第２次開発チューニング：探索効率が約10倍向上。
第３次開発チューニング：解品質が約5%向上。
copyright(c) 2001, ISAC Inc.
5.事例（２）
屋根パネル分割システム
copyright(c) 2001, ISAC Inc.
問題
屋根面をパネルに自動的に分割する。
開口の有無・位置や、隣接屋根面の形状
により、分割位置が決まる。
パネルのサイズの上限・下限・標準サイズ
などの条件がある。
パネルの枚数・パターンの異なり数など、
幾つかの最適化条件がある。
copyright(c) 2001, ISAC Inc.
システムの目的
グリッド単位の自由なプランに対して、基本的に
自動的なパネル分割を行うシステムを目指す。
基本的な規則の適用によって多様なプランに対
応できるシステムを目指す。
パネル分割方式についての設計支援シミュレー
ターとして利用できるようにする。
copyright(c) 2001, ISAC Inc.
システム設計上の前提
射影平面（屋根伏せ図）上での問題として解く。
屋根パネルの分割は、原則として軒線に対し
て垂直にのみ行う。
相互に隣接する屋根面間の対称性を考慮する。
問題の規模は邸の大きさに依存する。
copyright(c) 2001, ISAC Inc.
庇を含めた実際の軒線
屋根基準線
ユニット境界
copyright(c) 2001, ISAC Inc.
モデル化
①線分分割問題として定式化
１つの屋根面を属性を持った点により構成される１本の
射影線分として表現することができ、屋根パネル配置問
題は、この線分の分割の問題として扱うことができる。
分割についての条件として、以下のものが考えられる。



点の属性による分割についての制約条件、優先度などが定義さ
れる。
積載・施工・性能などの条件により制約条件、優先度などが定義
される。
巨視的なさまざまな最適化条件が与えられるため、問題は、制
約最適化問題として定義される。
copyright(c) 2001, ISAC Inc.
例）
分割対象の線分
優先分割点
分割禁止点
最大巾
標準巾
積載・施工・性能等の条件
最小巾
copyright(c) 2001, ISAC Inc.
モデル化
②問題変数の表現
線分を構成する点を変数とする。
変数の領域は２値で、意味はその点で分割をす
る／しない、となる。
評価用に適合度を点単位に導入する。
それ以外に、最適化条件によって目的関数を表
現する変数は導入する。
copyright(c) 2001, ISAC Inc.
モデル化
③点の属性の構造
線分を構成する点の属性。
例）
棟線属性：山（＝隣接屋根面）／壁当たり／バルコニー当た
り／棟違いetc.
 棟線Ｘ座標・Ｙ座標・傾き（傾き／変化点（微分不可能））
 軒線属性：けらば／谷etc.
 軒線Ｘ座標・Ｙ座標・傾き（傾き／変化点（微分不可能））
 開口：種別（トップライト／バルコニー開口／ド－マ－）・中／
端／外
 庇の長短

copyright(c) 2001, ISAC Inc.
例）自屋根面 ID：3
棟属性
1
1
*
2
2
2
w
w
w
w:壁当り 1,2:隣接面 *:変化点
棟座標
$
+
*
0
0
0
0
0
0
$:端点 *:変化点、+,0:傾き
開口
-
-
-
0
+
0
-
-
-
+:中 0:端 -:外
軒属性
0
0
0
0
0
0
0
*
4
0:軒 4:隣接面 *:変化点
軒座標
$
0
0
0
0
0
0
*
+
$:端点 *:変化点 +,0:傾き
copyright(c) 2001, ISAC Inc.
モデル化
④隣接屋根面（複数線分）間制約
隣接は棟線を介した関係（軒線が谷属性を持っ
ている部分の対称性は考慮しない。）
谷なので対象外
copyright(c) 2001, ISAC Inc.
モデル化
⑤制約条件
個別の制約条件については追加・削除を随時行っ
て調整していく。（設計支援シミュレーション）
例）






構法上の条件
開口の条件
輸送条件（道路交通法・積込問題上の制約条件）
施工条件（吊り下げ回数、据え付けの容易性など）
原板サイズ（歩留まり）などの生産条件
断熱性能などの性能条件
copyright(c) 2001, ISAC Inc.
モデル化
⑥最適化条件
下記の例のような条件につき、優先度づけを行って、
最適化の目的関数を構成する。優先度づけは、
評価を行いながら、変更していく。
例）





隣接屋根面での対称性
枚数
パネル形状数
パネル種類数（寸法・属性含む）
標準パネル出現率最大
copyright(c) 2001, ISAC Inc.
モデル化
⑦最適化の方法
最適化にあたって、邸全体ではなく、一部の屋根
面のみ解の改良を行ないたい場合などに対応す
るために、最適化ステップでは、以下のような割
付方法を採用した。
既に得られている解の変更したくない部分のみ、
先に結果を領域変数に割り付けてしまう。
 通常のように制約を設定する。
 残りの部分について、すでに求まっている評価値
を上回るという制約を追加した上で探索を行なう。

copyright(c) 2001, ISAC Inc.
評価・実用化
出現頻度が高いと思われるパターンに基づき、
例題を作成（約300種）。
一括立案実験・評価と切断条件の調整の繰返し
による評価サイクルを実施。すべての例で設計
者の意図を満足していることを検証。
予定通りのスケジュールでリリースし、実用化。
その後、2,3件／年の条件の追加に対応しなが
ら運用を継続。現在も使用中。
copyright(c) 2001, ISAC Inc.
6.まとめ：事例の評価と今後の方向性
copyright(c) 2001, ISAC Inc.
適用事例（１）（２）の評価
顧客のCR(Cost Reduction)効果への開発手法の寄与は
評価されている。
低予算・短いスケジュールでの初期開発、条件の変化を
伴う長期の保守に対する対応力はある
特殊な制約条件への対応力はあり、これがこれまでも今
後も最大の差別化のポイント。
ただし実用的なシステム開発ではチューニングが必要で
あり、受託開発向け。
開発スキルについても、比較的短期間で習得可能。ただ
し、上手く使いこなすためには経験の蓄積が必要。
copyright(c) 2001, ISAC Inc.
制約プログラミングの限界
問題の規模が大きくなると、H/W条件等の制約
もあり、制約プログラミングの利用は限定的に。
結局は伝播計算量の増大や、探索における組合
せ爆発が発生：大規模な問題を標準的な制約プ
ログラミング手法のみで解くことは不可能。
最適化ではヒューリスティクスは必須。
実務だからむしろ使いこなせている？
柔軟な最適化を行なうには探索手法や制約の適
用のタイミング・範囲について工夫が必要。
copyright(c) 2001, ISAC Inc.
どのように使えばよいか
問題のモデル化の道具として使える。
制約の追加・削除レベルの変更は容易。
試行錯誤を伴う、プロトタイピング方式の
開発向き。
実用的な観点からは、ヒューリスティクスの
検討・検証が重要。
他のパラダイムとの共存を考えるべき。
copyright(c) 2001, ISAC Inc.
まとめ
ー制約プログラミングは計画系システム開発に役立つか？－
制約プログラミングにより、他の手法では解決困難であっ
た問題をシステム化できる可能性がある。
制約プログラミングを使いこなすには、「まだ」ノウハウが
必要。
大規模システムへの適用には、OR等の他の手法との融
合が必須。
狭義の制約プログラミングでは、組み合わせるにあたっ
ての工夫が必要。
広義の制約パラダイムは、様々な手法を統合するプラッ
トフォームとして期待できる。
copyright(c) 2001, ISAC Inc.
調査研究のためのリソース
（国内）
ISACのWebページの制約処理入門
http://www.isac.co.jp/IZ/
www.constraint.org
淵（監修）・溝口、古川、Lassez（編）「制約
論理プログラミング」（共立出版）
コンピュータソフトウェアVol.9 No.6(1992)
人工知能学会誌Vol.12 No.3(1997)
石塚「知識の表現の高速推論」(丸善)
copyright(c) 2001, ISAC Inc.
調査研究のためのリソース
（海外・主要なもののみ）
Constraint Archive
http://www.cs.unh.edu/ccc/
Guide to Constraint Programming
http://kti.mff.cuni.cz/~bartak/constraints/
雑誌：Constraint (Kluwer)
学会：Principle & Practice of Constraint
Programming (CP)
商用：ILOG S.A. http://www.ilog.com/
copyright(c) 2001, ISAC Inc.

Download Report