JBoss.orgCommunity Documentation

OptaPlanner User Guide

by The OptaPlanner team

Version 6.1.0.Beta3

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. 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)
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
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. The 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. 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. TimeMillisSpentTermination
6.8.2. UnimprovedTimeMillisSpentTermination
6.8.3. BestScoreTermination
6.8.4. StepCountTermination
6.8.5. UnimprovedStepCountTermination
6.8.6. Combining multiple Terminations
6.8.7. 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. Generic MoveSelectors
7.2.1. changeMoveSelector
7.2.2. swapMoveSelector
7.2.3. pillarSwapMoveSelector
7.2.4. subChainChangeMoveSelector
7.2.5. 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.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. 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. Advanced Greedy Fit
8.6.1. Algorithm description
8.6.2. Configuration
8.6.3. Multiple variables
8.6.4. Multiple entity classes
8.6.5. Pick early type
8.7. Cheapest insertion
8.7.1. Algorithm description
8.7.2. Configuration
8.8. Regret insertion
8.8.1. Algorithm description
8.8.2. Configuration
9. Local search
9.1. Overview
9.2. Local Search concepts
9.2.1. Taking steps
9.2.2. Deciding the next step
9.2.3. Acceptor
9.2.4. Forager
9.3. Hill Climbing (Simple Local Search)
9.3.1. Algorithm description
9.3.2. Getting stuck in local optima
9.3.3. Configuration
9.4. Tabu Search
9.4.1. Algorithm description
9.4.2. Configuration
9.5. Simulated Annealing
9.5.1. Algorithm description
9.5.2. Configuration
9.6. Late Acceptance
9.6.1. Algorithm description
9.6.2. Configuration
9.7. Step Counting Hill Climbing
9.7.1. Algorithm description
9.7.2. Configuration
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. Exhaustive search
12.1. Overview
12.2. Brute Force
12.2.1. Algorithm description
12.2.2. Configuration
12.3. Branch And Bound
12.3.1. Algorithm description
12.3.2. Configuration
12.4. Scalability of Exhaustive Search
13. Benchmarking and tweaking
13.1. Finding the best Solver configuration
13.2. Doing a benchmark
13.2.1. Adding a dependency on optaplanner-benchmark
13.2.2. Building and running a PlannerBenchmark
13.2.3. ProblemIO: input and output of Solution files
13.2.4. Warming up the HotSpot compiler
13.2.5. Writing the output solution of the benchmark runs
13.3. Benchmark report
13.3.1. HTML report
13.3.2. Ranking the Solvers
13.4. Summary statistics
13.4.1. Best score summary (graph and table)
13.4.2. Best score scalability summary (graph)
13.4.3. Winning score difference summary (graph and table)
13.4.4. Worst score difference percentage (ROI) summary (graph and table)
13.4.5. Average calculation count summary (graph and table)
13.4.6. Time spent summary (graph and table)
13.4.7. Time spent scalability summary (graph)
13.4.8. Best score per time spent summary (graph)
13.5. Statistic per dataset (graph and CSV)
13.5.1. Enabling a problem statistic
13.5.2. Best score over time statistic (graph and CSV)
13.5.3. Step score over time statistic (graph and CSV)
13.5.4. Calculate count per second statistic (graph and CSV)
13.5.5. Best solution mutation over time statistic (graph and CSV)
13.5.6. Move count per step statistic (graph and CSV)
13.5.7. Memory use statistic (graph and CSV)
13.6. Advanced benchmarking
13.6.1. Benchmarking performance tricks
13.6.2. Template based benchmarking and matrix benchmarking
13.6.3. Benchmark report aggregation
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)
15. Integration
15.1. Overview
15.2. Persistent storage
15.2.1. Database: JPA and Hibernate
15.2.2. XML: XStream
15.2.3. XML: JAXB
15.3. SOA and ESB
15.3.1. Camel and Karaf
15.4. Other environments
15.4.1. OSGi
15.4.2. Android
15.5. Integration with human planners (politics)