制約プログラミング とは

制約プログラミング（CP: Constraint Programming）とは、現実問題を数式に置き換えた場合に、変数間の関係を「制約」という形で記述するプログラミングのことを言います。

その制約を「集合」と考えることで、さまざまな制約を満たす解がどこにあるかを検索するものです。

簡単に例を紹介しましょう。

例）お店の担当者割付をしたい！

• 貴金属店「もってけダイヤ」　では、販売員と警備員を常駐させています。
• 年中無休で頑張ってます。
• 販売員は10名、警備員は15名います。
• 販売員はどんな時間でも最低でも2人、忙しい時は8人態勢にします。
• 警備員は常に3人、忙しい時は7人態勢にします。
• お店の営業時間は10:00～19:00で、1回の連続勤務は4時間までの交代制です。
• 販売員は週休2日はとらなくてはいけません。
• 販売員はお休みを申請できますが、希望どおりにならないこともあります。
• 販売員には、商品を金庫から持って来れる人と、持って来れない人がいます。
• ある販売員とある警備員がペアの場合、都合の悪い出来事が起きます。
• ・・・。

沢山ありますね。これらのことは、「制約」といいます。組み合わせの数からすると、何百万通りもありそうです。しかも、ビジネスとして行う以上、コストを最小にしなければなりません。鉛筆をなめなめしながら、模造紙を使って組み立てていくと、それだけで1か月が過ぎてしまいそうです。

上に戻る

どうやって組み合わせを見つけるのか

制約プログラミングで最初に考える、制約伝播というものを見てみましょう。沢山ある組み合わせのうち、可能性のないもの（＝制約を満たさない領域）をカットしていくことで、目標までの道のりを短くしていきます。

• Xは0から20までの整数をとる。
• Yは0から20までの整数をとる。
• Zは0から20までの整数をとる。

これを絵にすると、下記のようになります。

取りうる組み合わせの数は、20 x 20 x 20 = 8000通りあります。これに、下記の制約を当てはめていきます。

x < y
x + y = z

そうすると、下記の絵のようになります。

• x = 20と y = 0は、x < y という制約を満たしません。
• z = 0 は、x + y = z という制約を満たしません。

この時点で、組み合わせの数は、19 x 19 x 19 = 6,859通りです。

さらに、z = 5 という制約を加えてみると、

x + y = z という制約があるので、z = 5という制約が加わったことでx, yにも制約が加わります。この時点で、組み合わせの数は、5 x 5 x 1 = 25 通りです。だいぶ、範囲が狭まってきました。

では、y = 4という制約をさらに与えてみましょう。

解が見つかりました。x = 1、y = 4、z = 5が、この場合の解になります。

このようにして、とりうる値の範囲を縮小させていくのが、制約伝播という手法になります。実際には制約伝播だけで解を導き出すのは難しいのですが、このように、よい解をすばやく取り出す様々な工夫が、最適化エンジンILOG CPには搭載されています。

上に戻る

制約プログラミングで解決する例

制約プログラミングは、膨大な組み合わせから条件に合うものを選択するような業務に適しています。

• 生産スケジューリング（生産ラインでの組み立て順序の最適化など）
• 巨大構造物の作成スケジューリング（航空機、橋梁など）
• 配送計画（トラックと荷物の割り振りなど）
• 人員の計画（運転士の時間割など）
• 試合日程の計画
• 授業日程の計画

上に戻る

四色定理をILOG CPで解いてみる

隣接する区域を、異なる色で塗り分けるという問題を、ILOG CPを使って書いてみましょう。四色定理とは、いかなる地図も、4色あれば隣接する領域が異なる色で塗ることができるという定理です。これは長い間数学の難問とされていましたが、1978年、アメリカ・イリノイ大学の研究者、ハーケンとアッペルが、大型コンピューターによる計算により証明に成功しました。これを、日本の都道府県を題材にして、ILOG CPで四色に塗り分けてみましょう。

この都道府県に対して、色を塗っていきますが、同じ色が隣り合わせにならないように塗っていきます。この場合の制約は、　

• 北海道の色≠青森の色、
• 青森の色≠秋田の色、青森の色≠岩手の色

のようになります。

では、実際に書いて色分けをしてみましょう。 現在販売しているILOG ODM (Optimization Decision Manager) では、ILOG CPLEX、ILOG CPの両方のエンジンを使用可能です。

まず、ODMでプロジェクトを作成します。

デフォルトの実行構成の追加、モデルの作成にチェックをつけ、終了ボタンをクリックします。

記述するソースは、OPL (Optimization Programming Language)です。ソースを書きますが、まずは最適化エンジンILOG CPを使う と宣言します。

/*********************************************

 * OPL 6.3 Model

 * Author: Masahiko UMENO

 * Creation Date: 2010/06/21 at 15:00:00

 *********************************************/



using CP;

たったこれだけです。Using CPと書かない場合は、最適化エンジンとしてILOG CPLEXが自動的に採用されます。

では、モデルを書いてみましょう。

4色を、それぞれ0、1、2、3という数値に置き換えます。

その4色は、青色、白色、黄色、緑色とします。

range r = 0..3;

string Names[r] = ["blue", "white", "yellow", "green"];

次に、決定変数を設定していきます。Hokkaidoが取りうる値は r値の0～3のうちのどれかになります。

dvar int Hokkaido in r;

dvar int Aomori in r;

dvar int Akita in r;

dvar int Iwate  in r;

dvar int Yamagata in r;

…

決定変数は47都道府県分作ります。

そして、制約をつけます。 これは、隣接する県は同じ色にしない というのを制約として書いていきます。

subject to {  
	Hokkaido != Aomori;　// 北海道は青森と同じ色ではない

	Aomori != Iwate;

	Aomori != Akita;

	Iwate != Miyagi;

	Akita != Yamagata;

	Akita != Miyagi;

	Yamagata != Fukushima;

	Yamagata != Niigata;

書くのはちょっと大変ですが、制約の数は100個になりました。

最後に、実行して結果を表示させるところを記述します。

execute {

	writeln("Hokkaido:",Names[Hokkaido]);

	writeln("Aomori:",Names[Aomori]);

	writeln("Akita:",Names[Akita]);

	writeln("Iwate:",Names[Iwate]);

	writeln("Yamagata:",Names[Yamagata]);

…

（今回記述したソースコードはこちらからダウンロードできます）

では実行してみましょう。

おおお。一瞬で答えが出たようです。

では実際に色をつけてみましょう。

隣接県で同じ色を使わずに色分けできました。（わかりやすくするために、WhiteをGrayにしています。）

これを、人間が考えてやってみると・・・。かなりの時間が掛かるのは簡単に想像できますよね。

ちなみに、三色で色付けしようとしてみると・・・? 是非、読者の皆様がお試しください。

上に戻る

まとめ

いかがでしょうか。最適化エンジンILOG CPは、制約が複雑で膨大な組み合わせから解を導き出すのに有用なエンジンです。現実問題では、制約問題を解くには組み合わせ爆発をいかにして抑えるかがキーポイントになります。 実際の開発局面においては、お客様への導入経験から得た知識を、サービスとしてご提供しております。

また、ILOG CPはILOG CPLEXと組み合わせて使うことで、お互いのエンジンのいいところをうまく生かして問題を解決することが可能です。

上に戻る

ダウンロード

ダウンロード形式について

著者について

この記事を評価する

コメント

上に戻る

目次

• 制約プログラミング とは
• どうやって組み合わせを見つけるのか
• 制約プログラミングで解決する例
• 四色定理をILOG CPで解いてみる
• まとめ
• ダウンロード
• 著者について
• コメント