OptaPlanner

From Training Material
Revision as of 19:02, 24 November 2014 by Cesar Chew (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
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 JavaTM
  • 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 (1080)
  • 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