https://training-course-material.com/index.php?action=history&feed=atom&title=OptaPlannerOptaPlanner - Revision history2026-05-13T22:05:23ZRevision history for this page on the wikiMediaWiki 1.45.1https://training-course-material.com/index.php?title=OptaPlanner&diff=23999&oldid=prevCesar Chew at 19:02, 24 November 20142014-11-24T19:02:41Z<p></p>
<p><b>New page</b></p><div>{{Cat|Drools}}<br />
<br />
<slideshow style="nobleprog" headingmark="⌘" incmark="…" scaled="true" font="Trebuchet MS" ><br />
;title: OptaPlanner<br />
;author: Bernard Szlachta (NobleProg Ltd)<br />
</slideshow><br />
<br />
== What is OptaPlanner ⌘ ==<br />
* "OptaPlanner is a lightweight, embeddable planning engine that optimizes planning problems"<br />
* Apache Software License 2.0 <br />
* 100% pure Java<sup>TM</sup> <br />
* Combines optimization heuristics and metaheuristics with very efficient score calculation (Drools Expert i.e. Rete or backward chaining)<br />
<br />
== Use cases ⌘ ==<br />
* Shift rostering (timetabling)<br />
* Trainer, plane timetabling<br />
* Agenda scheduling (meetings, appointments, maintenance jobs)<br />
* Educational timetabling (scheduling lessons, courses, exams, conference presentations)<br />
* Vehicle routing (planning vehicles with freight and/or people<br />
* Bin packing (filling containers, trucks, ships and storage warehouses, but also cloud computers nodes)<br />
* Job shop scheduling (planning assembly lines, machine queue planning, workforce task planning)<br />
* Cutting stock (minimizing waste while cutting materials, e.g. paper, steel, etc..) <br />
* Financial optimization (investment portfolio optimization, risk spreading)<br />
<br />
* Planning problems - provide products and services with a limited set of constrained resources (employees, assets, time and money)<br />
<br />
== Planning Problem ⌘ ==<br />
<br />
; Use Cases are NP-complete:<br />
* It's easy to verify a given solution to a problem in reasonable time<br />
* There is no silver bullet to find the optimal solution of a problem in reasonable time<br />
<br />
; Implication of the above:<br />
* brute force will usually take too long<br />
* simple algorithm (largest first) will not satisfactory (from business perspective) solution<br />
<br />
; OptaPlanner and NP-complete problems<br />
* Planner does find:<br />
** a good solution<br />
** in reasonable time<br />
<br />
== Constraints ⌘ ==<br />
; Hard negative<br />
* cannot be broken<br />
* e.g. ''trainer cannot provide two courses at the same time''<br />
<br />
; Soft negative<br />
* can be broken, but better solution do not break it<br />
* e.g. ''trainer should have always at least one day off between courses''<br />
<br />
; Soft positive (usually can be transformed to soft negative)<br />
* e.g. trainers likes Drools courses<br />
<br />
; Levels of constrains<br />
* can be only hard<br />
* can have many levels (hard, medium, soft) <br />
<br />
== Score ⌘ ==<br />
* Constraints define the score calculation (AKA '''fitness function''')<br />
* Each solution of a planning problem can be graded with a score<br />
* Score constraints are written in Drools rules (mvel, DSL) or Java rules<br />
* If constraints are written in rules language, they benefit the optimization (Rete, etc...)<br />
<br />
<br />
== Categories of solutions ⌘ ==<br />
; Possible solution <br />
* is any solution (event if it breaks constraints)<br />
<br />
; Feasible solution <br />
* does not break any (negative) hard constraints<br />
* relative to the number of possible solutions<br />
* there may be no feasible solutions<br />
<br />
; Optimal solution <br />
* solution with the highest score<br />
* usually there are 1 or a few optimal solutions<br />
* 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.<br />
<br />
; The best solution found <br />
* solution with the highest score found by an implementation in a given amount of time<br />
* likely to be feasible and, given enough time, it's an optimal solution<br />
<br />
== Possible solutions ⌘ ==<br />
* the number of possible solutions is usually huge (if calculated correctly), even with a small dataset<br />
* most cases have '''a lot more''' possible solutions than the minimal number of atoms in the known universe (10<sup>80</sup>)<br />
* 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.<br />
<br />
<br />
* OptaPlanner supports several optimization algorithms to reduce the number of solutions<br />
* it's impossible to tell in advance which algorithm is better<br />
* you can benchmark and switch optimization algorithm (in a config file)<br />
<br />
== Presentation ==<br />
* Go with the Cloud and Nqueen examples<br />
<br />
== Exercises ==<br />
# [http://docs.jboss.org/drools/release/latestFinal/optaplanner-docs/html_single/#examplesOverview Extend existing constraints]<br />
<br />
<!--http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#d0e871--></div>Cesar Chew