**JBoss.org****Community Documentation**

**Table 3.1. Examples overview**

Example | Domain | Entity size | Value size | Search space | Competition? |
---|---|---|---|---|---|

N queens | 1 entity class 1 variable
| <= `256` | <= `256` | <= `10^616` | Pointless |

Cloud balancing | 1 entity class 1 variable
| <= `2400` | <= `800` | <= `10^6967` | No |

Traveling salesman | 1 entity class 1 chained variable
| <= `980` | <= `980` | <= `10^2927` | Unrealistic |

Manners 2009 | 1 entity class 1 variable
| <= `144` | <= `144` | <= `10^310` | Unrealistic |

Tennis club scheduling | 1 entity class 1 variable
| <= `72` | <= `7` | <= `10^60` | Unrealistic |

Course timetabling | 1 entity class 2 variables
| <= `434` | <= 25 and <= `20` | <= `10^1171` | Realistic |

Machine reassignment | 1 entity class 1 variable
| <= `50000` | <= `5000` | <= `10^184948` | Nearly realistic |

Vehicle routing | 1 entity class 1 chained variable 1 shadow entity class 1 automatic shadow variable
| <= `134` | <= `141` | <= `10^285` | Unrealistic |

Vehicle routing with time windows | Extra on Vehicle Routing: 1 shadow variable
| <= `250` | <= `1250` | <= `10^3000` | Unrealistic |

Project job scheduling | 1 entity class 2 variables 1 shadow variable
| <= `640` | <= ? and <= `?` | <= ? | Nearly realistic |

Hospital bed planning | 1 entity class 1 nullable variable
| <= `2750` | <= `471` | <= `10^6851` | Nearly realistic |

Exam timetabling | 1 entity class 2 variables
| <= `1096` | <= 80 and <= `49` | <= `10^3374` | Realistic |

Employee rostering | 1 entity class 1 variable
| <= `752` | <= `50` | <= `10^1277` | Realistic |

Traveling tournament | 1 entity class 1 variable
| <= `1560` | <= `78` | <= `10^2951` | Unrealistic |

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.

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

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 sports stars and 2 programmers shouldn't be the same kind.

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.

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).