ホーム
製品
Red Hat Decision Manager
7.11
Red Hat Decision Manager で Red Hat ビルドの OptaPlanner を使用した Solver の開発
第4章 Red Hat ビルドの OptaPlanner で提供される例

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

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

注記

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

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

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

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

表4.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`

4.1. N クィーン

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

制約:

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

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

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

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

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

以下は正しい解です。

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

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

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.

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.

Copy to Clipboard

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

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

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

ドメインモデルの作成

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

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

public class Column {

    private int index;

    // ... getters and setters
}

public class Column {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

public class Row {

    private int index;

    // ... getters and setters
}

public class Row {

    private int index;

    // ... getters and setters
}

Copy to Clipboard

public class Queen {

    private Column column;
    private Row row;

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

    // ... getters and setters
}

public class Queen {

    private Column column;
    private Row row;

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

    // ... getters and setters
}

Copy to Clipboard

探索空間の計算

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
}

public class NQueens {

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

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

Copy to Clipboard

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

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

図4.3 クィーン 4 個の解

表4.2 ドメインモデルの解の詳細
	columnIndex	rowIndex	ascendingDiagonalIndex (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 つの駒が互いを取ることができます。

トップに戻る

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

4.1. N クィーン

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

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links