JBoss.orgCommunity Documentation

OptaPlanner User Guide

by The OptaPlanner team

Version 6.2.0.CR2

1. OptaPlanner introduction
1.1. What is OptaPlanner?
1.2. What is a planning problem?
1.2.1. A planning problem is NP-complete or NP-hard
1.2.2. A planning problem has (hard and soft) constraints
1.2.3. A planning problem has a huge search space
1.3. Download and run the examples
1.3.1. Get the release zip and run the examples
1.3.2. Run the examples in an IDE (IntelliJ, Eclipse, NetBeans)
1.3.3. Use OptaPlanner with Maven, Gradle, Ivy, Buildr or ANT
1.3.4. Build OptaPlanner from source
1.4. Status of OptaPlanner
1.5. Compatibility
1.6. Relationship with Drools and jBPM
1.7. Questions, issues and blog
2. Quick start
2.1. Cloud balancing tutorial
2.1.1. Problem statement
2.1.2. Problem size
2.1.3. Domain model diagram
2.1.4. Main method
2.1.5. Solver configuration
2.1.6. Domain model implementation
2.1.7. Score configuration
2.1.8. 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.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.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
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.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
4.3.5. Planning value and planning value ranges
4.3.6. 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. Score constraint signum (positive or negative)
5.1.3. Score constraint weight
5.1.4. Score level
5.1.5. Pareto scoring (AKA multi-objective optimization scoring)
5.1.6. Combining score techniques
5.1.7. Score interface
5.1.8. 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. Average calculation count per second
5.4.3. Incremental score calculation (with delta's)
5.4.4. Avoid calling remote services during score calculation
5.4.5. Pointless constraints
5.4.6. Build-in hard constraint
5.4.7. Other 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. Solver phase
6.7. Scope overview
6.8. Termination
6.8.1. TimeMillisSpentTermination
6.8.2. UnimprovedTimeMillisSpentTermination
6.8.3. BestScoreTermination
6.8.4. BestScoreFeasibleTermination
6.8.5. StepCountTermination
6.8.6. UnimprovedStepCountTermination
6.8.7. Combining multiple Terminations
6.8.8. Asynchronous termination from another thread
6.9. SolverEventListener
6.10. 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. subChainChangeMoveSelector
7.2.6. subChainSwapMoveSelector
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. Allocate Entity From Queue
9.6.1. Algorithm description
9.6.2. Configuration
9.6.3. Multiple variables
9.6.4. Multiple entity classes
9.6.5. Pick early type
9.7. Allocate To Value From Queue
9.7.1. Algorithm description
9.7.2. Configuration
9.8. Cheapest Insertion
9.8.1. Algorithm description
9.8.2. Configuration
9.9. Regret Insertion
9.9.1. Algorithm description
9.9.2. Configuration
9.10. Allocate From Pool
9.10.1. Algorithm description
9.10.2. Configuration
10. Local search
10.1. Overview
10.2. Local Search concepts
10.2.1. Taking steps
10.2.2. Deciding 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. Getting 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. Finding the best Solver configuration
14.2. Doing a benchmark
14.2.1. Adding a dependency on optaplanner-benchmark
14.2.2. Building and running 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. Writing the output solution of the 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. Winning score difference summary (graph and table)
14.4.4. Worst score difference percentage (ROI) summary (graph and table)
14.4.5. Average calculation count summary (graph and table)
14.4.6. Time spent summary (graph and table)
14.4.7. Time spent scalability summary (graph)
14.4.8. Best score per time spent summary (graph)
14.5. Statistic per dataset (graph and CSV)
14.5.1. Enabling 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. Calculate count per second 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. Enabling 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. Template based benchmarking and matrix benchmarking
14.7.3. Benchmark report aggregation
15. Repeated planning
15.1. Introduction to repeated planning
15.2. Backup planning
15.3. Continuous planning (windowed planning)
15.3.1. Immovable planning entities
15.4. Real-time planning (event based planning)
15.4.1. ProblemFactChange
15.4.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: XStream
16.2.3. XML: JAXB
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. Development
17.1. Methodology overview