OptaPlanner

title

OptaPlanner

author

Bernard Szlachta (NobleProg Ltd)

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⁸⁰)
• 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

1. Extend existing constraints