Menu Close

第1章 Red Hat Business Optimizer の概要

Red Hat Business Optimizer は組み込み可能な軽量プランニングエンジンで、プランニングの問題を最適化します。最適化のためのヒューリスティック法およびメタヒューリスティック法を、非常に効率的なスコア計算と組み合わせ、一般的な Java プログラマーがプランニングの問題を効率的に解決できるようにします。

Red Hat Business Optimizer は、さまざまなユースケースの解決に役立ちます。以下にその例を示します。

  • 従業員勤務表/患者一覧: 看護師の勤務シフト作成を容易にし、病床管理を追跡します。
  • 教育機関の時間割: 授業、コース、試験、および会議の計画を容易にします。
  • 工場の計画: 自動車の組み立てライン、機械の操業計画、および作業員のタスク計画を追跡します。
  • 在庫の削減: 紙や金属などの資源の消費を削減し、無駄を最小限に抑えます。

どの組織も、制約のある限定されたリソース (従業員、資産、時間、資金) を使用して製品やサービスを提供するといった、プランニングの問題に直面しています。

Red Hat Business Optimizer は、Apache Software License 2.0 を使用するオープンソースソフトウェアです。100% Pure Java に認定されており、ほとんどの Java 仮想マシンで稼働します。

1.1. 計画問題

計画問題では、限られたリソースや個別の制約の中で最適なゴールを見つけ出します。最適なゴールは、以下に示すように何らかの物の数となります。

  • 最大の利益: 最適なゴールにより、可能な限り高い利益が得られます。
  • 経済活動の最小フットプリント: 最適なゴールでは、環境負荷が最小となります。
  • スタッフ/顧客の最大満足: 最適なゴールでは、スタッフ/顧客のニーズが優先されます。

これらのゴールに到達できるかどうかは、利用できるリソースの数に依存します。たとえば、以下のようなリソースには制限があります。

  • 要員数
  • 時間
  • 予算
  • 装置、車両、コンピューター、施設などの物理資産

これらのリソースに関連する個別の制約についても考慮する必要があります。たとえば、要員が働くことのできる時間数、特定の装置を使用することのできる技能、または機器同士の互換性などです。

Red Hat Business Optimizer は、最適化のためのヒューリスティック法およびメタヒューリスティック法を効率的なスコア計算と組み合わせ、Java プログラマーが制約充足問題を効率的に解くことができるようにします。

1.2. 計画問題での NP 完全

例に挙げたユースケースは 通常 NP 完全または NP 困難 であり、以下のことが言えます。

  • 問題に対する解を実用的な時間内に検証することが容易である。
  • 問題に対する最適解を実用的な時間内に見つけ出す確実な方法がない。

この場合、一般的な 2 つの手法では不十分なので、問題を解くのが予想より困難だと考えられます。

  • 力まかせアルゴリズムでは (より高度な類似アルゴリズムであっても)、時間がかかり過ぎる。
  • (ビンパッキング問題 において) 容量が最大のビンから順に詰めてゆく クイックアルゴリズムでは、最適解からは程遠い解しか得られない。

高度な最適化アルゴリズムを用いる Business Optimizer であれば、このような計画問題に対する適切な解を、実用的な時間内に見つけ出すことができます。

1.3. 計画問題に対する解

プランニングの問題には、多数の解が存在します。

以下に示すように、解は複数のカテゴリーに分類されます。

可能解
可能解とは、制約に違反するかどうかは問わず、あらゆる解を指します。通常、プランニングの問題には膨大な数の可能解が存在します。ただし、それらの解の多くは、無価値なものです。
実行可能解
実行可能解とは、いずれの (負の) ハード制約にも違反しない解を指します。実行可能解の数は、可能解の数に比例する傾向にあります。実行可能解が存在しないケースもあります。実行可能解は、可能解の部分集合です。
最適解
最適解とは、最高のスコアを持つ解を指します。通常、プランニングの問題には数個の最適解が存在します。実行可能解が存在せず、最適解が現実的ではない場合でも、プランニングの問題には少なくとも 1 つの最適解が必ず存在します。
見つかった最善解
見つかった最善解とは、与えられた時間内に実施した検索で見つかった最高スコアの解を指します。通常、見つかった最善解は現実的で、十分な時間があれば最適解を見つけることができます。

直観には反していますが、小規模なデータセットの場合であっても、膨大な数の可能解が存在します (正しく計算された場合)。

planner-engine ディストリビューションフォルダーのサンプルでも、ほとんどのインスタンスには膨大な数の可能解が存在します。最適解を確実に見つけ出すことのできる方法は存在しないため、いかなる実行方法も、これらすべての可能解の部分集合を評価することしかできません。

膨大な数の可能解全体を効率的に網羅するために、Business Optimizer はさまざまな最適化アルゴリズムをサポートしています。

ユースケースによっては、ある最適化アルゴリズムが他のアルゴリズムより優れることがあります。ただし、それを事前に予測することは不可能です。Business Optimizer では、XML またはコード中の Solver 設定を数行変更するだけで、最適化アルゴリズムを切り替えることができます。

1.4. 計画問題に対する制約

通常、プランニングの問題には、少なくとも 2 つの制約レベルがあります。

  • (負の) ハード制約 は、絶対に違反してはならない。

    例: 1 人の教師は同時に 2 つの講義を受け持つことはできない。

  • (負の) ソフト制約 は、避けることが可能であれば違反してはならない。

    例: 教師 A は金曜日の午後に講義を受け持ちたくない。

正の制約を持つ問題もあります。

  • 正のソフト制約 (ボーナス) は、可能であれば満たす必要がある。

    例: 教師 B は月曜日の午前中に講義を受け持つことを希望している。

基本的な問題の中には、ハード制約しか持たないものや、3 つ以上の制約レベル (例: ハード、ミディアム、およびソフト制約) を持つものもあります。

これらの制約により、計画問題における スコア計算方法 (または 適合度関数) が定義されます。プランニングの問題の解は、それぞれスコアで等級付けすることができます。Business Optimizer のスコア制約は、Java コード等のオブジェクト指向言語または Drools ルールで記述されます。

このタイプのコードは柔軟で、スケーラビリティーに優れます。