Table 3.1. Examples overview
| SpeExample | Domain | Size | Competition? | Special features used |
|---|---|---|---|---|
| N queens |
|
|
| None |
| Cloud balancing |
|
|
| |
| Traveling salesman |
|
|
| |
| Dinner party |
|
|
|
|
| Tennis club scheduling |
|
|
| |
| Course timetabling |
|
|
| |
| Machine reassignment |
|
|
| |
| Vehicle routing |
|
|
| |
| Vehicle routing with time windows | Extra on Vehicle routing:
|
|
| |
| Project job scheduling |
|
|
| |
| Hospital bed planning |
|
|
|
|
| Exam timetabling |
|
|
| |
| Employee rostering |
|
|
| |
| Traveling tournament |
|
|
| None |
A realistic competition is an official, independent competition:
that clearly defines a real-word use case
with real-world constraints
with multiple, real-world datasets
that expects reproducible results within a specific time limit on specific hardware
that has had serious participation from the academic and/or enterprise Operations Research community
These realistic competitions provide an objective comparison of OptaPlanner with competitive software and academic research.
This documentation heavily uses the 4 queens puzzle as the primary example.
The above solution is wrong because queens A1 and B0 can attack each
other (so 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:
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.
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
}
When 2 queens share the same column, row or diagonal line, such as (*) and (**), they can attack each other.
Given a list of cities, find the shortest tour for a salesman that visits each city exactly once.
The problem is defined by Wikipedia. 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 rostering constraints.
Miss Manners is throwing another dinner party.
This time she invited 144 guests and prepared 12 round tables with 12 seats each.
Every guest should sit next to someone (left and right) of the opposite gender.
And that neighbour should have at least one hobby in common with the guest.
And the 2 politicians, 2 doctors, 2 coaches and 2 programmers shouldn't be the same kind at a table.
Schedule each lecture into a timeslot and into a room.
The problem is defined by the International Timetabling Competition 2007 track 3.
The problem is defined by the Google ROADEF/EURO Challenge 2012.
Besides the basic case (CVRP), there is also a variant with time windows (CVRPTW).
The capacitated vehicle routing problem (CVRP) and it's timewindowed variant (CVRPTW) are defined by the VRP web.
CVRP instances (without time windows):
A-n32-k5 has 1 depots, 5 vehicles and 31 customers with a search space of 10^46. A-n33-k5 has 1 depots, 5 vehicles and 32 customers with a search space of 10^48. A-n33-k6 has 1 depots, 6 vehicles and 32 customers with a search space of 10^48. A-n34-k5 has 1 depots, 5 vehicles and 33 customers with a search space of 10^50. A-n36-k5 has 1 depots, 5 vehicles and 35 customers with a search space of 10^54. A-n37-k5 has 1 depots, 5 vehicles and 36 customers with a search space of 10^56. A-n37-k6 has 1 depots, 6 vehicles and 36 customers with a search space of 10^56. A-n38-k5 has 1 depots, 5 vehicles and 37 customers with a search space of 10^58. A-n39-k5 has 1 depots, 5 vehicles and 38 customers with a search space of 10^60. A-n39-k6 has 1 depots, 6 vehicles and 38 customers with a search space of 10^60. A-n44-k7 has 1 depots, 7 vehicles and 43 customers with a search space of 10^70. A-n45-k6 has 1 depots, 6 vehicles and 44 customers with a search space of 10^72. A-n45-k7 has 1 depots, 7 vehicles and 44 customers with a search space of 10^72. A-n46-k7 has 1 depots, 7 vehicles and 45 customers with a search space of 10^74. A-n48-k7 has 1 depots, 7 vehicles and 47 customers with a search space of 10^78. A-n53-k7 has 1 depots, 7 vehicles and 52 customers with a search space of 10^89. A-n54-k7 has 1 depots, 7 vehicles and 53 customers with a search space of 10^91. A-n55-k9 has 1 depots, 9 vehicles and 54 customers with a search space of 10^93. A-n60-k9 has 1 depots, 9 vehicles and 59 customers with a search space of 10^104. A-n61-k9 has 1 depots, 9 vehicles and 60 customers with a search space of 10^106. A-n62-k8 has 1 depots, 8 vehicles and 61 customers with a search space of 10^108. A-n63-k10 has 1 depots, 10 vehicles and 62 customers with a search space of 10^111. A-n63-k9 has 1 depots, 9 vehicles and 62 customers with a search space of 10^111. A-n64-k9 has 1 depots, 9 vehicles and 63 customers with a search space of 10^113. A-n65-k9 has 1 depots, 9 vehicles and 64 customers with a search space of 10^115. A-n69-k9 has 1 depots, 9 vehicles and 68 customers with a search space of 10^124. A-n80-k10 has 1 depots, 10 vehicles and 79 customers with a search space of 10^149. F-n135-k7 has 1 depots, 7 vehicles and 134 customers with a search space of 10^285. F-n45-k4 has 1 depots, 4 vehicles and 44 customers with a search space of 10^72. F-n72-k4 has 1 depots, 4 vehicles and 71 customers with a search space of 10^131.
CVRPTW instances (with time windows):
Solomon_025_C101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_C201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_R101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_R201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_RC101 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_025_RC201 has 1 depots, 25 vehicles and 25 customers with a search space of 10^34. Solomon_100_C101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_C201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_R101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_R201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_RC101 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Solomon_100_RC201 has 1 depots, 25 vehicles and 100 customers with a search space of 10^200. Homberger_0200_C1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_C2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_R1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_R2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_RC1_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0200_RC2_2_1 has 1 depots, 50 vehicles and 200 customers with a search space of 10^460. Homberger_0400_C1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_C2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_R1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_R2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_RC1_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0400_RC2_4_1 has 1 depots, 100 vehicles and 400 customers with a search space of 10^1040. Homberger_0600_C1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_C2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_R1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_R2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_RC1_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0600_RC2_6_1 has 1 depots, 150 vehicles and 600 customers with a search space of 10^1666. Homberger_0800_C1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_C2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_R1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_R2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_RC1_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_0800_RC2_8_1 has 1 depots, 200 vehicles and 800 customers with a search space of 10^2322. Homberger_1000_C110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_C210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_R110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_R210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_RC110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000. Homberger_1000_RC210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^3000.
The vehicle routing with timewindows domain model makes heavily use of shadow variables. This allows it to express its constraints more
naturally, because properties such as arrivalTime and departureTime, are
directly available on the domain model.
This problem features overconstrained datasets.
The problem is a variant on Kaho's Patient Scheduling and the datasets come from real world hospitals.
Soft constraints (each of which has a parametrized penalty):
Period spread: 2 exams that share students should be a number of periods apart.
Mixed durations: 2 exams that share a room should not have different durations.
Front load: Large exams should be scheduled earlier in the schedule.
Period penalty (specified per dataset): Some periods have a penalty when used.
Room penalty (specified per dataset): Some rooms have a penalty when used.
It uses large test data sets of real-life universities.
The problem is defined by the International Timetabling Competition 2007 track 1. Geoffrey De Smet finished 4th in that competition with a very early version of OptaPlanner. Many improvements have been made since then.
Below you can see the main examination domain classes:
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 their period or room property changes. The Topic,
Period and Room instances never change during solving (these are problem
facts, just like some other classes).
For each shift, assign a nurse to work that shift.
The problem is defined by the International Nurse Rostering Competition 2010.
Schedule matches between n teams.
The problem is defined on Michael Trick's website (which contains the world records too).