JBoss.orgCommunity Documentation

Drools Planner User Guide

by The JBoss Drools team

Version 5.5.0.Final

1. Planner introduction
1.1. What is Drools Planner?
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. Status of Drools Planner
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 Drools Planner with maven, gradle, ivy, buildr or ANT
1.4.4. Build Drools Planner from source
1.5. Questions, issues and blog
2. Quick start
2.1. Cloud balancing tutorial
2.1.1. Problem statement
2.1.2. Domain model diagram
2.1.3. Main method
2.1.4. Solver configuration
2.1.5. Domain model implementation
2.1.6. Score configuration
2.1.7. Beyond this tutorial
3. Use cases and examples
3.1. Introduction
3.2. Toy 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. Positive and negative constraints
5.1.3. Score constraint weighting
5.1.4. Score level
5.1.5. Pareto scoring (AKA multi-objective optimization scoring)
5.1.6. The Score interface
5.2. Choose a Score definition
5.2.1. SimpleScore
5.2.2. HardAndSoftScore (recommended)
5.2.3. 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. Caching
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. The size of real world problems
6.2. The secret sauce of Drools Planner
6.3. Optimization algorithms overview
6.4. Which optimization algorithms should I use?
6.5. SolverPhase
6.6. Scope overview
6.7. Termination
6.7.1. TimeMillisSpendTermination
6.7.2. ScoreAttainedTermination
6.7.3. StepCountTermination
6.7.4. UnimprovedStepCountTermination
6.7.5. Combining multiple Terminations
6.7.6. Asynchronous termination from another thread
6.8. SolverEventListener
6.9. 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 in advance or Just In Time
7.2.2. SelectionOrder: original, random or shuffled selection
7.2.3. Recommended combinations of CacheType and SelectionOrder
7.2.4. Filtered selection
7.2.5. Sorted selection
7.2.6. Probability 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.5.1. TODO
7.6. ValueSelector
7.6.1. TODO
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
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. Exact methods
11.1. Overview
11.2. Brute Force
11.2.1. Algorithm description
11.2.2. Configuration
11.3. Depth-first search
11.3.1. Algorithm description
11.3.2. Configuration
12. Benchmarking and tweaking
12.1. Finding the best Solver configuration
12.2. Doing a benchmark
12.2.1. Adding the extra dependency
12.2.2. Building and running a PlannerBenchmark
12.2.3. ProblemIO: input and output of Solution files
12.2.4. Writing the output solution of the benchmark runs
12.2.5. Warming up the HotSpot compiler
12.3. Benchmark report
12.3.1. HTML report
12.3.2. Summary statistics
12.3.3. Statistic per data set (graph and CSV)
12.3.4. Ranking the Solvers
12.4. Advanced benchmarking
12.4.1. Benchmarking performance tricks
12.4.2. Template based benchmarking and matrix benchmarking
13. Repeated planning
13.1. Introduction to repeated planning
13.2. Backup planning
13.3. Continuous planning (windowed planning)
13.3.1. Immovable planning entities
13.4. Real-time planning (event based planning)