Toggle navigation OptaPlanner logo
  • Home
  • Download
  • Learn
    • Documentation
    • Videos
    • Slides
    • Training
    • Use cases
    • Compatibility
    • Testimonials and case studies
  • Get help
  • Source
  • Team
  • Services
  • Star
  • @OptaPlanner
  • Fb
Fork me on GitHub

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

1.1. OptaPlanner とは何ですか?
1.2. 必要なもの
1.3. 計画問題とは?
1.3.1. 計画問題は NP 完全または NP 困難
1.3.2. 計画問題には制約がある(ハード, ソフト制約)
1.3.3. 計画問題は巨大な探索空間を持つ
1.4. サンプルのダウンロードと実行
1.4.1. 公開 .zip の入手とサンプルの実行
1.4.2. IDE (IntelliJ, Eclipse, NetBeans) でのサンプルの実行
1.4.3. OptaPlanner を Maven や Gradle, Ivy, Buildr, ANT とともに使う
1.4.4. OptaPlanner をソースからビルドする
1.5. 管理・運営
1.5.1. OptaPlanner のレベルの高さ
1.5.2. 後方互換性
1.5.3. コミュニティとサポート
1.5.4. Drools や jBPM との関係

1.1 OptaPlanner とは何ですか?

optaPlannerLogo

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

  • 従業員シフト勤務計画: 看護師や修理工などの勤務表作成

  • 実施スケジューリング: 会議, 設備, メンテナンス作業, 広告などのスケジューリング

  • 教育時間割り: 授業, 講座, 試験, 会議プレゼンテーションなどのスケジューリング

  • 輸送経路計画: 荷物および/または人を乗せた乗り物 (トラック, 列車, 船舶, 飛行機など) の計画

  • 箱詰め(ビンパッキング): コンテナ, トラック, 船舶への積載や倉庫への保管, さらにはクラウドコンピュータのノードなども

  • 注文生産スケジューリング: 自動車組立ライン, 機械処理, 人員作業などの計画

  • 在庫削減: 紙や鋼, カーペットなどの切断で生じる無駄の最少化

  • スポーツにおけるスケジューリング: フットボールや野球などのリーグ戦計画

useCaseOverview

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

whatIsAPlanningProblem

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

1.2. 必要なもの

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

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

compatibility

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) は、与えられた時間内での実行結果に見出される、最高スコアを持つ解です。見出された最善解は、実行可能である場合が多く、時間が十分に与えられる場合には最適解となります。 可能解の数は、(もしも正確に計算するとしたら、) たとえデータセットが小さくとも、直感に反して膨大になります。サンプルで確認できるように、ほとんどのケースで、既知の宇宙に存在する原子の数の最小値 (1080) よりもずっと多くの可能解があります。その最適解を確実に見つけられる方法が存在しないため、いかなる実行方法も、そのすべての可能解の部分集合だけを評価することしかできません。

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

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

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

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

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

2. 解凍します。

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

Linux または macOS:

$ cd examples
$ ./runExamples.sh

Windows:

$ cd examples
$ runExamples.bat

distributionZip

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

plannerExamplesAppScreenshot
注意

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 回/月) リリースされます。

kieFunctionalityOverview

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

- - - -
Latest release
  • 8.1.0.Final released
    Fri 15 January 2021
Paid support and consulting

Want to talk to the experts? Red Hat offers certified binaries with enterprise consulting. Contact optaplanner-info for more information.

Upcoming events
  • KIE Live
    Worldwide - Tue 19 January 2021
    • OptaPlanner Shadow Variables for the Vehicle Routing Problem and Task Assignment by Geoffrey De Smet, Karina Varela, Alex Porcelli
  • Javaland
    Worldwide - Tue 16 March 2021
    • AI on Quarkus: I love it when an OptaPlan comes together by Geoffrey De Smet
Add event / Archive
Latest blog posts
  • Solve the facility location problem
    Fri 9 October 2020
     Jiří Locker
  • OptaPlanner Week 2020 recordings
    Mon 7 September 2020
     Geoffrey De Smet
  • Let’s OptaPlan your jBPM tasks (part 1) - Integrating the two worlds
    Fri 3 July 2020
     Walter Medvedeo
  • AI versus Covid-19: How Java helps nurses and doctors in this fight
    Fri 8 May 2020
     Christopher Chianelli
  • Workflow processes with AI scheduling
    Tue 5 May 2020
     Christopher Chianelli
  • Constraint Streams - Modern Java constraints without the Drools Rule Language
    Tue 7 April 2020
     Geoffrey De Smet
  • How to plan (and optimize) a Secret Santa
    Wed 18 December 2019
     Christopher Chianelli
Blog archive
Latest videos
  • YT Shadow variables
    Tue 19 January 2021
     Geoffrey De Smet
  • YT Domain modeling and design patterns
    Tue 17 November 2020
     Geoffrey De Smet
  • YT Quarkus insights: AI constraint solving
    Tue 20 October 2020
     Geoffrey De Smet
  • YT AI in kotlin
    Wed 23 September 2020
     Geoffrey De Smet
  • YT Planning agility: continuous planning, real-time planning and more
    Thu 3 September 2020
     Geoffrey De Smet
  • YT Quarkus and OptaPlanner: create a school timetable application
    Thu 3 September 2020
     Radovan Synek
  • YT Business use cases and the impact of OptaPlanner
    Thu 3 September 2020
     Satish Kale
Video archive

KIE projects

  • Drools rule engine
  • OptaPlanner constraint solver
  • jBPM workflow engine

Community

  • Blog
  • Get Help
  • Team
  • Governance
  • Academic research

Code

  • Build from source
  • Submit a bug
  • License (Apache-2.0)
  • Release notes
  • Upgrade recipes
Sponsored by
Red Hat
More coder content at
Red Hat Developers
© Copyright 2006-2021, Red Hat, Inc. or third-party contributors - Privacy statement - Terms of use - Website info