Chapter 1. OptaPlanner イントロダクション

1.1 OptaPlanner とは何ですか？

OptaPlanner は、計画問題の最適解を得る、組み込み可能で軽量な制約充足エンジンです。 次のようなユースケースを解きます。

従業員シフト勤務計画: 看護師や修理工などの勤務表作成
実施スケジューリング: 会議, 設備, メンテナンス作業, 広告などのスケジューリング
教育時間割り: 授業, 講座, 試験, 会議プレゼンテーションなどのスケジューリング
輸送経路計画: 荷物および／または人を乗せた乗り物 (トラック, 列車, 船舶, 飛行機など) の計画
箱詰め（ビンパッキング）: コンテナ, トラック, 船舶への積載や倉庫への保管, さらにはクラウドコンピュータのノードなども
注文生産スケジューリング: 自動車組立ライン, 機械処理, 人員作業などの計画
在庫削減: 紙や鋼, カーペットなどの切断で生じる無駄の最少化
スポーツにおけるスケジューリング: フットボールや野球などのリーグ戦計画

あらゆる組織が計画問題に直面しています。製品やサービスは、制約を受け 、限定されたリソース (従業員, 資産, 時間, 金) を使って提供されています。OptaPlanner は、そのような計画を最適化することによって、より少ないリソースでより多くの業務を実行できるようにします。これは、オペレーションズリサーチ 分野の一つである 制約充足プログラミング として知られています。

OptaPlanner の助けがあれば、普通の Java™ プログラマーでも制約充足問題を効率よく解くことができます。OptaPlanner の内部では、最適化のためのヒューリスティック法およびメタヒューリスティック法が非常に効率的なスコア計算と組み合わされています。

1.2. 必要なもの

OptaPlannerは、Apache ソフトウェアライセンス 2.0の下で配布される オープンソース・ソフトウェア です。このライセンスは、非常に進歩的で、商用目的での再使用を許可しています。一般向け説明に目を通してください。

OptaPlanner は、100% 純粋に Java™ で作られており、バージョン 1.6 以上のすべての JVM 上で動作します。他の Java™ 技術との統合は非常に簡単です。OptaPlanner は、Maven Central Repositoryで利用できます。

1.3. 計画問題とは？

1.3.1. 計画問題は NP 完全または NP 困難

上に挙げたユースケースはすべて、おそらく 、NP 完全もしくはそれよりも困難な問題です。NP 完全とは、普通の言葉で表現すると次のような意味です。

問題の解を、簡単に、適度な時間内に検証できる。
問題の最適解を適度な時間内に見つける確実な方法がない(*)。

注意

(*) 少なくとも、世界中の頭の切れるコンピュータ科学者でさえ、まだ誰もそのような確実な方法を見出せていません。しかし、誰かが 1 つの NP 完全問題について解を一つ見つけたとしたら、その解はすべての NP 完全問題に当てはまることになります。実際、そのような確実な方法が実在するかどうかを証明した人には 100 万ドルの懸賞金が与えられることになっています。

これは実に恐ろしいことを示唆しています。つまり、次の 2 つの一般的な方法が力不足であるために、自分の抱える問題を解くのが、おそらくは想像以上に困難だということです。

総当たりアルゴリズムは、時間がかかりすぎる。（たとえ巧妙に作った変種であっても。）
速成のアルゴリズムは、例えば箱詰め（ビンパッキング）において Largest First 法に従って物を入れる アルゴリズムのように、最適解からはほど遠い解を返してしまう。

OptaPlanner は、先進的な最適化アルゴリズムを使用することによって、そのような計画問題に対して、適度な時間内に良い解を見つけ出します。

1.3.2. 計画問題には制約がある（ハード, ソフト制約）

計画問題には、多くの場合、少なくとも次のような 2 つの水準の制約があります。

ハード制約 (負値) は、違反してはならない。例: 1 人の先生が異なる 2 つの授業で同時に教えることはできない。
ソフト制約 (負値) は、避けられる限り、違反してはならない。例: 先生 A は、金曜日の午後に教えたくない。

次のように、正値の制約を持つ問題もあります。

可能な限り、正値のソフト制約 (または報酬) が満足されなければならない。例: 先生 Bは、月曜日の朝に教えたい。

基本的な問題 (例えば N Queens 問題) には、ハード制約のみ持つものがあります。ハード制約, ミディアム制約, ソフト制約といったように、3 つ以上の水準の制約を持つ問題もあります。

これらの制約によって、各問題の スコア計算方法 ( AKA 適合度関数 ) が定義されます。一つの問題の複数の解それぞれにスコアを与え、解の優劣を付けることができます。OptaPlanner のスコア制約は、Java コードのようなオブジェクト指向言語または Drools ルールによって記述されます。 それらのコードは、簡単で、柔軟性と拡張性を有しています。

1.3.3. 計画問題は巨大な探索空間を持つ

一つの計画問題には多数の解が存在します。解にはいくつかの種類があります。

可能解 (possible solution) は、違反する制約の数を問わずに挙げられるすべての解です。計画問題には、膨大な数の可能解を持つ傾向があります。その解の多くに価値はありません。

実行可能解 (feasible solution) は、ハード制約 (負値) を一つも違反しない解です。実行可能解の数は、可能解の数と相関を持つ傾向にあります。実行可能解が存在しない場合もあります。すべての実行可能解は可能解です。
最適解 (optimal solution) は、最高スコアを持つ解です。計画問題には、1 つから数個の最適解を持つ傾向があります。実行可能解が存在せず、最適解が実行可能でない場合であっても、少なくとも 1 つの最適解は必ず存在します。
最善解 (best solution found) は、与えられた時間内での実行結果に見出される、最高スコアを持つ解です。見出された最善解は、実行可能である場合が多く、時間が十分に与えられる場合には最適解となります。可能解の数は、(もしも正確に計算するとしたら、) たとえデータセットが小さくとも、直感に反して膨大になります。サンプルで確認できるように、ほとんどのケースで、既知の宇宙に存在する原子の数の最小値 (10⁸⁰) よりもずっと多くの可能解があります。その最適解を確実に見つけられる方法が存在しないため、いかなる実行方法も、そのすべての可能解の部分集合だけを評価することしかできません。

OptaPlanner は、複数の最適化アルゴリズムを備えており、そのような膨大な数の可能解を効率的に処理します。ユースケース次第で、ある最適化アルゴリズムが他のものよりも良好な性能を示すことがありますが、そのことを事前に知ることは不可能です。OptaPlanner なら、最適化アルゴリズムを簡単に切り換えられます。 XML またはコードの中のソルバ設定を数行書き替えるだけです。

1.4. サンプルのダウンロードと実行

1.4.1. 公開 .zip の入手とサンプルの実行

今すぐやってみましょう。

1. OptaPlanner ウェブサイトから OptaPlanner の公開 .zip をダウンロードします。

2. 解凍します。

3. *examples* ディレクトリを開き、スクリプトを実行します。

Linux または Mac:

$ cd examples
$ ./runExamples.sh

Windows:

$ cd examples
$ runExamples.bat

distributionZip

サンプル GUI アプリケーションが開きます。サンプルを一つ選択してください。

注意

OptaPlanner 自体は GUI に対して依存性を持ちません。OptaPlanner は、デスクトップ上とまったく同様に、サーバやモバイル JVM 上でも動作します。

1.4.2. IDE (IntelliJ, Eclipse, NetBeans) でのサンプルの実行

自分の好みの IDE でサンプルを実行するには次のようにします。

1. IDE を設定します。 * IntelliJ IDEA と NetBeans では、*examples/sources/pom.xml* を新しいプロジェクトとして開きます。そうするだけで、残りは Maven が統合してくれます。 * Eclipse では、ディレクトリ *examples/sources* について新しいプロジェクトを開きます。ファイル *examples/binaries/optaplanner-examples-_version_.jar* を除く、ディレクトリ *bineries* および *examples/binaries* に含まれるすべての jar をクラスパスに追加します。 Java ソースディレクトリ *src/main/java* と Java リソースディレクトリ *src/main/resources* を追加します。

2. Run 設定を作成します。 * メインクラス: org.optaplanner.examples.app.OptaPlannerExamplesApp * VM パラメータ (オプション): -Xmx512M -server

3. この Run 設定を実行します。

1.4.3. OptaPlanner を Maven や Gradle, Ivy, Buildr, ANT とともに使う

OptaPlanner の jar は、Maven Central Repository でも利用できます。（JBoss Maven Repository でも利用できます。）

Maven を使う場合は、以下のように、プロジェクトの *pom.xml* で optaplanner-core に依存性を追加してください。

    <dependency>
      <groupId>org.optaplanner</groupId>
      <artifactId>optaplanner-core</artifactId>
    </dependency>

これは、Gradle, Ivy, Buildr についても同様です。最新版は、Maven Central Repository で確認してください。

他の OptaPlanner モジュールも使用することになる可能性があるため、以下のように、Maven の dependencyManagement で optaplanner-bom をインポートすることを推奨します。こうしておくと、OptaPlanner のバージョン指定は一回だけで済みます。

  <dependencyManagement>
    <dependencies>
      <dependency>
        <groupId>org.optaplanner</groupId>
        <artifactId>optaplanner-bom</artifactId>
        <type>pom</type>
        <version>...</version>
        <scope>import</scope>
      </dependency>
      ...
    </dependencies>
  </dependencyManagement>

まだ (Ivy なしで) ANT を使用している場合は、ダウンロードした zip 内のディレクトリ *binaries* にあるすべての jar を自分のクラスパスにコピーします。

注意

ダウンロードした zip 内のディレクトリ *binaries* には、optaplanner-core が実際に使用するよりもはるかに多くの jar を含まれています。optaplanner-benchmark など他のモジュールが使用する jar も含まれています。

Maven リポジトリの *pom.xml* ファイルを確認し、(特定のバージョンのための) 特定のモジュールについて、最小の依存性セットを決めてください。

1.4.4. OptaPlanner をソースからビルドする

OptaPlanner をソースからビルドするのは簡単です。

1. Git を設定し、GitHub からの clone optaplanner を実行します。(または、zipball をダウンロードします。)

$ git clone git@github.com:kiegroup/optaplanner.git optaplanner
...

注意

GitHub アカウントを持っていない場合や、ローカルの Git インストール設定がそのアカウントでなされていない場合は、代わりに次のコマンドを使用して認証問題を回避してください。

$ git clone https://github.com/kiegroup/optaplanner.git optaplanner
...

2. Maven を使ってビルドします。

$ cd optaplanner
$ mvn clean install -DskipTests
...

注意

Maven の初回は、jar をダウンロードする必要があるため、時間がかかるかもしれません。

3. サンプルを実行します。

$ cd optaplanner-examples
$ mvn exec:exec
...

4. 好みの IDE でソースを編集します。

5. オプション: Java プロファイラを使用します。

1.5. 管理・運営

1.5.1. OptaPlanner のレベルの高さ

OptaPlanner が持つ特長:

安定性: ユニットごとのテスト, 統合環境でのテスト, ストレステストによって非常によくテストされている。
信頼性: 世界中で、製品で使用されている。
スケーラビリティ: サンプルの一つでは、50000 個の変数が扱われ、その 5000 個ごとに、複数の種類の制約とそれを満たす何億ものパターンが扱われている。
整備された文書: 詳細な本マニュアルや多くのサンプルの一つを見てください。

1.5.2. 後方互換性

OptaPlanner では、API と実装が分離されます。

パブリック API: パッケージ名前空間 *org.optaplanner.core.api* は、将来のリリースにおいて、100% の後方互換性を有します。
Impl クラス: パッケージ名前空間 *org.optaplanner.core.impl* にあるすべてのクラスには、後方互換性がありません。将来のリリースにおいて変更される可能性があります。UpgradeFromPreviousVersionRecipe.txtと呼ばれるレシピには、新しいバージョンにアップグレードする場合の、各変更内容およびその変更にすばやく対処する方法が記述されています。
XML 設定: XML ソルバ設定は、非パブリック API クラスを使用する必要のある要素を除くすべての要素について、後方互換性を有します。XML ソルバ設定は、パッケージ名前空間 *org.optaplanner.core.config* にあるクラスによって定義されます。

注意

本説明書では、impl クラスもいくつか扱われています。それら文書化された impl クラスは、(本説明書で実験的なものだと明記されない限り) 信頼性があり、安全に使用できます。ただし、それらは、確定的に記述するにはまだ時期尚早なものだと私たちは考えています。

1.5.3. コミュニティとサポート

ニュースや記事は、私たちのブログや Google+ (OptaPlanner, Geoffrey De Smet)、Twitter (OptaPlanner, Geoffrey De Smet) で確認してください。OptaPlanner が役に立った場合には、そのことについてブログに書いたり Twitter でつぶやいたりして、私たちをご支援ください！

私たちのコミュニティーの公開フォーラムでの質問や課題トラッカーでのバグ報告、機能要望を歓迎します。GitHub への pull 要求を大いに歓迎し、優先的に扱います！ご自身の改善をオープンソース化すれば、それに対して私たちが加える専門的なチェックやさらなる改良をご自身のために役立てることができます。

Red Hat は、中核となるチームを雇用する形で、OptaPlanner の展開を後援しています。企業向けのサポートやコンサルティングについては、BRMS および BPMS 製品 (含 OptaPlanner) を参照するか、Red Hat へお問い合わせください。

1.5.4. Drools や jBPM との関係

OptaPlanner は、KIE プロジェクト・グループの一部です。KIE グループは、Drools ルールエンジンと jBPM ワークフローエンジンとともに、定期的に (通常 1〜2 回/月) リリースされます。

Drools を用いたオプションの統合についてより多く知るには、構造の概要を参照してください。