かなりのボリュームです。まずはざくっとナナメ読み。
http://docs.jboss.org/drools/release/6.0.1.Final/optaplanner-docs/html_single/index.html
1. Planner introduction
何のためのソフトウェアか、という話です。
OptaPlanner is a lightweight, embeddable planning engine that optimizes planning problems.
Embeddableなところがポイントかも知れませんね。自分のアプリに組み込むことができます。いろんなユースケースがリストされているけれど、Bin packingが一番イメージしやすいかな。いろんなサイズの入れ物に、いろんなサイズのモノを入れる。最適解は？というのが問題。
「A planning problem is NP-complete」に対して「By using advanced optimization algorithms, Planner does find a good solution in reasonable time for such planning problems.」ということです。
Planning Problem には、soft制約とhard制約があります。
A (negative) hard constraint must not be broken. For example: 1 teacher can not teach 2 different lessons at the same time.
A (negative) soft constraint should not be broken if it can be avoided. For example: Teacher A does not like to teach on Friday afternoon.
- A possible solution : 制約を考慮しない、ありうるソリューション。（= すべての組み合わせ）
- A feasible solution : hard制約を破らないソリューション
- An optimal solution : スコアの最も良いソリューション
- The best solution : 一定時間内に得られた、スコアの最も良いソリューション
2. Quick start
Cloud balancing example をチュートリアルとして説明します。クラウド上のコンピュータに対し、必要なプロセスを効率的に割り当てるというプランです。「Cloud balance class diagram」を見ればわかるように、プランする対象'Process' を @PlannningEntity, そのProcessから見た変数 'computer' を @PlanningVariable, 結果 'CloudBalance' を @PlanningSolution としてそれぞれアノテートします。ここを読めば OptaPlanner の使い方/考え方がざっくりと理解できると思います。
3. Use cases and examples
examplesのユースケースを個々に説明しています。かなり詳しいです。おそらくこれを読むことで、実際のユースケースに OptaPlanner を適用するための基礎力をつけることができるのではないでしょうか。
4. Planner configuration
設定ファイル(solver configuration)、クラスの実装、solverの実行、という一連の流れを解説。わかりやすいですね。
4.2. Solver configuration
「OptaPlanner makes it relatively easy to switch optimization algorithm(s) just by changing the configuration.」
4.3. Model your planning problem
- A problem fact class: used by the score constraints, but does NOT change during planning (as long as the problem stays the same). For example: Bed, Room, Shift, Employee, Topic, Period, ...
- A planning entity class: used by the score constraints and changes during planning. For example: BedDesignation, ShiftAssignment, Exam, ...
ここで Problem fact は@PlanningVariableで参照されることもあるし、単なる固定プロパティの場合もある。 Problem fact 自身は変化しないことに注意
5. Score calculation
best solutionを決定するためのスコアリング。ここも相当詳しく書いてあるな。スコアリングがパフォーマンスネックになる場合とかを特に気にしているようだ。
6. Optimization algorithms
「The nature of NP-complete problems make scaling a prime concern. The result quality of a small dataset guarantees nothing about the result quality of a large dataset. 」なるほど。
各種アルゴリズム、後の章にリンクされてる。むしろこの章以降ずっとアルゴリズムに関連した話になるかな。ここは腰据えて理解せんとなー。
あと、Solver Phase/Step/Move これが、各デバッグレベルに紐付いている。
7. Move and neighborhood selection
solutionの探索についての詳細。solution A から solution B に移るのが Move。1 move で隣り合っている solution は neighbor。
8. Construction heuristics
A construction heuristic builds a pretty good initial solution in a finite length of time. Its solution isn't always feasible, but it finds it fast so metaheuristics can finish the job.
まず Construction heuristics がスタートラインのようです。なかでも First Fit / First Fit Decreasing を押さえておこう。
9. Local search
こっちが Metaheuristics。ひとつの （Construction heuristicsで決定された）initialized solution から、さらにベターな手を探る方法。その方法のアルゴリズムにバリエーションがある。
10. Evolutionary algorithms
まだ実装されていません。
11. Hyperheuristics
データセットに応じて、どのheuristicを使うかを決定すること。Plannerの将来のバージョンでサポートされるが、現在でも自分でSolver configurationを切り替えればいい。
12. Exact methods
ベタな手法。Brute Force、Depth-first search。スケールしない。Depth-first searchは未実装。
13. Benchmarking and tweaking
PlannerBenchmarkでベンチマークが取れる。で、試行錯誤すればよい。
14. Repeated planning
solver実行中にplanning factsが変更される場合、どうする？plannerは長時間実行されるものだから実際のユースケースとして考慮しないといけない。
- Unforeseen fact changes: For example: an employee assigned to a shift calls in sick, an airplane scheduled to take off has a technical delay, one of the machines or vehicles break down, ... Use backup planning.
- Unknown long term future facts: For example: The hospital admissions for the next 2 weeks are reliable, but those for week 3 and 4 are less reliable and for week 5 and beyond are not worth planning yet. Use continuous planning.
- Constantly changing planning facts: Use real-time planning.
15. Integration
データセットをDBから読む、結果をRESTで公開するなど。
