JBoss.orgCommunity Documentation

Chapter 2. Use cases and examples

2.1. Introduction
2.2. The n queens example
2.2.1. Problem statement
2.2.2. Solution(s)
2.2.3. Screenshot
2.2.4. Problem size
2.2.5. Domain class diagram
2.3. The Manners 2009 example
2.3.1. Problem statement
2.4. The Traveling Salesman Problem (TSP) example
2.4.1. Problem statement
2.5. The Traveling Tournament Problem (TTP) example
2.5.1. Problem statement
2.5.2. Simple and smart implementation
2.5.3. Problem size
2.6. Cloud balancing
2.6.1. Problem statement
2.7. The ITC 2007 curriculum course example
2.7.1. Problem statement
2.8. The ITC 2007 examination example
2.8.1. Problem statement
2.8.2. Problem size
2.8.3. Domain class diagram
2.9. The patient admission scheduling (PAS) example (hospital bed planning)
2.9.1. Problem statement
2.10. The INRC 2010 nurse rostering example
2.10.1. Problem statement

2.1. Introduction

Drools Planner has several examples. In this manual we explain Drools Planner mainly using the n queens example. So it's advisable to read at least the section about that example. For advanced users, the following examples are recommended: curriculum course and nurse rostering.

You can find the source code of all these examples in the drools source distribution and also in git under drools-planner/drools-planner-examples.

2.2. The n queens example

The n queens puzzle is a puzzle with the following constraints:

The most common n queens puzzle is the 8 queens puzzle, with n = 8. We 'll explain Drools Planner using the 4 queens puzzle as the primary example.

A proposed solution could be:

A wrong solution for the 4 queens puzzle

Figure 2.1. A wrong solution for the 4 queens puzzle


The above solution is wrong because queens A1 and B0 can attack each other (as can queens B0 and D0). Removing queen B0 would respect the "no 2 queens can attack each other" constraint, but would break the "place n queens" constraint.

Below is a correct solution:

A correct solution for the 4 queens puzzle

Figure 2.2. A correct solution for the 4 queens puzzle


All the constraints have been met, so the solution is correct. Note that most n queens puzzles have multiple correct solutions. We 'll focus on finding a single correct solution for a given n, not on finding the number of possible correct solutions for a given n.

Here is a screenshot of the example:

Screenshot of the n queens example

Figure 2.3. Screenshot of the n queens example


These numbers might give you some insight on the size of this problem.

Table 2.1. NQueens problem size

# queens (n)# possible solutions (each queen its own column)# feasible solutions (= optimal in this use case)# optimal solutions# optimal out of # possible
4256221 out of 128
81677721664641 out of 262144
161844674407370955161614772512147725121 out of 1248720872503
321.46150163733090291820368483e+48???
643.94020061963944792122790401e+115???
nn ^ n?# feasible solutions?

The Drools Planner implementation has not been optimized because it functions as a beginner example. Nevertheless, it can easily handle 64 queens.

Use a good domain model: it will be easier to understand and solve your planning problem with Drools Planner. This is the domain model for the n queens example:

public class Column {
    
    private int index;

    // ... getters and setters
}
public class Row {
    
    private int index;

    // ... getters and setters
}
public class Queen {
    
    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}
public class NQueens implements Solution<SimpleScore> {
    
    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

A Queen instance has a Column (for example: 0 is column A, 1 is column B, ...) and a Row (its row, for example: 0 is row 0, 1 is row 1, ...). Based on the column and the row, the ascending diagonal line as well as the descending diagonal line can be calculated. The column and row indexes start from the upper left corner of the chessboard.

Table 2.2. A solution for the 4 queens puzzle shown in the domain model

A solutionQueencolumnIndexrowIndexascendingDiagonalIndex (columnIndex + rowIndex)descendingDiagonalIndex (columnIndex - rowIndex)
A1011 (**)-1
B010 (*)1 (**)1
C22240
D030 (*)33

When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.

A single NQueens instance contains a list of all Queen instances. It is the Solution implementation which will be supplied to, solved by and retrieved from the Solver. Notice that in the 4 queens example, NQueens's getN() method will always return 4.

2.3. The Manners 2009 example

In Manners 2009, miss Manners is throwing a party again.

Drools Expert also has the normal miss Manners examples (which is much smaller) and employs a brute force heurstic to solve it. Drools Planner's implementation employs far more scalable heuristics while still using Drools Expert to calculate the score..

2.4. The Traveling Salesman Problem (TSP) example

Given a list of cities, find the shortest tour for a salesman that visits each city exactly once. See the wikipedia definition of the traveling Salesman Problem.

It is one of the most intensively studied problems in computational mathematics. Yet, in the real world, it's often only part of a planning problem, along with other constraints, such as employee shift time constraints.

2.5. The Traveling Tournament Problem (TTP) example

Schedule matches between N teams with the following hard constraints:

and the following soft constraint:

The problem is defined on this webpage (which contains several world records too).

There are 2 implementations (simple and smart) to demonstrate the importance of some performance tips. The DroolsPlannerExamplesApp always runs the smart implementation, but with these commands you can compare the 2 implementations yourself:

$ mvn exec:exec -Dexec.mainClass="org.drools.planner.examples.travelingtournament.app.simple.SimpleTravelingTournamentApp"
...
$ mvn exec:exec -Dexec.mainClass="org.drools.planner.examples.travelingtournament.app.smart.SmartTravelingTournamentApp"
...

The smart implementation performs and scales exponentially better than the simple implementation.

These numbers might give you some insight on the size of this problem.

Table 2.3. Traveling tournament problem size

# teams# days# matches# possible solutions (simple)# possible solutions (smart)# feasible solutions# optimal solutions
46122176782336<= 518400?1?
610301000000000000000000000000000000<= 47784725839872000000?1?
814561.52464943788290465606136043e+64<= 5.77608277425558771434498864e+43?1?
1018909.43029892325559280477052413e+112<= 1.07573451027871200629339068e+79?1?
12221321.58414112478195320415135060e+177<= 2.01650616733413376416949843e+126?1?
14261823.35080635695103223315189511e+257<= 1.73513467024013808570420241e+186?1?
16302403.22924601799855400751522483e+354<= 2.45064610271441678267620602e+259?1?
n2 * (n - 1)n * (n - 1)(2 * (n - 1)) ^ (n * (n - 1))<= (((2 * (n - 1))!) ^ (n / 2))?1?

2.6. Cloud balancing

There are a number of computers available. Assign a list of processes on those computers.

Hard constraints:

Soft constraints:

This is a form of bin packing.

2.7. The ITC 2007 curriculum course example

Schedule lectures into rooms and time periods.

The problem is defined by the International Timetabling Competition 2007 track 3.

2.8. The ITC 2007 examination example

Schedule each exam into a period and into a room. Multiple exams can share the same room during the same period.

There are a number of hard constraints that cannot be broken:

There are also a number of soft constraints that should be minimized (each of which has parameterized penalty's):

It uses large test data sets of real-life universities.

The problem is defined by the International Timetabling Competition 2007 track 1.

These numbers might give you some insight on the size of this problem.

Table 2.4. Examination problem size

Set# students# exams/topics# periods# rooms# possible solutions# feasible solutions# optimal solutions
exam_comp_set1788360754710^1564?1?
exam_comp_set212484870404910^2864?1?
exam_comp_set316365934364810^3023?1?
exam_comp_set4442127321110^360?1?
exam_comp_set58719101842310^2138?1?
exam_comp_set6790924216810^509?1?
exam_comp_set7137951096802810^3671?1?
exam_comp_set8771859880810^1678?1?
?stpr(p * r) ^ e?1?

Geoffrey De Smet (the Drools Planner lead) finished 4th in the International Timetabling Competition 2007's examination track with a very early version of Drools Planner. Many improvements have been made since then.

Below you can see the main examination domain classes:

Examination domain class diagram

Figure 2.4. Examination domain class diagram


Notice that we've split up the exam concept into an Exam class and a Topic class. The Exam instances change during solving (this is the planning entity class), when they get another period or room property. The Topic, Period and Room instances never change during solving (these are problem facts, just like some other classes).

2.9. The patient admission scheduling (PAS) example (hospital bed planning)

In this problem, we have to assign each patient (that will come to the hospital) a bed for each night that the patient will stay in the hospital. Each bed belongs to a room and each room belongs to a department. The arrival and departure dates of the patients is fixed: only a bed needs to be assigned for each night.

There are a couple of hard constraints:

And of course, there are also some soft constraints:

The problem is defined on this webpage and the test data comes from real world hospitals.

2.10. The INRC 2010 nurse rostering example

Schedule nurses into shifts.

The problem is defined by the International Nurse Rostering Competition 2010.