# OptaPlanner

Jump to navigation
Jump to search

## What is OptaPlanner ⌘

- "OptaPlanner is a lightweight, embeddable planning engine that optimizes planning problems"
- Apache Software License 2.0
- 100% pure Java
^{TM} - Combines optimization heuristics and metaheuristics with very efficient score calculation (Drools Expert i.e. Rete or backward chaining)

## Use cases ⌘

- Shift rostering (timetabling)
- Trainer, plane timetabling
- Agenda scheduling (meetings, appointments, maintenance jobs)
- Educational timetabling (scheduling lessons, courses, exams, conference presentations)
- Vehicle routing (planning vehicles with freight and/or people
- Bin packing (filling containers, trucks, ships and storage warehouses, but also cloud computers nodes)
- Job shop scheduling (planning assembly lines, machine queue planning, workforce task planning)
- Cutting stock (minimizing waste while cutting materials, e.g. paper, steel, etc..)
- Financial optimization (investment portfolio optimization, risk spreading)

- Planning problems - provide products and services with a limited set of constrained resources (employees, assets, time and money)

## Planning Problem ⌘

- Use Cases are NP-complete

- It's easy to verify a given solution to a problem in reasonable time
- There is no silver bullet to find the optimal solution of a problem in reasonable time

- Implication of the above

- brute force will usually take too long
- simple algorithm (largest first) will not satisfactory (from business perspective) solution

- OptaPlanner and NP-complete problems

- Planner does find:
- a good solution
- in reasonable time

## Constraints ⌘

- Hard negative

- cannot be broken
- e.g.
*trainer cannot provide two courses at the same time*

- Soft negative

- can be broken, but better solution do not break it
- e.g.
*trainer should have always at least one day off between courses*

- Soft positive (usually can be transformed to soft negative)

- e.g. trainers likes Drools courses

- Levels of constrains

- can be only hard
- can have many levels (hard, medium, soft)

## Score ⌘

- Constraints define the score calculation (AKA
**fitness function**) - Each solution of a planning problem can be graded with a score
- Score constraints are written in Drools rules (mvel, DSL) or Java rules
- If constraints are written in rules language, they benefit the optimization (Rete, etc...)

## Categories of solutions ⌘

- Possible solution

- is any solution (event if it breaks constraints)

- Feasible solution

- does not break any (negative) hard constraints
- relative to the number of possible solutions
- there may be no feasible solutions

- Optimal solution

- solution with the highest score
- usually there are 1 or a few optimal solutions
- There is always at least 1 optimal solution, even in the case that there are no feasible solutions and the optimal solution isn't feasible.

- The best solution found

- solution with the highest score found by an implementation in a given amount of time
- likely to be feasible and, given enough time, it's an optimal solution

## Possible solutions ⌘

- the number of possible solutions is usually huge (if calculated correctly), even with a small dataset
- most cases have
**a lot more**possible solutions than the minimal number of atoms in the known universe (10^{80}) - Because there is no silver bullet to find the optimal solution, any implementation is forced to evaluate at least a subset of all those possible solutions.

- OptaPlanner supports several optimization algorithms to reduce the number of solutions
- it's impossible to tell in advance which algorithm is better
- you can benchmark and switch optimization algorithm (in a config file)

## Presentation

- Go with the Cloud and Nqueen examples

## Exercises