株式会社NTTデータセキスイシステムズ

NTT Data

制約プログラミング入門


はじめに

制約プログラミングとは、「制約条件を満たす答えを 探して見つけ出す問題」を解くための手法・考え方の枠組みです。
この手の問題は「制約充足問題(ConstraintSatisfactionProbrem)」とも呼ばれています。

システム開発を手掛けていますと、様々な分野で制約充足問題に遭遇します。
特に、プラニングや生産スケジューリング、資源割当(ResourceAllocation)といった計画系システムでは、必ずといって良いほど制約充足問題を解く要件が出てくるので、避けては通ることはできません。
制約充足問題を解くには様々な手法が考案されていますし、また各々得手不得手もあるでしょう。制約プログラミングもその例外ではありません。
その考え方全てをWebページで書き尽くすのは無理なことではありますが、雰囲気だけでも掴んで頂けるようご紹介したいと思います。

ページの先頭へ

制約充足問題

例えば、時間割を作成する場合を思い浮かべてみてください。

最終的に必要(つまりこの問題の解)なのは、全クラスの時限枠に教科が埋まった表です。
これは例えば、クラス毎に時限枠の配列を持ち、配列の値として教科を与えるといった定式化 をすれば、プログラミングで扱えるようなモデルに落とし込むことができます。
さらに、同時に各時限の担当教師も決めないといけないですから、各教師毎の配列 (値は担当するクラス)も必要になります。

次に制約条件としては、まず、

  • 各学年、各教科毎に1週間の時限数(上下限?)
  • 各学年、各教科毎に担当可能な教師
  • 各教師の1週間の担当時限数(上下限?)

などが決まっている、というのがあるかと思います。
また、人が考えるなら当たり前のことですが、プログラムを書く上では 忘れてはならない制約があります。

  • 1人の教師は同じ時限に複数の授業は担当できない
  • 1つのクラスで、同じ時限に複数の授業はできない
  • ある教師が担当する「時限、クラス、教科」の組合せと、 あるクラスの「時限、教科、教師」の組合せは一致しないといけない

さらに、可能な限りそうあって欲しいという、 言わば答えの評価基準になるような、制約に準ずる条件もあります。

  • クラスでみた場合、可能な限り同一教科を同じ日に重ねない
  • 教師でみた場合、可能な限り担当時限数、時間帯(午前・午後)を公平にする

こういった希望的制約は、他にもまだまだ考えられると思います。

以上のような制約条件に違反することなく、 各クラスの時間割の枠に教科が埋まった状態、
それがこの制約充足問題(時間割作成)の解となる訳です。

目的は、もちろんその解を求めるプログラムを書くことですが、 この手の問題では、答えがどうあって欲しいかを規定しているだけで、 答えの求め方に決まったアルゴリズムがある訳ではありません。 ですので、制約条件を手掛かりに良さそうなアルゴリズムを考えて 答えを導かなければなりません。

さらに悪いことに、良さそうなアルゴリズムに決めたとしても、 制約条件が複雑に絡み合っているため、 次回も同じアルゴリズムで、制約を違反しない答えが得られる保証がないのです。 僅かに条件が変わった(例えば、ある学年の1週間の国語の授業数が1増えた) だけで、全く答えが出なくなるというのは、この手の問題では当たり前のことです。

ということは、どういったアルゴリズムで答えを求めるべきか自体、入力データが 決まった段階でやっと考え始めることができるということになります。

これはプログラマにとっては大変な負担です。なにしろ、 問題を解くためのアルゴリズムを考えるプログラム[*1]を 作らなければいけないのですから。

それでは大変なので、もっと簡単なやり方としては、 とにかくまず答え(というか答えになりそうなもの)を次々に生成し、 それを制約条件で検査して、条件に違反してないものが見つかるまで虱潰しに探す[*2]、 という方法もあります。

ただこの方法は、問題の大きさ(クラスや教師、教科、条件付制約条件の数など)によって、 答えを探す範囲が急速に大きくなります。ですので、なにか探し方の工夫[*3]を してやらないと全く答えまで辿り着けなくなります。

ページの先頭へ

制約プログラミング

制約プログラミングには、

  • 制約条件と探索戦略の分離により、[*1]を作る負担を軽減する
  • 制約伝播の技法により、[*3]の工夫をして[*2]を高速化する

という2つの大きな側面があります。

後者の制約伝播については次章で説明します。本章では前者の特徴と、 それに関連して制約プログラミングの設計方法論をご紹介します。

制約の宣言的記述

制約プログラミングでは、まず制約条件を宣言的に記述します。 その上で、条件を満たす答えを見つけ出すといった方法を採ります。 答えを探すときに制約条件を自動的にチェックする仕掛けがあるので、 このような方法が採れるのです。

制約の記述というのは、先の時間割作成の例をご覧になれば判るとおり、 与えられた問題そのものですから、

  • 解くべき問題を宣言する
  • 答えを探す

の2つのフェーズに分けて考えていると言い換えることもできます。
このように、制約条件と探索戦略を分離すると、

  • 如何に高速に解に到達するかに特化して、探索戦略を考えることができる
  • 問題に則したプロトタイピングが可能
  • (実装する制約条件を減らすことでプロトタイプを作成するのではなく、 入力データに対する汎用性を落とすことでプロトタイプを作成できる)

といった利点が、実際のシステム開発において現れてきます。

制約プログラミングにおける開発工程

まず、現実の問題に対して制約プログラミングを適用するところまで 分解するために、モデリングという設計工程を実施します。

モデリングの段階で、システムの目標決定や問題の定式化を行い、 制約プログラミングの手法が適していることがわかったならば、 プロトタイピングによる設計/実装の段階に入ります。

制約プログラミングにおける設計は次の3点に分解できます。

  • 変数の決定
  • 制約の記述
  • 探索戦略の決定

プロトタイプ作成の段階では、このうち上記2つを実施し、 典型的なデータセットに対して要件を満すことができることを検証します。
汎用的な探索戦略の決定は最後のチューニング段階で行います。

ところで実際の問題では、「制約条件」として提示された 関係に強弱、優先順位が出てきたり、応答時間の制限から 単に可否を判定する制約として扱えない場合が多くあります。

そこで、

  • 強い制約(絶対的な制約)は制約伝播の技法で
  • 弱い制約(条件つき、解の評価基準)は
    • 探索戦略の中にプログラムする
    • 解の評価基準としての目的関数として実装する
    • 強い制約として実装し、可能解が得られるまで緩和する

などの方法を検討しながら設計します。

制約の記述方法が決定し、プロトタイプによる検証が終了すると、 チューニングの段階に移ります。

チューニングでは、可能な限り多くの実データを用いて検証しながら、 入力に対する汎用性(妥当な結果が得られる範囲)や処理時間性能を 高めるための探索戦略を決定していきます。

ページの先頭へ

制約伝播

制約伝播とは、問題を解くための探索空間を小さくする工夫の一つです。

制約プログラミングでは、解くべき対象を「取り得る値の範囲(=ドメイン)」を持つ 変数の組で、制約条件をそれら変数間の関係式で表現します。

そうした上で、計算中に明らかになる個々の変数の変化を、制約を介して関係する変数に 伝えることで探索空間を小さくし、解探索の高速化を狙っています。

制約伝播の仕組み

最も単純な例として「鶴亀算」を使って、制約伝播の仕組みを説明します。

鶴亀算では、鶴の数(X)、亀の数(Y)の2つの変数の組[X,Y]が解くべき対象となります。 ここでは、鶴、亀とも0〜99の範囲の値を取ることにしましょう。

変数の組[X,Y]
とり得る値の範囲(ドメイン)
X:0..99
Y:0..99

これを、先の[*2]の方法で解くことを考えます。全く工夫なしに探した場合、 [X,Y]=[0,0],[0,1]...[99,99]のと1万通りの組合せから探すことになります。

制約プログラミングではここで制約を記述します。鶴亀算の制約とは、

  • 頭の数の合計が決まっている
  • 足の数の合計が決まっている

の2つです。

制約(変数間の関係)
X+Y=16...頭の数の制約(1)
2X+4Y=44...足の数の制約(2)

ここまで記述したところで実行してみることにします。
プログラム実行時には変数の初期化に続いて制約を評価します。
制約の評価とは、変数各々のとり得る値を制約を介して伝え合い、 明らかに制約に反する値を取り除く(制約の一貫性チェック)ことです。
一貫性チェックには様々な理論・実装方法がありますが、ここでは X,Y各々の上限値、下限値をチェックする方法だとします。

制約の一貫性チェックにより、関係している各変数のとり得る値の範囲が 小さくなる場合があります(ドメイン縮小)。
すると、ドメイン縮小を引き金に、直ちにその変数が関係している 他の制約を活性化し、再評価します。
さらに、新たに活性化した制約に関係する他の変数についても、 ドメインの縮小が起き、さらにまたその変数が関係している 他の制約を活性化します。

といった具合に、制約の再評価とドメインの縮小が繰り返されることになります。 これが制約伝播です。

鶴亀算の例で制約伝播の動きを追ってみると、

XY
0..990..99
X+Y=16頭の数の制約(1)を評価
0..160..16
X*2+Y*4=44さらに足の数の制約(2)を評価→Yのドメイン縮小→制約(1)を活性化
0..163..11
X+Y=16Yが関係する他の制約(1)を再評価→Xのドメイン縮小→制約(2)を活性化
5..133..11
X*2+Y*4=44Xが関係する他の制約(2)を再評価→Yのドメイン縮小→制約(1)を活性化
6..125..8
X+Y=16…以下同様…
8..115..8
X*2+Y*4=44
8..106..7
X+Y=16
9..106..7
X*2+Y*4=44→X:10,Y:6

何と、制約を記述しただけで探さなくても答えがでてしまいました。鶴亀算のような単純な例ですとこういうこともあります。
例えば右図のような不等式であれば、答えまでは出ませんが、それでも探索空間は、最初より遥かに小さくなります。

なお、制約伝播の技法では次のことを保証します。

  • 制約伝播は必ず停止する
  • 制約伝播は必ずドメインが縮小する方向に働く
  • 制約伝播を実施する順序は結果に影響しない
探索時の制約伝播

鶴亀算の例では制約を書いただけで終わってしまいましたが、実際の問題では、 伝播が発生した後ある程度の探索空間を残して停止するのが普通です。

その場合でも制約伝播は答えを探す過程で活きてきます。
解探索とは変数の値を試しに決めてみることですが、変数の値を1つに 決めるということは即ちドメインの縮小ですから、制約伝播が発生します。
この制約伝播によって無駄な値決めが減り、結果として解探索が高速化できます。

ページの先頭へ

制約プログラミング・ライブラリ「iZ」

iZは、有限範囲の整数同士の関係を制約伝播を使って解くための仕掛けです。

iZ-Cでは何が出来るか

iZ-Cは、制約伝播を実装したC言語の関数ライブラリです。
製品情報のページに機能説明があります。

iZ-CのAPIを用いてC言語でアプリケーションを開発することができます。

iZ-Cの応用例:
快決!シフト君
iZ-Cを使ったソフトウェア製品です。
1ヶ月間のシフト勤務計画を自動的に立案します。

ページの先頭へ

制約プログラミング情報

www.constraint.orgでは、制約プログラミングに関する情報を集めています。

ページの先頭へ