By using our website you consent to accepting cookies in accordance with our Cookie policy

Latest News

OptaPlanner for RED Virtual Event

I have long been known as having a very good knowledge of excel and various tools. So it was not a surprise when I was approached by Shereen with the following question “Is it possible to arrange participants into group for the RED Virtual Event?”.

Such problem is similar to timetabling and wedding seating planning problems. I had looked into these problems a couple of years ago out of curiosity and had learnt that they are very difficult. I had recently seen a Hacker New post talking about a tool to optimize planning and scheduling tasks. So I decided to have a look at it if Shereen could share some of the data structure and needs.

OptaPlanner is a library – not a tool – and hence a planning tool needs to be developed. This was a successful and relatively easy process that I am sharing now.

I am not an expert on this type of problem and may use incorrect terminology or approach throughout. If you find such mistake, please notify me to allow these to be corrected.

Problem & data description

The problem and data description are key to defining a working approach in OptaPlanner. In my case, I used the tutorials at docs.jboss.org and quarkus.io to get started. These tutorials are covering the same problem but uses two different frameworks. These tutorials refer to the Domain Modelling Guidelines that proves very useful for defining the problem appropriately, particularly the definitions of the @PlanningEntity and @PlanningVariable. A read is highly recommended.

The RED Virtual Event is based on 3 rounds of short – 20 minutes - virtual meetings occurring within an hour-long event. Each virtual meeting is hosted by a Group Lead and are attended by up to 6 Participants. Each round consists of a set of Rendez Vous that represents a meeting between a Participant and a Group Lead.

The aim of the meeting is to maximise the mixing of Participants – ie a Participant should not attend a meeting hosted by the same Group Lead twice, and two Participants should not meet in multiple meetings if possible.

This post uses the same description strategy that is employed in the tutorials mentioned above.

Coding - The hard part?

Model the domain objects

The approach taken here is based on the goal of assigning each Rendez Vous to a Participant and a Group Lead as shown in the class diagram below:

Participant

The Participant class represents an individual taking part in the event. It is characterised by its name, that is assumed to be unique, and its office. One Participant take part in one and only one Rendez Vous in each round.

The Participant class looks as follows:

Group Lead

The Group Lead represents a specific individual taking part in the event. The Group Lead differs from the Participant in that he or she will be in charge of a group of Participants during each of the three rounds and animate the discussion during the round. The Group Lead is characterised by their name, assumed to be unique, and their office. A Group Lead will have the same status in each round.

The Group Lead class is as follows:

Rendez Vous

The Rendez Vous definition differs from the Lesson definition employed in the tutorial. This difference is  due to the definition of the problem based on my interpretation of the Domain Modelling Guidelines. The problem considered here is close the Employee shift rostering modelling guide presented, whereby a Shift is akin to the Group Lead and an Employee is akin to a Participant. The modelling guide introduce the concept of ShiftAssignment to allow the derivation of a good model, where the planning variable is a many to one relationship. In our context, we introduce the concept of Rendez Vous to represent the assignment of a Participant to a Group Lead at each round.

During solving, OptaPlanner changes the groupLead field to assign each Participant to a Group Lead. Because OptaPlanner changes this field, Rendez Vous is a planning entity and the Group Lead is a planning variable for the planning entity.

The Rendez Vous class only uses an identifier, simply represented by an integer, a round number, again an integer, and allocate a Group Lead and a Participant. The class is shown below:

Define the Constraints and Calculate the score

OptaPlanner uses a score approach to represent the quality of a solution. As mentioned in the jboss tutorial, “OptaPlanner looks for the best solution, which is the solution with the highest score found in the available time. It might be the optimal solution.”

In the current context, we are implementing an EasyScoreCalculator as it allows us to phrase the calculation of the score easily. Whilst this method is not optimal, it is sufficient for the use case employed here. The score is defined using the following constraints:

  • Hard constraints – that must not be broken – are set on:
    • The minimum and maximum number of participant in each group, respectively set to 3 and 7;
    • A requirement that a Participant does not see the same group lead more than once;
  • Soft constraints – that should not be broken if possible – are set on:
    • One soft constraint score for when the number of participants is away for the ideal number of participants per group – set to 5;
    • One soft constraint score for when a Participant meet another Participant more than once.

In addition, the first round aims to gather people from the same office. In this implementation, the office is driven by the group lead office with one soft constraint score for each participant that has an office differing from the group lead office.

The score calculation has been reworked in the following implementation using Java’s functional programming features:

Gather the domain objects in a planning solution

A TimeTable class wraps the Planning Entity and Planning Variables into a single dataset. This class differs from the similar class employed in the jboss tutorial in the following respects:

  • The event is organised over three rounds. Two approaches could be employed to take this peculiarity into account. The initial approach was to run a different optimisation on each round separately: optimise round 1, then optimise round 2, then optimise round 3 and repeat until an optimal solution over all rounds is obtained. In the updated approach, the solver optimises all 3 rounds together. This leads to not requiring an iterative solution, but as the domain is larger the solver takes a longer term to converge and hence is not necessarily faster.

The TimeTable class is implemented as follows and includes a number of helper functions to allow one to easily access a list of rendez vous based on participant and group lead:

Create the solver

The solver function, called from the main function, consists of the creation of the initial TimeTable that stores the list of Group Lead, Participants and Rendez Vous. The solver is created from an xml configuration file. In the approach used here, the solver is called multiple time on each round so that each round is optimised and the solution over the three rounds is also optimised.

The solver function is shown below:

In addition to the above function, a number of helper functions to generate the initial Time Table and save the solution are used. These are not shown here due to their relatively trivial nature.

The xml configuration file employed is as follows:

In Use

The ability of the above implementation is assessed using a made-up list of participant names, offices and group lead. These are generated using a simple spreadsheet, that is read directly, from popular baby names and most common last names. The input data is parametrised to allow for varying number of participants and group leads and number of groups. This parameters allows for the generation of easier solutions – solutions that will have a large number of participants with a ratio of participants to group of circa 5– or difficult solutions – with a small number of participants and ratio of participants to group that are significantly different to 5.

The following table shows an extract of an easy solution with 100 participants and 17 groups that is representative of the attendance to the event:

Name

Office

Group Lead

Sophia Smith

London

x

Liam Smith

Istanbul

x

Olivia Smith

Bicester

x

Noah Smith

Newcastle

x

Riley Smith

Dubai

x

Jackson Smith

Singapore

x

Emma Smith

Manila

x

Aiden Smith

London

x

Ava Smith

Istanbul

x

Elijah Smith

Bicester

x

Isabella Smith

Newcastle

x

Grayson Smith

Dubai

x

Aria Smith

Singapore

x

Lucas Smith

Manila

x

Aaliyah Smith

London

x

Oliver Smith

Istanbul

x

Amelia Smith

Bicester

x

Caden Smith

Newcastle

 

Mia Smith

Dubai

 

Mateo Smith

Singapore

 

Sophia Wang

Manila

 

Liam Wang

London

 

Olivia Wang

Istanbul

 

Noah Wang

Bicester

 

Riley Wang

Newcastle

 

Jackson Wang

Dubai

 

 

When employing this list of an input, the analysis output is as shown below. The output shows the number of group leads as 17 and the number of rendez vous as 83. This corresponds to a total number of participants, including the group leads of 100. The solution is solved iteratively over 11 iterations, indicating that each round is solved circa 4 times. At each iteration, a separate round is solved, typically to a result of 0 hard score – i.e not breaking any hard constraints – and -2 soft score – i.e indicating that some of the soft constraints aren’t necessarily respected. In addition, the overall hard and soft score are reported. These correspond to the calculation of the constraint over the 3 rounds. This is employed as a convergence criteria as it is possible that the current round be solved fully, but that other rounds may not be fully solved.

The final solution shows that no hard constraint is broken and that 6 soft constraints are broken. The soft constraint broken correspond to 2 groups in each round that have 4 participants, i.e one participant less than the ideal number of participants, hence totalling 6 broken soft constraints. The solver did optimise the distribution of participants so that a participant does not meet another participant more than once.

The following table shows an extract of the planning solution:

Round 0 group leaders:

Sophia Smith

Liam Smith

Olivia Smith

Noah Smith

Riley Smith

1:

Aaliyah Wang

Caden Smith

Sophia Wang

Riley Wang

Mia Smith

2:

Amelia Jones 

Liam Wang

Emma Jones 

Jackson Wang

Noah Johnson

3:

Sophia Johnson

Isabella Wang

Aria Jones 

Isabella Jones 

Oliver Johnson

4:

Liam Johnson

Caden Jones 

Emma Li 

Isabella Johnson

Isabella Li 

5:

Ava Li 

Aiden Li 

Oliver Li 

Mateo Li 

Aria Li 

 

Parting Word

This side project was very interesting in learning about OptaPlanner and its capabilities. It is understood that this open-source tool is used as the underlying engine for various planning tool – which clearly demonstrate its power. Its application to the problem described above was straightforward and a solution is reached with computational time of typically less than 1 minutes – so very reasonable.

Whilst it was not applied for the first event, it will be used for the second event as it has shown that it was able to generate these time-tables in significantly less time than a person would do. Interestingly, I have been asked if it could be possible to maximise the mixing of people for different offices as well. This change allowed me to have a look at rationalising some of the coding in what is presented in this post. But also shows the power of technology in unlocking further and further capabilities.

Ready to join the team?

If you think you have what it takes to join an award winning team and help RED continue its exciting journey, we want to hear from you.