JBoss.orgCommunity Documentation

OptaPlanner User Guide

The OptaPlanner team

Version 7.0.0.Beta1

1. OptaPlanner Introduction
1.1. What is OptaPlanner?
1.2. Requirements
1.3. What is a Planning Problem?
1.3.1. A Planning Problem is NP-complete or NP-hard
1.3.2. A Planning Problem Has (Hard and Soft) Constraints
1.3.3. A Planning Problem Has a Huge Search Space
1.4. Download and Run the Examples
1.4.1. Get the Release .zip and Run the Examples
1.4.2. Run the Examples in an IDE (IntelliJ, Eclipse, NetBeans)
1.4.3. Use OptaPlanner with Maven, Gradle, Ivy, Buildr or ANT
1.4.4. Build OptaPlanner from Source
1.5. Governance
1.5.1. Status of OptaPlanner
1.5.2. Release Notes
1.5.3. Backwards Compatibility
1.5.4. Community and Support
1.5.5. Relationship with Drools and jBPM
2. Quick Start
2.1. Cloud Balancing Tutorial
2.1.1. Problem Description
2.1.2. Value Proposition
2.1.3. Problem Size
2.1.4. Domain Model Design
2.1.5. Main Method
2.1.6. Solver Configuration
2.1.7. Domain Model Implementation
2.1.8. Score Configuration
2.1.9. Beyond this Tutorial
3. Use Cases and Examples
3.1. Examples Overview
3.2. Basic Examples
3.2.1. N Queens
3.2.2. Cloud Balancing
3.2.3. Traveling Salesman (TSP - Traveling Salesman Problem)
3.2.4. Dinner Party
3.2.5. Tennis Club Scheduling
3.2.6. Meeting Scheduling
3.3. Real Examples
3.3.1. Course Timetabling (ITC 2007 Track 3 - Curriculum Course Scheduling)
3.3.2. Machine Reassignment (Google ROADEF 2012)
3.3.3. Vehicle Routing
3.3.4. Project Job Scheduling
3.3.5. Hospital Bed Planning (PAS - Patient Admission Scheduling)
3.3.6. Task assigning
3.4. Difficult Examples
3.4.1. Exam Timetabling (ITC 2007 track 1 - Examination)
3.4.2. Employee Rostering (INRC 2010 - Nurse Rostering)
3.4.3. Traveling Tournament Problem (TTP)
3.4.4. Cheap Time Scheduling
3.4.5. Investment asset class allocation (portfolio optimization)
4. Planner Configuration
4.1. Overview
4.2. Solver Configuration
4.2.1. Solver Configuration by XML
4.2.2. Solver Configuration by Java API
4.2.3. Annotations Configuration
4.3. Model a Planning Problem
4.3.1. Is This Class a Problem Fact or Planning Entity?
4.3.2. Problem Fact
4.3.3. Planning Entity
4.3.4. Planning Variable (genuine)
4.3.5. Planning Value and Planning Value Range
4.3.6. Shadow Variable
4.3.7. Planning Problem and Planning Solution
4.4. Use the Solver
4.4.1. The Solver Interface
4.4.2. Solving a Problem
4.4.3. Environment Mode: Are There Bugs in my Code?
4.4.4. Logging Level: What is the Solver Doing?
4.4.5. Random Number Generator
5. Score Calculation
5.1. Score Terminology
5.1.1. What is a Score?
5.1.2. Formalize the Business Constraints
5.1.3. Score Constraint Signum (Positive or Negative)
5.1.4. Score Constraint Weight
5.1.5. Score Constraint Level (hard, soft, ...)
5.1.6. Pareto Scoring (AKA Multi-objective Optimization Scoring)
5.1.7. Combining Score Techniques
5.1.8. Score interface
5.1.9. Avoid Floating Point Numbers in Score Calculation
5.2. Choose a Score Definition
5.2.1. SimpleScore
5.2.2. HardSoftScore (Recommended)
5.2.3. HardMediumSoftScore
5.2.4. BendableScore
5.2.5. Implementing a Custom Score
5.3. Calculate the Score
5.3.1. Score Calculation Types
5.3.2. Easy Java Score Calculation
5.3.3. Incremental Java Score Calculation
5.3.4. Drools Score Calculation
5.3.5. InitializingScoreTrend
5.3.6. Invalid Score Detection
5.4. Score Calculation Performance Tricks
5.4.1. Overview
5.4.2. Score Calculation Speed
5.4.3. Incremental Score Calculation (with Deltas)
5.4.4. Avoid Calling Remote Services During Score Calculation
5.4.5. Pointless Constraints
5.4.6. Built-in Hard Constraint
5.4.7. Other Score Calculation Performance Tricks
5.4.8. Score Trap
5.4.9. stepLimit Benchmark
5.4.10. Fairness Score Constraints
5.5. Explaining the Score: Using Score Calculation Outside the Solver
6. Optimization Algorithms
6.1. Search Space Size in the Real World
6.2. Does Planner Find the Optimal Solution?
6.3. Architecture Overview
6.4. Optimization Algorithms Overview
6.5. Which Optimization Algorithms Should I Use?
6.6. Power tweaking or default parameter values
6.7. Solver Phase
6.8. Scope Overview
6.9. Termination
6.9.1. TimeMillisSpentTermination
6.9.2. UnimprovedTimeMillisSpentTermination
6.9.3. BestScoreTermination
6.9.4. BestScoreFeasibleTermination
6.9.5. StepCountTermination
6.9.6. UnimprovedStepCountTermination
6.9.7. ScoreCalculationCountTermination
6.9.8. Combining Multiple Terminations
6.9.9. Asynchronous Termination from Another Thread
6.10. SolverEventListener
6.11. Custom Solver Phase
7. Move and Neighborhood Selection
7.1. Move and Neighborhood Introduction
7.1.1. What is a Move?
7.1.2. What is a MoveSelector?
7.1.3. Subselecting of Entities, Values and Other Moves
7.2. Generic MoveSelectors
7.2.1. changeMoveSelector
7.2.2. swapMoveSelector
7.2.3. pillarChangeMoveSelector
7.2.4. pillarSwapMoveSelector
7.2.5. tailChainSwapMoveSelector or 2-opt (chained variables only)
7.2.6. subChainChangeMoveSelector (chained variables only)
7.2.7. subChainSwapMoveSelector (chained variables only)
7.3. Combining Multiple MoveSelectors
7.3.1. unionMoveSelector
7.3.2. cartesianProductMoveSelector
7.4. EntitySelector
7.5. ValueSelector
7.6. General Selector Features
7.6.1. CacheType: Create Moves Ahead of Time or Just In Time
7.6.2. SelectionOrder: Original, Sorted, Random, Shuffled or Probabilistic
7.6.3. Recommended Combinations of CacheType and SelectionOrder
7.6.4. Filtered Selection
7.6.5. Sorted Selection
7.6.6. Probabilistic Selection
7.6.7. Limited Selection
7.6.8. Mimic Selection (Record/Replay)
7.6.9. Nearby Selection
7.7. Custom Moves
7.7.1. Which Move Types Might be Missing in my Implementation?
7.7.2. Custom Moves Introduction
7.7.3. The Interface Move
7.7.4. MoveListFactory: the Easy Way to Generate Custom Moves
7.7.5. MoveIteratorFactory: Generate Custom Moves Just in Time
8. Exhaustive Search
8.1. Overview
8.2. Brute Force
8.2.1. Algorithm Description
8.2.2. Configuration
8.3. Branch And Bound
8.3.1. Algorithm Description
8.3.2. Configuration
8.4. Scalability of Exhaustive Search
9. Construction Heuristics
9.1. Overview
9.2. First Fit
9.2.1. Algorithm Description
9.2.2. Configuration
9.3. First Fit Decreasing
9.3.1. Algorithm Description
9.3.2. Configuration
9.4. Weakest Fit
9.4.1. Algorithm Description
9.4.2. Configuration
9.5. Weakest Fit Decreasing
9.5.1. Algorithm Description
9.5.2. Configuration
9.6. Strongest Fit
9.6.1. Algorithm Description
9.6.2. Configuration
9.7. Strongest Fit Decreasing
9.7.1. Algorithm Description
9.7.2. Configuration
9.8. Allocate Entity From Queue
9.8.1. Algorithm Description
9.8.2. Configuration
9.8.3. Multiple Variables
9.8.4. Multiple Entity Classes
9.8.5. Pick Early Type
9.9. Allocate To Value From Queue
9.9.1. Algorithm Description
9.9.2. Configuration
9.10. Cheapest Insertion
9.10.1. Algorithm Description
9.10.2. Configuration
9.11. Regret Insertion
9.11.1. Algorithm Description
9.11.2. Configuration
9.12. Allocate From Pool
9.12.1. Algorithm Description
9.12.2. Configuration
10. Local Search
10.1. Overview
10.2. Local Search Concepts
10.2.1. Step by Step
10.2.2. Decide the Next Step
10.2.3. Acceptor
10.2.4. Forager
10.3. Hill Climbing (Simple Local Search)
10.3.1. Algorithm Description
10.3.2. Stuck in Local Optima
10.3.3. Configuration
10.4. Tabu Search
10.4.1. Algorithm Description
10.4.2. Configuration
10.5. Simulated Annealing
10.5.1. Algorithm Description
10.5.2. Configuration
10.6. Late Acceptance
10.6.1. Algorithm Description
10.6.2. Configuration
10.7. Step Counting Hill Climbing
10.7.1. Algorithm Description
10.7.2. Configuration
10.8. Strategic Oscillation
10.8.1. Algorithm Description
10.8.2. Configuration
10.9. Using a Custom Termination, MoveSelector, EntitySelector, ValueSelector or Acceptor
11. Evolutionary Algorithms
11.1. Overview
11.2. Evolutionary Strategies
11.3. Genetic Algorithms
12. Hyperheuristics
12.1. Overview
13. Partitioned Search
13.1. Overview
14. Benchmarking And Tweaking
14.1. Find The Best Solver Configuration
14.2. Benchmark Configuration
14.2.1. Add Dependency On optaplanner-benchmark
14.2.2. Build And Run A PlannerBenchmark
14.2.3. SolutionFileIO: Input And Output Of Solution Files
14.2.4. Warming Up The HotSpot Compiler
14.2.5. Benchmark Blueprint: A Predefined Configuration
14.2.6. Write The Output Solution Of Benchmark Runs
14.2.7. Benchmark Logging
14.3. Benchmark Report
14.3.1. HTML Report
14.3.2. Ranking The Solvers
14.4. Summary Statistics
14.4.1. Best Score Summary (Graph And Table)
14.4.2. Best Score Scalability Summary (Graph)
14.4.3. Best Score Distribution Summary (Graph)
14.4.4. Winning Score Difference Summary (Graph And Table)
14.4.5. Worst Score Difference Percentage (ROI) Summary (Graph and Table)
14.4.6. Score Calculation Speed Summary (Graph and Table)
14.4.7. Time Spent Summary (Graph And Table)
14.4.8. Time Spent Scalability Summary (Graph)
14.4.9. Best Score Per Time Spent Summary (Graph)
14.5. Statistic Per Dataset (Graph And CSV)
14.5.1. Enable A Problem Statistic
14.5.2. Best Score Over Time Statistic (Graph And CSV)
14.5.3. Step Score Over Time Statistic (Graph And CSV)
14.5.4. Score Calculation Speed Statistic (Graph And CSV)
14.5.5. Best Solution Mutation Over Time Statistic (Graph And CSV)
14.5.6. Move Count Per Step Statistic (Graph And CSV)
14.5.7. Memory Use Statistic (Graph And CSV)
14.6. Statistic Per Single Benchmark (Graph And CSV)
14.6.1. Enable A Single Statistic
14.6.2. Constraint Match Total Best Score Over Time Statistic (Graph And CSV)
14.6.3. Constraint Match Total Step Score Over Time Statistic (Graph And CSV)
14.6.4. Picked Move Type Best Score Diff Over Time Statistic (Graph And CSV)
14.6.5. Picked Move Type Step Score Diff Over Time Statistic (Graph And CSV)
14.7. Advanced Benchmarking
14.7.1. Benchmarking Performance Tricks
14.7.2. Statistical Benchmarking
14.7.3. Template Based Benchmarking And Matrix Benchmarking
14.7.4. Benchmark Report Aggregation
15. Repeated Planning
15.1. Introduction to Repeated Planning
15.2. Backup Planning
15.3. Overconstrained Planning
15.3.1. Overconstrained Planning with Nullable Variables
15.3.2. Overconstrained Planning with Virtual Values
15.4. Continuous Planning (Windowed Planning)
15.4.1. Immovable Planning Entities
15.4.2. Nonvolatile Replanning to minimize disruption (Semi-movable Planning Entities)
15.5. Real-time Planning
15.5.1. ProblemFactChange
15.5.2. Daemon: solve() Does Not Return
16. Integration
16.1. Overview
16.2. Persistent Storage
16.2.1. Database: JPA and Hibernate
16.2.2. XML or JSON: XStream
16.2.3. XML or JSON: JAXB
16.2.4. JSON: Jackson
16.3. SOA and ESB
16.3.1. Camel and Karaf
16.4. Other Environments
16.4.1. JBoss Modules, WildFly and JBoss EAP
16.4.2. OSGi
16.4.3. Android
16.5. Integration with Human Planners (Politics)
17. Design Patterns
17.1. Design Patterns Introduction
17.2. Assigning Time to Planning Entities
17.2.1. Timeslot Pattern: Assign to a Fixed-Length Timeslot
17.2.2. TimeGrain Pattern: Assign to a Starting TimeGrain
17.2.3. Chained Through Time Pattern: Assign in a Chain that Determines Starting Time
17.3. Multi-stage planning
18. Development
18.1. Methodology Overview
18.2. Development guidelines