第31章 Red Hat ビルドの OptaPlanner で提供される例

Red Hat Process Automation Manager には、Red Hat ビルドの OptaPlanner のサンプルが複数同梱されています。たとえばコードなどを確認して、ニーズに合ったものに変更できます。

注記

Red Hat は、Red Hat Process Automation Manager ディストリビューションに含まれるコードサンプルのサポートはしていません。

OptaPlanner サンプルには、教育関連のコンテストで出題された問題を解決するものもあります。以下の表の Contest 列には、このようなコンテストが掲載されています。また、コンテストの目的として、現実的 か、非現実的 かの識別をしています。現実的なコンテスト とは、以下の基準を満たす、独立した公式コンテストを指します。

  • 明確に定義された実際のユースケースであること
  • 実際に制約があること
  • 実際のデータセットが複数あること
  • 特定のハードウェアで特定の時間内に結果を再現できること
  • 教育機関および/または企業の運用研究コミュニティーが真剣に参加していること

現実的なコンテストでは、競合のソフトウェアや教育研究と OptaPlanner を客観的に比較できます。

表31.1 サンプルの概要

例ドメインサイズコンテストディレクトリー名

N クィーン

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 256

値 ⇐ 256

探索空間 ⇐ 10^616

無意味 (不正が可能)

nqueens

クラウドバランシング

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 2400

値 ⇐ 800

探索空間 ⇐ 10^6967

いいえ (弊社が定義)

cloudbalancing

巡回セールスマン

エンティティークラス 1 つ

(連鎖変数 1 つ)

エンティティー ⇐ 980

値 ⇐ 980

探索空間 ⇐ 10^2504

現実的でない TSP Web

tsp

テニスクラブのスケジュール

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 72

値 ⇐ 7

探索空間 ⇐ 10^60

いいえ (弊社が定義)

tennis

会議のスケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 10

値 ⇐ 320 および ⇐ 5

探索空間 ⇐ 10^320

いいえ (弊社が定義)

meetingscheduling

コースの時間割

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 434

値 ⇐ 25 および ⇐ 20

探索空間 ⇐ 10^1171

現実的 ITC 2007 track 3

curriculumCourse

マシンの再割当て

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 50000

値 ⇐ 5000

探索空間 ⇐ 10^184948

ほぼ現実的 ROADEF 2012

machineReassignment

配送経路

エンティティークラス 1 つ

(連鎖変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 2740

値 ⇐ 2795

探索空間 ⇐ 10^8380

現実的でない VRP Web

vehiclerouting

時間枠がある中での 配送経路

配送経路すべて

(シャドウ変数 1 つ)

エンティティー ⇐ 2740

値 ⇐ 2795

探索空間 ⇐ 10^8380

現実的でない VRP Web

vehiclerouting

プロジェクトジョブのスケジュール

エンティティークラス 1 つ

(変数 2 つ)

(シャドウ変数 1 つ)

エンティティー ⇐ 640

値 ⇐ ? および ⇐ ?

探索空間 ⇐ ?

ほぼ現実的 MISTA 2013

projectjobscheduling

タスクの割り当て

エンティティークラス 1 つ

(連鎖変数 1 つ)

(シャドウ変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 500

値 ⇐ 520

探索空間 ⇐ 10^1168

いいえ (弊社が定義)

taskassigning

試験の時間割

エンティティークラス 2 つ (同じ階層)

(変数 2 つ)

エンティティー ⇐ 1096

値 ⇐ 80 および ⇐ 49

探索空間 ⇐ 10^3374

現実的 ITC 2007 track 1

examination

看護師の勤務表

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 752

値 ⇐ 50

探索空間 ⇐ 10^1277

現実的 INRC 2010

nurserostering

巡回トーナメント

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 1560

値 ⇐ 78

探索空間 ⇐ 10^2301

現実的でない TTP

travelingtournament

コストを抑えるスケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 500

値 ⇐ 100 および ⇐ 288

探索空間 ⇐ 10^20078

ほぼ現実的 ICON Energy

cheaptimescheduling

投資

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 11

値 = 1000

探索空間 ⇐ 10^4

いいえ (弊社が定義)

investment

会議スケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 216

値 ⇐ 18 および ⇐ 20

探索空間 ⇐ 10^552

いいえ (弊社が定義)

conferencescheduling

ロックツアー

エンティティークラス 1 つ

(連鎖変数 1 つ)

(シャドウ変数 4 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 47

値 ⇐ 48

探索空間 ⇐ 10^59

いいえ (弊社が定義)

rocktour

航空機乗組員のスケジューリング

エンティティークラス 1 つ

(変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 4375

値 ⇐ 750

探索空間 ⇐ 10^12578

いいえ (弊社が定義)

flightcrewscheduling

31.1. N クィーン

n サイズのチェスボードで、他のクィーンに取られない場所に n 個のクィーンを置きます。最も一般的な n クィーンパズルは、n = 8 の 8 個のクィーンパズルです。

nQueensScreenshot

制約:

  • n 列および n 行のチェスボードを使用します。
  • チェスボードに n 個のクィーンを置きます。
  • クィーンが他のクィーンに取られないように配置します。クィーンは、同じ水平線上、垂直線上、対角線上にある他のクィーンを取ることができます。

本書では、4 つのクイーンパズルを主な例として多用しています。

以下が提案された解です。

図31.1 クィーン 4 個のパズルの誤った解

partiallySolvedNQueens04Explained

上記の解は、A1 と B0 (および B0 と D0) のクィーンがお互いに駒を取れるので間違っています。B0 のクィーンをどかせば他のクィーンに取られないようにするという制約は順守できますが、n 個のクィーンを置くという制約に違反します。

以下は正しい解です。

図31.2 クィーン 4 個のパズルの正しい解

solvedNQueens04

すべての制約が満たされているので、これが正解です。

n クィーンパズルでは、正解が複数存在する場合が多々あります。指定した n に対して考えられるすべての解を見つけるのではなく、指定の n に対する正しい解を 1 つ導き出すことに焦点をあてます。

問題の規模

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

n クィーンは、初心者用のサンプルとして実装されているため、最適化はされていません。それにもかかわらず、クィーンが 64 個になっても簡単に処理できます。何点か変更を加えると、クィーンが 5000 個以上になっても簡単に対応できることが立証されています。

31.1.1. N クィーンのドメインモデル

この例では、4 つのクィーンの問題を解決するドメインモデルを使用します。

  • ドメインモデルの作成

    適切なドメインモデルを使用すると、プランニングの問題をより簡単に理解し、解決することができます。

    以下は、n クィーンの例のドメインモデルです。 

    public class Column {

    private int index;

    // ... getters and setters
}
    public class Row {

    private int index;

    // ... getters and setters
}
    public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

  • 探索空間の計算

    Queen インスタンスには Column (例: 0 は列 A、1 は列 B​) および Row (例: 0 は行 0、1 は行 1​) が含まれます。

    列と行をもとに、昇順の対角線、および降順の対角線を計算することができます。

    列と行のインデックスは、チェスボードの左上隅から数えています。 

    public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

  • 解の求め方

    1 つの NQueens インスタンスには Queen インスタンスの一覧が含まれています。これが Solution 実装として提供され、Solver が解決して読み出します。

たとえば、4 クイーンのサンプルでは、NQueens の getN() メソッドが常に 4 を返します。

図31.3 クィーン 4 個の解

partiallySolvedNQueens04Explained

表31.2 ドメインモデルの解の詳細

 columnIndexrowIndexascendingDiagonalIndex (columnIndex + rowIndex)descendingDiagonalIndex (columnIndex - rowIndex)

A1

0

1

1 (**)

-1

B0

1

0 (*)

1 (**)

1

C2

2

2

4

0

D0

3

0 (*)

3

3

(*) や (**) のように、クィーン 2 つが同じ行、列、対角線を共有する場合は、2 つの駒が互いを取ることができます。