JBoss.orgCommunity Documentation

OptaPlanner User Guide

by The OptaPlanner team

Version 6.0.0.Beta1

1. Planner introduction
1.1. What is OptaPlanner?
1.2. What is a planning problem?
1.2.1. A planning problem is NP-complete
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. 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. Manners 2009
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. 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. Sport scheduling (TTP - Traveling tournament problem)
4. Planner configuration
4.1. Overview
4.2. Solver configuration
4.2.1. Solver configuration by XML file
4.2.2. Solver configuration by Java API
4.3. Model your planning problem
4.3.1. Is this class a problem fact or planning entity?
4.3.2. Problem fact
4.3.3. Planning entity and planning variables
4.3.4. Planning value and planning value ranges
4.3.5. 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?
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. The Score interface
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. Simple Java score calculation
5.3.3. Incremental Java score calculation
5.3.4. Drools score calculation
5.3.5. Detecting invalid scores
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. Unused constraint
5.4.6. Build-in hard constraint
5.4.7. Other performance tricks
5.4.8. Score trap
5.4.9. stepLimit benchmark
5.5. Reusing the 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. SolverPhase
6.7. Scope overview
6.8. Termination
6.8.1. TimeMillisSpendTermination
6.8.2. ScoreAttainedTermination
6.8.3. StepCountTermination
6.8.4. UnimprovedStepCountTermination
6.8.5. Combining multiple Terminations
6.8.6. Asynchronous termination from another thread
6.9. SolverEventListener
6.10. Custom SolverPhase
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. General Selector features
7.2.1. CacheType: Create moves ahead of time or Just In Time
7.2.2. SelectionOrder: original, sorted, random, shuffled or probabilistic
7.2.3. Recommended combinations of CacheType and SelectionOrder
7.2.4. Filtered selection
7.2.5. Sorted selection
7.2.6. Probabilistic selection
7.3. Generic MoveSelectors
7.3.1. changeMoveSelector
7.3.2. swapMoveSelector
7.3.3. pillarSwapMoveSelector
7.3.4. subChainChangeMoveSelector
7.3.5. subChainSwapMoveSelector
7.4. Combining multiple MoveSelectors
7.4.1. unionMoveSelector
7.4.2. cartesianProductMoveSelector
7.5. EntitySelector
7.6. ValueSelector
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
7.7.6. Move generation through DRL
8. Construction heuristics
8.1. Overview
8.2. First Fit
8.2.1. Algorithm description
8.2.2. Configuration
8.3. First Fit Decreasing
8.3.1. Algorithm description
8.3.2. Configuration
8.4. Best Fit
8.4.1. Algorithm description
8.4.2. Configuration
8.5. Best Fit Decreasing
8.5.1. Algorithm description
8.5.2. Configuration
8.6. Cheapest insertion
8.6.1. Algorithm description
8.6.2. Configuration
8.7. Regret insertion
8.7.1. Algorithm description
8.7.2. Configuration
9. Local search
9.1. Overview
9.2. Hill climbing (simple local search)
9.2.1. Algorithm description
9.3. Tabu search
9.3.1. Algorithm description
9.4. Simulated annealing
9.4.1. Algorithm description
9.5. Late acceptance
9.5.1. Algorithm description
9.6. About neighborhoods, moves and steps
9.6.1. Move generation tips
9.6.2. A step
9.6.3. Getting stuck in local optima
9.7. Deciding the next step
9.7.1. Acceptor
9.7.2. Forager
9.8. Using a custom Termination, MoveSelector, EntitySelector, ValueSelector or Acceptor
10. Evolutionary algorithms
10.1. Overview
10.2. Evolutionary Strategies
10.3. Genetic algorithms
11. Hyperheuristics
11.1. Overview
12. Exact methods
12.1. Overview
12.2. Brute Force
12.2.1. Algorithm description
12.2.2. Configuration
12.3. Depth-first search
12.3.1. Algorithm description
12.3.2. Configuration
13. Benchmarking and tweaking
13.1. Finding the best Solver configuration
13.2. Doing a benchmark
13.2.1. Adding the extra dependency
13.2.2. Building and running a PlannerBenchmark
13.2.3. ProblemIO: input and output of Solution files
13.2.4. Writing the output solution of the benchmark runs
13.2.5. Warming up the HotSpot compiler
13.3. Benchmark report
13.3.1. HTML report
13.3.2. Summary statistics
13.3.3. Statistic per data set (graph and CSV)
13.3.4. Ranking the Solvers
13.4. Advanced benchmarking
13.4.1. Benchmarking performance tricks
13.4.2. Template based benchmarking and matrix benchmarking
14. Repeated planning
14.1. Introduction to repeated planning
14.2. Backup planning
14.3. Continuous planning (windowed planning)
14.3.1. Immovable planning entities
14.4. Real-time planning (event based planning)