Artificial Intelligence planning with OptaPlanner by Geoffrey De smet

hi everybody um 16 years ago i started an open source project nothing serious you know just a hobby and people started using it and

i so i started adding uh test tests and documentation and stuff like that and after about seven years i had joined red hat meanwhile i was able to work on it full time

and now um yeah 16 years later it's used all across the globe for all kinds of planning problems so um let me uh go through this project and explain you

a bit a little bit more about it so what i'm going to show you today is we're going to try to solve this uh planning problem we're going to try to assign lessons to rooms into time slots and we're going to write an application

or i'll show you how to write an application when you click on the solve button that it actually solves that with artificial intelligence with our constraint solver so

um what's the problem i would like to show you to solve today where i want to focus on it's just one planning problem and there's many more planning problems but this is the one i want to focus on so you get an idea on how to code this

yourself is we need to assign a number of lessons to a number of rooms and two number of time slots so over here we can see we have four lessons math chemistry french and history we have a number of rooms

room a room b we have a number of time slots 8 30 to 9 30 9 30 to 10 30. and we

have to decide which lesson goes in which room at which time seems simple except for the fact of course that some of these lessons have the same students so for example math and chemistry are both

being taught to the ninth grade and chemistry and french are both being taught by the same teacher marie curie and french and history have the same students so what are we going to do we're going to write an application that

if you give this to constraint solver like optoplanner that you get a solution like this now if you look at the solution what you will see is it scheduled math and french at the same time which is fine because they don't

have the same students 9th grade and 10th grade they don't have the same teacher alan turing and marie curie so it's all fine right and same thing with chemistry and history so um

now why is this a difficult problem why why not solve this by hand well um if you remember from high school when they had to make make these uh back then um you

probably saw it sometimes took a couple of weeks for the lesson schedule to stabilize and it is a very difficult uh very difficult exercise and just to give you an idea why it's a very difficult

exercise is how long how many combinations would you have if you have like four lessons how many possible ways can you schedule those in these four four slots in these two rooms and two time slots if you have

400 lessons and in 400 slots how many ways could you do that so let's take a look at it so let's look at the size of the search space all possible ways you could

schedule those lessons into those rooms so here we have those uh four times those four slots basically so in two rooms and two time slots and we

could schedule matt in the first room room a at 8 30 or in room b at 8 30 or in room a at 9 30 or in room b at uh 9 30. right so that's four different

options now for each of these four list of options we can then take the next lesson we can take the history lesson and we could decide okay we're going to schedule that let's presume we've

scheduled maths in room a at 8 30. again

we could do the same with the history lesson you could immediately see of course this would look like a very bad idea because now we have two lessons in the same room at the same time but

for all of the other options here over there we also have four branches right so now we have already a bunch more combinations but much more all for just scheduling those two lessons into

four slots then of course if we try the third lesson and i've chosen to actually break this branch out and this branch out you can see we see here to assign the chemistry lesson um we could assign

it again you know first slot second slot third slot fourth slot uh or if we had actually went with this case where matt was at 8 30 and history was in the same room

we could then go through again put out chemistry in those four options and then of course we can do the same thing with the french lesson and you might say okay

this one this solution over here we have a mat in the first room um and history also but in different uh um vote at 830 different rooms and chemistry and french also assigned you might think this is a

good uh solution but in fact if you look from through the previous one uh previous slide you'll see that these actually have the same teacher so chemistry and french actually have the

same teacher and here history and french actually have the same students so those are actually not the feasible solutions and in fact one of the feasible solutions the ones where you say okay we can actually execute this plan the ones i showed earlier is in one of these

branches hidden away right so the question is how can we get to that feasible solution or that most optimal solution as quickly as possible right and how big is the search piece let's presumably look at every single

thing how big is the search piece here well for the first thing we had four different states now for the uh for you know assigning maths only when we started assigning history we had four times 4 different

states we had 16 different states it's 4 to the power 2.

when we sign the third one we go to 4 times 4 times 4 so 4 to the power 3 64 different states and for the fourth one we already have 265 different states

so how does this continue what happens when you have 400 lessons assigned to 400 slots 400 lessons times 400 slots

that's 400 to the power 400 which is something like 10 to the power 1040. so

let me just bring let me zoom in a little bit so if you assign n lessons the entire search piece is n to the power n if you assign 400 lessons that means it ends up something around 10 to

the power 1040.

anybody i got an idea how many uh atoms there are in the observable universe so think about every grain of salt every every atom in the area right here right count those all up including all of

those on all of our planets and all of our suns and and the stars we can see in the sky right well that's about 10 to the power 80.

so um so what happens if we can do this more optimally right because you could if you go back here you could say okay the moment i actually assign these here in the same room at the same time i

don't have to look at any of those branches below there all the branches over here these branches here i don't have to look of those so i can probably throw 99 of this search tree away

if you throw 99 away of a number of 10 to the power 1040 your search base is 10 to the power 1038.

you have it's a drop in the ocean right so you need much much smarter algorithms than than than doing some smart decisions there right or very different algorithms so

this kind of planning problems is not just for us lesson scheduling not just high schools have this kind of planning problems but also for example employee rostering you want to assign a number of shifts to a number of employees and you

have to decide which employee does which which shift at which time right so here we have a morning shift an afternoon shift and evening shifts and we are assigning these two employees with

different skills so here we have two nurses an engineer and a designer and um then of course we have a number of what we call constraints now constraints come in two forms typically well actually

sometimes more than two but the in the simple cases recommend two forms hard constraints and soft constraints so hard constraints are things like this you only want to have one shift per day per employee

right uh you only when a certain skill requires a certain shift requires a certain skill so for example this afternoon shift requires the nurse skill we want to make sure we assign somebody

with that skill here in engineering skill we need signed engineer now if you do this of course in the hospital what you would get is um for

example to work in the maternity uh department uh to do shift there you need to have a certain skill uh but uh this the nurses who work who have that skill can also do normal normal shifts right

so it's a much more you know closer variety than of course nurses and engineers skill but it's the same principle and then of course you might have have hard constraints like certain contracts certain employees can

only work during the week and cannot do night work or things like that and on top of that you have soft constraints soft constraints are things like you can only work five consecutive shifts in a row um and uh we want to do forward

rotation which is really really good for the health of of the ner of the of the employees for example forward notation rotation means is that if you have a morning shift you can have an evening shift the next day

but if you have an evening shift you don't want to get a morning shift the next day because between those two shifts there's only eight hours it's not enough time to go home get some food and actually have a good night's sleep right

and so that also means that that the servers you know they will not do their job as well if they didn't have a good night's sleep right so there's it's good for them for not just the employee but also for the

um the organization right and um the big one here is the day off requests right um so what is the off request a nurse says for example or you know of one of the employees or security guards if you're assigning security

hours they say okay i want to be friday off because i like to go out on friday and other other employees might say i want to be you know wednesday afternoon off because i want to take care of my grandchildren right and the more we can

say yes you get your preferable days off the better right and so we can take more of these requests in in account by automating this and we can uh we've done tests with this we've seen

this in production we can say yes half of the time more so basically means you know we make them let's say 50 happier uh depending on how you measure of course now employee rostering is all great and

all fine and applies to all kinds of you know any employee that's not working nine to five i would argue but arguably the most interesting vehicle the most interesting planning problem is

probably vehicle routing so in vehicle routing what do we need to do is we need to send the number of vehicles to a number of locations across the country to do these particular dots we in this case were for example

delivering items but it also could be for example a technician that has to install something with people's home let's say a telco or needs to go to certain locations to fix the electricity

grid or you know anything you can think of and what we want to do is we want to uh optimize their routes right so we have to decide which vehicle and which driver

which technician goes to which location and in which order do they do that there's number of constraints of course so if you're delivering items that could be capacity constraints like here 20 tons if you're actually a technician who

does have to do a certain amount of work there it would be the amount of hours they can drive around and by the time they what time they need back for example eight hours and then they need to be able to get back you might have

have certain skills or certain um you know things on the vehicle like in this case uh for to deliver here you need to have an armed vehicle because it's an expensive delivery you might be dealing with time windows we promised

the customer order location there that we would arrive there but in the morning or between 8 and 10 right and of course the big thing you want to do is you want to reduce the amount of travel time

you have any idea how much travel time we could actually reduce if we automate this versus what is happening now in production right so we had this one case

with tens of thousands of vehicles and their management expected a one percent driving time reduction and would have saved them literally you know millions

right um it was 25 less driving time so they vastly underestimated this um so they were quite happy with that what

was the results of that the result is year over year they reduced their co2 emissions output by tens of millions of kilograms uh every year as of since they put this in production

um i was quite happy about that because if you calculate it it's like flying from um i guess brussels to new york 25 uh times a day right you know 25 persons

doing that flight back and forth actually so that's every single day what what the amount of co2 they they uh save they were quite happy about the fact that it saved them 100 millions

of dollars per year um so um yeah that was that was a big shock so that's why i would argue vehicle rafting is really the the number one um

interesting case especially if you're interested in these kinds of results but there's many more there's maintenance scheduling you know doing grids or equipments elevators escalators

uh there's agenda scheduling when you want to assign court hearings uh there's two or tv advertisements there's job shop scheduling when you were building things like a car in in a factory you

need to figure out uh which uh which uh thing on the on the on the car happens in which order and you can optimize that and and so forth and so forth you want to reduce your make spend and things like that so

the world is full of planning problems if you've ever walked into an airport there are security guards there those need to be that's shift assignment there's gate there that's flight that's planes to gate

assignment uh the gates the the flight's taking off which airplane is actually taking off and it's flying which direction that's uh another planning problem um which crew is going into which

uh air uh flights um and and uh coming back in with other flights it's all planning problems the world is full of them um and so one solution there is our uh ai

constraint solve for optoplanner which is open source apache license so it's fully open source um it's sponsored by red hat by the way and so um you can just use it and many people do

you can use it from java but you can also use it from kotlin and scala so we have an example in java and in kotlin we have scala users out there we don't have an example out of the box you can use it from plain java just

embed it you can use it from quarkus and you can use it from spring so we have a quarkx extension and a spring starter which you can use and uh yeah you can use it for maven and gradle and we actually have examples for all of this

so we have a java plain java example we have a quarkus one a spring one and maven and some of the you know all of these three actually built both with maven and gradle um and we have many different use cases

also and those only built with maple but the the basic tree actually showed that how to do it with cradle2 so we're going to build this application right so let's see uh how do we do that

um so i've already started an app an app so i've already started a project and i've already put some things in there i've in this particular case i've chosen to go with quarkus and

i've already exposed the rest service and with some json i've pushed that to in a browser with a nice ui to visualize that school time tabling and i've uh hooked it up to a relational database

where we store the things there is no ai in this yet so at this point so let me just show you that i have that here so this is the application

there's a few bunch of coding here but just to prove if i actually go in here and i look for let's say opta planner right you will see there's no opto planner in here yet i do have already

put optoplanner part of the palm so it is already in the class but you can see that here i've taken the optopener qarcus extension um if you would have used spring you would use the spring starter if you

would have used uh plain java then you would just add optoplanar core directly but yeah the this gives it makes it a bit easier to integrate so

um here we go okay so um let's take a talk a little take a uh take a look at the domain so what's the domain behind us so we want to implement

this case so what are the main classes how would the domain classes look behind this so um we have um a time slot and a room class so the time

class has a day of week this comes from uh java time of course day of week is monday tuesday wednesday and so forth please don't ever use anything else but

please never use java until the date right you are going to run into problems there always use java.time

um and these kinds of objects and then there's a start time and an end time that's a local time again from java.time

um i don't have a date in here why not if you look at the problem a minute ago we actually are scheduling a week's worth of lessons and we'll copy paste that every week that's how the high

schools do it however if you look at different use cases for example for university you will see you probably have this domain a little bit differently because you'll probably actually be not this scheduling one week

that you copy paste every week but uh you know an entire semester where every date might be completely different right um so and and so depending on your model you will you will do things differently

there but in this case it's quite simple we just have a day of week and then from when till when the times of this then we have a room class which has a name something like you know room a room b room c

and then we have a lesson class which has a subject like math french history right and a teacher like marie curie alan turing and so forth and then we a student group 9th grade 10th grade

and so forth and we're going to have to assign these lessons to time slot and to room right so the time so then the room are actually not filled in before we get have our a for before our

ai solver actually start solving this for us right so uh let's take a look at the coding behind this i will start up the application with maven quark as dev right now so here we go um

let's okay here we go so maven carcass dev if i now go to localhost

this is a localhost let me check here so uh the reason i'm starting up in dev mode is because as i start adding things you will see the results of that immediately you might see there was a warning here the warning was just the

thing that it says okay you have an optoplanner extension in there but there's actually no optoplanner code in there which uh like i showed earlier so we'll be adding that in a minute here we

go localhost this is the application so we have our rooms rooms a b c here we have a number of time slots here we have number on assigned lessons and the ai's job will be to take each of

these lessons um about 20 or so and put them into these time slots and these rooms and make sure that we fulfill all of the constraints constraints are things like

we don't want to have two lessons in the same room at the same time right but also we don't want to have two teachers teaching two lessons at the same time or two students having to attend the same student same lesson at the same time and that's

why we have these buttons here on the top so we can easily switch okay what how does it look like per teacher and per student group okay so let's take a look at the code behind that um here's the domain classes

here we go um so we have a room class as i uh mentioned earlier the room class just has the name as you can see but also all

of my entities have a database id i've put this into the database with a simple gpa indentation saying this is an entity this is the database id that needs to be generated by the database and beyond

this there's just some getters and setters in this of course as a java right and then time slot very similar we have the id again and then we have those three properties i

showed day of week monday tuesday wednesday start time let's say 8 30 and then end time 9 30 for example right and again for the rest just getters and setters um and then we have a lesson class right

and the lesson is again we put it in database that's why the entity thing there and we have uh an id subject math french and so forth teacher mariqui and so for student group

nine grade and so forth the time slots and the room and you can see these are many to one relationships in jpa because multiple lessons will actually end up in the same time slots but hopefully not in

the same temple and the same room for for two lessons right um then i also have a timetable class this is the class that i sent to the to the to the front end because i need a way to take all of my rooms all of my

time so it's all of my lessons and say okay i ship it to the to the client so this is what my rest service actually returns say okay give me your timetable and this is the thing it returns and

this is also what i showed in the ui um i save everything into a database um so i have these this is from panache it's very similar to spring data if you're familiar with that but it

basically says okay i want something which this is a lesson repository where i can say okay please save this lesson please find all my lessons and so forth and when i actually look at the rest

service that says okay load me the the timetable what i do is i create a new timetable object and i from the database i list all of the timeslots i

list all of the rooms and i list all of the lessons as you can see here i sort them by some properties of course and that is the timetable i give back to the client and i play with there's some test

data you saw so and that's being done here there's a test data thing here where i inject those repositories that that allow me access to the database i listen to the startup

event and i say when every time this corkus application starts up i am i want to create this test data right and put that in the database so you can see i created time slots here i can share the rooms and the lessons now

let's have some fun i'm going to actually change one of these rooms let's say this is the devoxx uk room and so when i change it here just to see if it all

works you can see the change happens here immediately right so um and immediately refresh should give an idea on what happens there behind the scenes this is corker's death playing for us so

what happens is uh when we start up it compiles the resources creates the schema insert inserts the test data um every time we then ask or give me the index you know give me that that the

this thing right it says okay i'll just execute the sql queries but if we actually change something in our id if we change one of the sources what actually happens is cork is detected and says okay wait a second the next time

you ask for the get index right the next time we hit that refresh button on the top of our browser but it actually says i'm going to trigger restart and instead of just doing the sql queries it's going to compile the change sources drop the

schema insert the test data then actually do the rest request and return all that and that takes less than a second and just to show you that it takes less than a second it took well it

took a second here that's oh uh probably some let's try this again why this is more than a second so let's go to something else room e or something let's refresh here

maybe have something running in the background oh let's refresh here here we go and that took the live route less than a second so that looks better right so that's really nice and we're going to use that in a minute once we start

adding some optional stuff so let's start doing that here we go so let's add some ai planning optimization um so

we add in the opto planner extension in our architecture and um [Music] then we need to hear tell obtainer what can you change can optoplanar say okay i am going to change the subject of a

lesson instead of teaching maths will teach i don't know some something else right um music right instead of or the teacher right instead of marie teaching

chemistry uh we'll give that to you know um indiana jones or something like that right so of course they can't so what opt can actually change is the time slot and the

room right everything everything else is not the decision that our ai can make so we need to tell opto planner what are the decisions you can make what can i change and we do

that by annotating those particular properties with the planning variable so we tell opto planner you can ch you can pick the time slots and you can pick the room those are planning variables now anything any class that has one or more

planning variables needs to have a planning entity annotation that's just a way to know for opt-out planner to know okay in this class there are things that i need to change and um

it and it needs us for a very number of reasons okay so before we give the problem to opt-off planner so let's say we have 20 lessons right and we have ten time slots and and

two rooms or three rooms or whatever um before we give the pro those lessons to opto planner all of those lessons do not uh are have time slot null and ull have have the room annual those are not

filled in after wrapped up planner solves it they will all be filled in so that's what what's this doing for us right so um okay let's start coding that

so we go here we go to our lesson class and we're going to tell them okay this is so this is a class where something changes during planning so this is an at planning uh entity right

um and then the time slot and the room are the two fee the two things that we want autopilot to fill in for us so we'll make this planning a variable the time slot and for the room we will

do the same now can optoplanner just say okay you want me to fill in a timeslot i'll just create one for you create a new time slot sunday evening 10 am right but

it doesn't work like that right it has to pick from the time slots we give it to this and so somewhere we're going to have a we need to get a range of time slots so what i'm going to do here is i'm going to say

i'm going to provide you value range provider with the value range so i'm going to call this the time slot range and somewhere else you'll see where we have a list of our time so i'll say okay that the id of that value range is times

of the range and that's when operator knows okay for this 20 lessons here for each of those 20 lessons these are the for example 10 times those i can pick from right um and then of course we have the same

for the room so for again for the room somewhere we'll have to make a room range a list of rooms and then operator can choose from those um okay fair enough and then

some advice this is usually the difficult the most difficult part when you start with optoplanner what is my planning entity what changes during planning and what are my planning variables making those choices very

important we have a domain modeling guide in our documentation around that if you see if you find that difficult in your case and some for some planning problems it is difficult

read that modeling guide go through it and help you make the right choices on how to design that the rest of this is actually much simpler it's always the same but i'll take you through it anyway because of

course we want this to actually run in a sec in a few seconds so the timetable is actually that that class that has a list of all of our rooms in our lesson and our time source right it's also the time table is also

the the the the instance we give to opera we'll call the solve method and in the solve method there will be one thing we give it and that's our timetable instance it will solve that and it will

give us back another timetable instance right so what we're going to do is we're going to say okay when when it's solved it's actually planning solution so we're going to assign an annotate this with the

planning solution annotation so that means this is the thing we're going to give to optopar is going to solve it for us and give it back um in that timetable solution we have a number of lessons right this is our

lesson list so optoplayer needs to find where are those instances that i can change right and that's why in this lesson list we have to tell them okay this is actually our planning entity collection property which literally

means this is a collection for example a list or a set of planning entities and this is the property that whole zones right so that's how we tell up the planner pick those that's where you'll find your list

of lessons that's the ones you need to start assigning and then looks into the lesson class to see okay there's the planning variables there on rooms and time slots so i'll need to assign those

again we need to we need to find what what list of uh time slots we can choose from this that's over here that's our time sub list so we're going to provide a value range and this is the id and the

id will make that the same as in the other one right so this is the time slot range so by annotating this value range provider here we can we can make sure that in the lesson side

that to fill in this particular variable on each of the lesson instances it will choose from this list of time slots right in a similar way we can do that here value

range provider is the room range here we go now when opto planner actually solves this it will try to quantify how good the solution is and it will do that through something called a score

and more more particularly in this case we're going to use a hard soft score because we only care about hard and soft constraints in this particular case so you there's different variations on that but

most cases will start with a hard and soft score so we're going to actually put a field on here this is the score field and an opto planner after it's solved once it's solving it it will

actually say oh it would actually put the quality of our solu of our solution into that uh scoring so after we're done we can actually check do we have a feasible solution you know don't we have you know are we sure we

don't break any constraints and it can also tell us you know how if we break soft constraints how many soft constraints we have broken into each degree we need to annotate that with the planning score annotation so optoplanar

knows okay that's that's where that score field is okay now we'll also need constraints right this is our model now what what are our goals where do we want to get to

right this is what we give him and then he tells us back the decisions but we also need to tell them what are the what are the goals right so what i'm going to do is i'm going to create a constraint provider and that gives us our goals our

constraints our hard and soft constraints but for right now and so to do that you implement the constraints provider interface constraint provider interface

i'll just generate this method here and for now i'm going to just return no constraints just an empty list of an empty array of constraints right um so basically we're going to tell them

you can do whatever you want and we'll see the results of that quite soon and we can start playing with that by adding some constraints now we still need to hook it up right so if i

actually click in that button over here let me just show you if i click in that button over here we'll get an exception and the reason we get an exception is because

if we go to the code here [Music] yeah here we go there's an exception because in this method as you can see there's a no such you know unsupported operation exception so that's the part

we actually have to implement right now and so that's what i'll be doing doing right now and then we can see how auto planner assigns our lessons what i'm going to do so how do you solve a problem with upload planner you use

the solver manager which has that solve method so i'm going to inject a solver manager so if you work in for example spring

that you would auto wire solver manager and then uh this oh now this and this solver manager will be of type will be solving timetables for us right

it's a particular one to solve that kind of problems and anytime we ask it to do something we can give it a job id and uh we can choose that type too and here i've chosen a long type so that could

also be a string or uid this is only when you would be solving times it would be interesting if you would be solving timetables of middle multiple schools right you're great recreating

you know a service or something where you can solve all of the timetables for all of the schools let's say here in england and then um you could actually solve be solving multiple at the same time and each one has a different uh

problem id and and you could then say okay i want a long there or one a uuid there or something like that so in our source method so when we push that button what we're going to do is we're going to say okay

solver manager please solve and listen what's the listen thing well i want to see every time opto planner finds a new better solution a better solution to this problem i want to

immediately see that in my ui and so by listening that means that every time it does it immediately will store the better solution into the database so when my ui comes around it can

immediately show that right the ui does have a two second refresh you could also if you have a if you don't do a pulling approach but you actually have like um a websocket or something you could also push it back to

the client immediately but in this case i've chosen a simpler replica a simpler approach so what i get in and solve and listen method i get i have three parameters the first one is just the job id it's

basically the uh but i'm just going to hardcode that onto one because i only have one timetable so i'm not going to worry about this in this simple case

and um then i have uh two methods read methods and the right methods the read method gives me that problem id that one l and

i need to and uh i need to say okay load the timetable so i have a load timetable method here right which i shown earlier which says okay i create a new timetable by listing all of the time slots all the rooms and all of the

lessons you can see this is transactional what's really cool about qarcus is even though this is a protected methods which i'm calling from the same class the transactional thing actually works it's not ignored

and then so this is how i load the problem and the second is i need to save it so when i have a timetable how do i need to save this and i'm going to call a save method i have set up here which is going to

take just show you that save method here again transactional is going to go through all of the lessons and then find the same lesson in the database and set

the time slot and the room uh the same as as the one i've just sent it to right for those this might be a bit strange to see for some people if you're not too familiar

with jpa but uh this is about how how jpa managed the you know the the um what they call it the context right so um here we go

maybe we want to terminate it earlier we can do that here too so we can just say okay solver manager when this when you call the stop solving magnet minute method please do terminate early and

particularly that particular job of this this you know the same job you started here if you want to terminate that early um so let's take a look we do a refresh we'll scroll down here and do a refresh

here here we go quark has restarted i can click the solve method and it starts solving for us like instead there's a polling mixing mechanism so with two second delay until you see the results and what has all

planner done for us it says okay i'll do that for you i'll assign all of your lessons in room a at 8 30. there are no constraints i can do whatever i want so that looks

that's a problematic right that's not something we can actually send to the schools and say this is the new schedule right maybe the students will like it just one hour of lessons and then can they come home but

not not good in reality so how can we implement those constraints now so we could say so there's hard and soft constraints so again hard constraints must not be

broken soft constraints we don't want to break them but if we have to we will right and as men as little as possible of them may be weighted some constraints are some soft constraints are more important than other soft constraints

right one way you could do this this way right so what you could do is you say okay how do i detect if two two lessons are assigned in the same room at the same time how do we solve it that's uh if we go to our problem here that we

don't start assigning all of those lessons in the same room at the same time so we could say okay we create a hard score zero and then we go through all of the lessons

and then we go through all of the other lessons and if those two lessons are in the same time slot right and in the same room we're going to reduce the hard score by one and we probably also want to check in there to make sure that we

don't penalize that if they're actually the same lesson a and b and then we can make return a hard score this and we support this you can do this i don't recommend to doing it why not

well there's a couple of problems with this there's two big performance problems there's a scalability problem with this and a performance problem with this scalability the biggest problem is it's not incremental

so that means when optopanel wants to go through about a hundred thousand timetables per second that's what it likes to do try to actually try out a hundred thousand uh

you know score a hundred thousand timetables per second there's no way you can get to that with this kind of code because when the room of the matte lesson changes right the entire and it

says okay let me take the math lesson and let me swap that with the french license for example let's say the history lessons for example it would it will it will and it runs down this entire piece of code it will actually check if french and chemistry use the

same room that doesn't scale it really that's that's a big o notation verse uh of scalability so instead of that what you want to do is deltas

now and we have an interface for that too and that's a one-way ticket into um you know the asylum because it's it's it's it's very very difficult to write this kind of code and listen to the

change events and and do the deltas and so forth um i've written a couple and um six months later you look at them and you go like what does this do and then when you need to add an extra constraint it's it's very very painful and

difficult so we have the option that we we actually uh recommend and that's our what we call our constraint streams api and i'm going to show you that here

right now so i'm going to add here a constraint call it the room conflict constraint and i'm going to pass my constraint factory that's the thing that is going to build the

constraints that helps me build the constraints so here we have a room conflict constraint so i'm going to say okay constraint factory what i want you to do

this is more functional and i'll see that in a minute um what i want you to do is i want you to do for each of the lessons all right i want you and that's important lessons

i want you to join that like in sql very this is very sql like but you can actually run any sign of code with any other lesson and then when

the these two lessons are in the same room at the same time i want you to penalize that so that's the general thing of things you do for reach you might do some joints and stuff like that some

filters and you end up in a penalize so it and the so let's take a look at the for reach with the join here any two lessons no because if these lessons are in not in

the same room or not at the same time it's actually fine right we only want to penalize if they're in the same room at the same time so what we're going to do is we're going to say okay i want to do an equal constraint here

where i say lesson is actually the same room and also lesson is actually the same the joiners equal

lesson is actually the same time shot now for the record um you can do for each of a lesson with another type of object doesn't need to be a a lesson again and then you can actually specify

how do you get the room from the lesson from the left side and how do you get it from the right side and so forth um you know this is this is just the the most condensed form of the api i'm showing you but it's very very broad and very

very there's many many methods there that you can use a very rich api now there's not an additional advantage on this because by doing it this way internally

optoprinter can do indexing and hashing for you which is another big performance gain because i can check if i take a lesson and instead i don't need to go through all of the other lessons to to combine it with that

i can actually just do in an index lookup find the same lesson within the same room in the same timeline and immediately see if they are um you know if if if we should do a penalize or not

um so that that's it's that's the second big gain you get by switching to something like the uh constraints frames api so anyway if this happens we're going to say this is a room conflict and

we're going to hit up the planner on the head so don't do this with a heart constraint right and this is just one hard but you could actually say of heart and say okay it's seven hard points but i'll keep it simple and just say it's a

one heart thing so let's take a look at what happens now if i go here i do a refresh here we go we click the solve button optoplanar assigned all of the lessons for us

this stuff starts looking better right so we don't have uh no lessons in the same room at the same time but this is easy right you could do that you could just take the lessons just start

pinning them up and problem solved but there's more constraints why is this so difficult why is planning so difficult here's the teachers marie curie i hope she can be in two

places at the same time because she's teaching french and critics at 9 30 at the same time on tuesday so that's not a good schedule here right this is not a feasible schedule here's the student

groups we want some students to be in two places at the same time right chemistry and math at the same time here so that's not a good thing so what we can do is we can say okay

i want to have a teacher conflict here we go um here we go and i'm going to have a constraint for that teacher conflict so what we do is we say

okay um i'm going to for every teacher actually can copy paste the code from here so let's do that for a second so what i can say okay for every lesson

joined that with every other lesson where they don't i don't care if they have the same room or not i just care if they have the same teacher and if those teachers are if it's the same teacher for those two lessons and it's actually at the same time slot then we're asking

a teacher to be in two places at the same time then we have a teacher conflict right and again let's penalize this as a hard constraint we do refresh here there you go we click the solve button

it's solving we see the results here this looks okay we go by teacher see this is now feasible marie curie can actually do her schedule and but again we still have problems with

the students so let's do that again for students too here we go so we have uh stood student group conflict

uh i'll just copy this one right say okay we have a student group conflict here if they have not the same teacher but the same student group then

this is student group conflict so again for a lesson join that with any other lesson that's in the steam that has the same student group same teacher same time slot and then of course hit up the pattern ahead we don't want it we could

actually do the reverse too we could actually reward that too which is something we don't want to do here but if you say i want to write a positive constraint because i like being positive um then that's possible but most

constraints are typically written you know more naturally in a negative way you typically things you don't want to see in the planning you want to penalize that but there's a few cases where you you would write positive

constraints anyway let's try that out hit the refresh button here click the solve here we go looks good this is feasible no no room

conflicts no teacher conflicts no student groups conflicts right now um you could do more of this right if you look at this this teacher schedule you could argue yeah this is a feasible

schedule schedule but will our teachers be happy we'll yeah here darren he has to come for one hour on monday morning and then for one hour on tuesday morning

we have marie curie here she has all of these separate blocks so um what if we can we not make sure that you know can we not fix that too and that's what something you would do in

soft constraints why you will not be able to create a compact schedule uh and make everybody perfectly happy but what you can do is you can for example say i want to minimize the amount of time that

happens or you might even want to do it fairly right you might want to say okay um the person who is worst off with the schedule we want them that person to be as best off as possible and then the

second person first off and then the third person worst off uh we supported an optoplanner that will take me a little bit more than the time i have left to explain so i'll not jump in it actually a lot more it's it's a fairly

mathematical uh problem but you have support on that so you don't have to worry about that you can just reuse you use what we have right so um and there's other constraints you could have for example for the students

you might want to avoid having two like here two math lessons in a row um you might you know you might wanna say okay i want more variety in the schedule and of course we can add that uh easily too

but that's out of the scope for today so um if you wanna get started with optoplanner um i warmly recommend you to go to the optoplanar website and uh

there's a you can find documentation there and and so forth but there's also clone the quickstarts code there and i'll just show you right now if we go here here we go talktoan.org here there's a clone the

quick starts code you click on that um so if you don't know what to do this evening oh i double clicked something else here you clone this repository and you will

find the example just showing you here in use cases uh school time uh school time tabling here as you can see you'll find many other use cases vehicle routing maintenance scheduling plea

rostering vaccination scheduling uh order picking and so forth and um if you want to see them in other technologies here's technologies you can see okay i want the spring version i

want the kotlin version um we even have python but that's uh that's called optapi not optoplanar that's that's that's much further away than the other stuff

we have one with activemq so you can try all this out so do try it out and this is the code to run it and if there's any questions i'll happily answer those

thank you for listening okay yes uh how good is this in when you compare it to for example google or tools

where is this deterministic satisfaction problem solving so for vehicle routing we beat them it's quite simple uh you do have to in opt

turn on nearby selection which is not turned on by default but um so i've i've been in multiple cases where we were in direct competition uh the last one was a

an academic competition but also with a couple of uh customers like uh you know really big cases of vehicle routing and um they clearly saw that planner just uh you

know one quote i had i'm not sure if it was google or anymore tools but they were trying google or tools too one quote i've once heard is that we did in five minutes what took the others three hours

to do so um yeah we feel quite comfortable in that regards is that true for everything for all planning cases um for vehicle routing so definitely when you scale out

uh you know we will definitely when but um there are cases of so like share sketching we we do well but there are particular cases of of which work well

better in the so our tool is actually two different solvers right it's the vehicle routing solver that they have which is very problem specific which is hard to customize by the way too but

that's the one we clearly beat there and then they have the one which is more linear programming style where you add your constraints as mathematical equations right which is

a fun thing on its own and so i have actually a benchmark of that against our cloud balancing one where we also win uh when we scale out uh but when you

scale down we do see that it becomes interesting so um your mileage may vary but um if you run into you know contact us ping me on twitter or whatever and i'm happy to look take a look at all theories because you know we want to be

the best and but they're they're they're good decent competition uh they're uh yeah they're we respect them uh yeah definitely yeah uh

okay thanks um i tried the opt-out planner like 10 years ago did the base uh engine changed

since then or just improved or that there was a radical change um so many things changed in 10 years as you can imagine so the biggest one you

probably saw is that i was not writing my constraints in drl but in plain java so code highlighting debugging all that kind of fun stuff faster so

even though on under hood we still use similar technologies no not we use some some interesting technologies there uh like the the rule engine we have an implementation we have an action experimental implementation of

an alternative there too um so we're always making it faster it you will see that it's much faster uh you will also see we have better integration with all of the other toolkits we have more algorithms so the default algorithm

these days is late acceptance hill climbing but the original one was uh taboo search at the time ten years ago i think we were still using taboo search why would you care not really but it's

like garbage collection tuning if you want to tune for the best possible results specifically for your use case we have something called opt upon our benchmarker and we have more algorithms now you can play with and tune with and

to pick one which is best for your use case most users don't even do that but you know one percent of 100 million dollars is kind of worth doing it so

it kind of depends on the use case um the what else we have multithreaded solving which is really fun so you can use more of your course to solve one dataset okay thank you

thank you sorry i came in a bit like um with regard to the so is that only uh used for planning or can you use it for other solving other problems uh only used for planning good question

um planning scheduling it the the problems are typically the same so theoretically so the real answer to that question is you

can you only want to use it on nb heart problems or np complete problems we're basically saying um i'm not going to give you an answer here that that's that's that's that makes sense right because

um it's if if you go on wikipedia you can find a good definition of that but and there's like three thousands of these kinds of problems

uh some of them might um there's like i know it's been used for for game setting up the the so there's a few cases where you would

do it would you not consider it planning not for an adversarial um adversarial cases but for cases where you would set up a first

playing field or something like that but generally it's mostly planning and scheduling problems that's that's that's your short answer i think i think we're out of time i'll answer

your your question uh yeah let's answer the door maybe i think okay thanks