Performance Zone is brought to you in partnership with:

Geoffrey De Smet is the OptaPlanner lead. Geoffrey has posted 12 posts at DZone. You can read more from them at their website. View Full User Profile

06.05.2012
| 10419 views |

## Cloud balancing tutorial

### 1. Problem statement

Suppose your company owns a number of cloud computers and needs to run a number of processes on those computers. Assign each process to a computer under the following 4 constraints.

Hard constraints which must be fulfilled:

• Every computer must be able to handle the minimal hardware requirements of the sum of its processes:

• The CPU power of a computer must be at least the sum of the CPU power required by the processes assigned to that computer.

• The RAM memory of a computer must be at least the sum of the RAM memory required by the processes assigned to that computer.

• The network bandwidth of a computer must be at least the sum of the network bandwidth required by the processes assigned to that computer.

Soft constraints which should be optimized:

• Each computer that has one or more processes assigned, incurs a maintenance cost (which is fixed per computer).

• Minimize the total maintenance cost.

How would you do that? This problem is a form of bin packing. Here's a simplified example where we assign 4 processes to 2 computers with 2 constraints (CPU and RAM) with a simple algorithm:

The simple algorithm used here is the First Fit Decreasing algorithm, which assigns the bigger processes first and assigns the smaller processes to the remaining space. As you can see, it's not optimal, because it does not leave enough room to assign the yellow process D.

Drools Planner does find the more optimal solution fast, by using additional, smarter algorithms. And it scales too: both in data (more processes, more computers) and constraints (more hardware requirements, other constraints). So let's take a look how we can use Planner for this.

### 2. Domain model diagram

Let's start by taking a look at the domain model. It's pretty simple:

• Computer: represents a computer with certain hardware (CPU power, RAM memory, network bandwidth) and maintenance cost.

• Process: represents a process with a demand. Needs to be assigned to a Computer by Drools Planner.

• CloudBalance: represents a problem. Contains every Computer and Process for a certain data set.

In the UML class diagram above, the Planner concepts are already annotated:

• Planning entity: the class (or classes) that changes during planning. In this example that's the class Process.

• Planning variable: the property (or properties) of a planning entity class that changes during planning. In this examples, that's the property computer on the class Process.

• Solution: the class that represents a data set and contains all planning entities. In this example that's the class CloudBalance.

### 3. Main method

Try it yourself. Download and configure the examples in your favorite IDE. Run org.drools.planner.examples.cloudbalancing.app.CloudBalancingHelloWorld. By default, it is configured to run for 120 seconds. It will execute this code:

CloudBalancingHelloWorld.java

```public class CloudBalancingHelloWorld {

public static void main(String[] args) {
// Build the Solver
SolverFactory solverFactory = new XmlSolverFactory(
"/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
Solver solver = solverFactory.buildSolver();

// Load a problem with 400 computers and 1200 processes
CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

// Solve the problem
solver.setPlanningProblem(unsolvedCloudBalance);
solver.solve();
CloudBalance solvedCloudBalance = (CloudBalance) solver.getBestSolution();

// Display the result
System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
+ toDisplayString(solvedCloudBalance));
}

...

}```

The code above does this:

• Build the Solver based on a solver configuration (in this case an XML file).

```        SolverFactory solverFactory = new XmlSolverFactory(
"/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
Solver solver = solverFactory.buildSolver();```
• Load the problem. CloudBalancingGenerator generates a random problem: you'll replace this with a class that loads a real problem, for example from a database.

`        CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);`
• Solve the problem.

```        solver.setPlanningProblem(unsolvedCloudBalance);
solver.solve();
CloudBalance solvedCloudBalance = (CloudBalance) solver.getBestSolution();```
• Display the result.

```        System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
+ toDisplayString(solvedCloudBalance));```

The only non-obvious part is building the Solver. Let's examine that.

### 4. Solver configuration

Take a look at the solver configuration:

cloudBalancingSolverConfig.xml

```<?xml version="1.0" encoding="UTF-8"?>
<solver>
<!--<environmentMode>DEBUG</environmentMode>-->

<!-- Domain model configuration -->
<solutionClass>org.drools.planner.examples.cloudbalancing.domain.CloudBalance</solutionClass>
<planningEntityClass>org.drools.planner.examples.cloudbalancing.domain.CloudProcess</planningEntityClass>

<!-- Score configuration -->
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.cloudbalancing.solver.score.CloudBalancingSimpleScoreCalculator</simpleScoreCalculatorClass>
<!--<scoreDrl>/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
</scoreDirectorFactory>

<!-- Optimization algorithms configuration -->
<termination>
<maximumSecondsSpend>120</maximumSecondsSpend>
</termination>
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
<constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType>
</constructionHeuristic>
<localSearch>
<selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericChangeMoveFactory</moveFactoryClass>
</selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericSwapMoveFactory</moveFactoryClass>
</selector>
</selector>
<acceptor>
<planningEntityTabuSize>7</planningEntityTabuSize>
</acceptor>
<forager>
<minimalAcceptedSelection>1000</minimalAcceptedSelection>
</forager>
</localSearch>
</solver>```

This solver configuration consists out of 3 parts:

• Domain model configuration: What can Planner change? We need to make Planner aware of our domain classes:

```  <solutionClass>org.drools.planner.examples.cloudbalancing.domain.CloudBalance</solutionClass>
<planningEntityClass>org.drools.planner.examples.cloudbalancing.domain.CloudProcess</planningEntityClass>```
• Score configuration: How should Planner optimize the planning variables? Since we have hard and soft constraints, we use a HardAndSoftScore. But we also need to tell Planner how to calculate such the score, depending on our business requirements. Further down, we 'll look into 2 alternatives to calculate the score: using a simple Java implementation or using Drools DRL.

```  <scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.cloudbalancing.solver.score.CloudBalancingSimpleScoreCalculator</simpleScoreCalculatorClass>
<!--<scoreDrl>/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
</scoreDirectorFactory>```
• Optimization algorithms configuration: How should Planner optimize it? Don't worry about this for now: this is a good default configuration that works on most planning problems. It will already surpass human planners and most in-house implementations. Using the Planner benchmark toolkit, you can tweak it to get even better results.

```  <termination>
<maximumSecondsSpend>120</maximumSecondsSpend>
</termination>
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
<constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType>
</constructionHeuristic>
<localSearch>
<selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericChangeMoveFactory</moveFactoryClass>
</selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericSwapMoveFactory</moveFactoryClass>
</selector>
</selector>
<acceptor>
<planningEntityTabuSize>7</planningEntityTabuSize>
</acceptor>
<forager>
<minimalAcceptedSelection>1000</minimalAcceptedSelection>
</forager>
</localSearch>```

Let's examine the domain model classes and the score configuration.

### 5. Domain model implementation

5.1. The class Computer

The class Computer is a POJO (Plain Old Java Object), nothing special. Usually, you'll have more of these kind of classes.

CloudComputer.java

```public class CloudComputer ... {

private int cpuPower;
private int memory;
private int networkBandwidth;
private int cost;

... // getters

}```
5.2. The class Process

The class Process is a little bit special. We need to tell Planner that it can change the field computer, so we annotate the class with @PlanningEntity and the getter getComputer with @PlanningVariable:

CloudProcess.java

```@PlanningEntity(...)
public class CloudProcess ... {

private int requiredCpuPower;
private int requiredMemory;
private int requiredNetworkBandwidth;

private CloudComputer computer;

... // getters

@PlanningVariable(...)
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty = "computerList")
public CloudComputer getComputer() {
return computer;
}

public void setComputer(CloudComputer computer) {
computer = computer;
}

public CloudProcess clone() {
CloudProcess clone = new CloudProcess();
clone.id = id;
clone.requiredCpuPower = requiredCpuPower;
clone.requiredMemory = requiredMemory;
clone.requiredNetworkBandwidth = requiredNetworkBandwidth;
clone.computer = computer;
return clone;
}

...

}```

The values that Planner can chose from for the field computer, are retrieved from a method on the Solution implementation: CloudBalance.getComputerList() which returns a list of all computers in the current data set. We tell Planner about this by using the annotation @ValueRange.

The method clone() is used by the class CloudBalance.

5.3. The class CloudBalance

The class CloudBalance implements the Solution interface. It holds a list of all computers and processes. We need to tell Planner how to retrieve the collection of process which it can change, so we need to annotate the getter getProcessList with @PlanningEntityCollectionProperty.

The CloudBalance class also has a property score which is the Score of that Solution instance in it's current state:

CloudBalance.java

```public class CloudBalance ... implements Solution<HardAndSoftScore> {

private List<CloudComputer> computerList;

private List<CloudProcess> processList;

private HardAndSoftScore score;

public List<CloudComputer> getComputerList() {
return computerList;
}

@PlanningEntityCollectionProperty
public List<CloudProcess> getProcessList() {
return processList;
}

...

public HardAndSoftScore getScore() {
return score;
}

public void setScore(HardAndSoftScore score) {
this.score = score;
}

// ************************************************************************
// Complex methods
// ************************************************************************

public Collection<? extends Object> getProblemFacts() {
List<Object> facts = new ArrayList<Object>();
// Do not add the planning entity's (processList) because that will be done automatically
return facts;
}

/**
* Clone will only deep copy the {@link #processList}.
*/
public CloudBalance cloneSolution() {
CloudBalance clone = new CloudBalance();
clone.id = id;
clone.computerList = computerList;
List<CloudProcess> clonedProcessList = new ArrayList<CloudProcess>(
processList.size());
for (CloudProcess process : processList) {
CloudProcess clonedProcess = process.clone();
}
clone.processList = clonedProcessList;
clone.score = score;
return clone;
}

...

}```

The method getProblemFacts() is only needed for score calculation with Drools. It's not needed for the other score calculation types.

The method clone() is required. Planner uses it to make a clone of the best Solution in encounters during searching.

### 6. Score configuration

Planner will search for the Solution with the highest Score. We're using a HardAndSoftScore, which means Planner will look for the solution with no hard constraints broken (fulfill hardware requirements) and as little as possible soft constraints broken (minimize maintenance cost).

There are several ways to implement the score function:

• Simple Java

• Incremental Java

• Drools

Let's look at 2 different implementations:

6.1. Simple Java score configuration

One way to define a score function is to implement the interface SimpleScoreCalculator in plain Java.

```  <scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.cloudbalancing.solver.score.CloudBalancingSimpleScoreCalculator</simpleScoreCalculatorClass>
</scoreDirectorFactory>```

Just implement the method calculateScore(Solution) to return a DefaultHardAndSoftScore instance.

CloudBalancingSimpleScoreCalculator.java

```public class CloudBalancingSimpleScoreCalculator implements SimpleScoreCalculator<CloudBalance> {

/**
* A very simple implementation. The double loop can easily be removed by using Maps as shown in
*/
public HardAndSoftScore calculateScore(CloudBalance cloudBalance) {
int hardScore = 0;
int softScore = 0;
for (CloudComputer computer : cloudBalance.getComputerList()) {
int cpuPowerUsage = 0;
int memoryUsage = 0;
int networkBandwidthUsage = 0;
boolean used = false;

// Calculate usage
for (CloudProcess process : cloudBalance.getProcessList()) {
if (computer.equals(process.getComputer())) {
cpuPowerUsage += process.getRequiredCpuPower();
memoryUsage += process.getRequiredMemory();
networkBandwidthUsage += process.getRequiredNetworkBandwidth();
used = true;
}
}

// Hard constraints
int cpuPowerAvailable = computer.getCpuPower() - cpuPowerUsage;
if (cpuPowerAvailable < 0) {
hardScore += cpuPowerAvailable;
}
int memoryAvailable = computer.getMemory() - memoryUsage;
if (memoryAvailable < 0) {
hardScore += memoryAvailable;
}
int networkBandwidthAvailable = computer.getNetworkBandwidth() - networkBandwidthUsage;
if (networkBandwidthAvailable < 0) {
hardScore += networkBandwidthAvailable;
}

// Soft constraints
if (used) {
softScore -= computer.getCost();
}
}
return DefaultHardAndSoftScore.valueOf(hardScore, softScore);
}

}```

Even if we optimize the code above to use Maps to iterate through the processList only once, it is still slow because it doesn't do incremental score calculation. To fix that, either use an incremental Java score function or a Drools score function.

6.2. Drools score configuration

To use the Drools rule engine as a score function, simply add a scoreDrl resource in the classpath:

```  <scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<scoreDrl>/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>
</scoreDirectorFactory>```

First, we want to make sure that all computers have enough CPU, RAM and network bandwidth to support all their processes, so we make those hard constraints:

cloudBalancingScoreRules.drl - hard constraints

```...

import org.drools.planner.examples.cloudbalancing.domain.CloudBalance;
import org.drools.planner.examples.cloudbalancing.domain.CloudComputer;
import org.drools.planner.examples.cloudbalancing.domain.CloudProcess;

global HardAndSoftScoreHolder scoreHolder;

// ############################################################################
// Hard constraints
// ############################################################################

rule "requiredCpuPowerTotal"
when
\$computer : CloudComputer(\$cpuPower : cpuPower)
\$requiredCpuPowerTotal : Number(intValue > \$cpuPower) from accumulate(
CloudProcess(
computer == \$computer,
\$requiredCpuPower : requiredCpuPower),
sum(\$requiredCpuPower)
)
then
insertLogical(new IntConstraintOccurrence("requiredCpuPowerTotal", ConstraintType.NEGATIVE_HARD,
\$requiredCpuPowerTotal.intValue() - \$cpuPower,
\$computer));
end

rule "requiredMemoryTotal"
...
end

rule "requiredNetworkBandwidthTotal"
...
end

// ############################################################################
// Calculate hard score
// ############################################################################

// Accumulate hard constraints
rule "hardConstraintsBroken"
salience -1 // Do the other rules first (optional, for performance)
when
\$hardTotal : Number() from accumulate(
IntConstraintOccurrence(constraintType == ConstraintType.NEGATIVE_HARD, \$weight : weight),
sum(\$weight)
)
then
scoreHolder.setHardConstraintsBroken(\$hardTotal.intValue());
end```

Next, if those constraints are met, we want to minimize the maintenance cost, so we add that as a soft constraint:

cloudBalancingScoreRules.drl - soft constraints

```// ############################################################################
// Soft constraints
// ############################################################################

rule "computerCost"
when
\$computer : CloudComputer(\$cost : cost)
exists CloudProcess(computer == \$computer)
then
insertLogical(new IntConstraintOccurrence("computerCost", ConstraintType.NEGATIVE_SOFT,
\$cost,
\$computer));
end

// ############################################################################
// Calculate soft score
// ############################################################################

// Accumulate soft constraints
rule "softConstraintsBroken"
salience -1 // Do the other rules first (optional, for performance)
when
\$softTotal : Number() from accumulate(
IntConstraintOccurrence(constraintType == ConstraintType.NEGATIVE_SOFT, \$weight : weight),
sum(\$weight)
)
then
scoreHolder.setSoftConstraintsBroken(\$softTotal.intValue());
end```

If you use the Drools rule engine for score calculation, you can integrate with other Drools technologies, such as decision tables (XSL or web based), the Guvnor rule repository, ...

### 7. Beyond this tutorial

Now that this simple example works, you can go further. Try enriching the domain model and adding extra constraints:

• Each Process belongs to a Service. A computer can crash, so processes running the same service should be assigned to different computers.

• Each Computer is located in a Building. A building can burn down, so processes of the same services should be assigned to computers in different buildings.

Published at DZone with permission of its author, Geoffrey De Smet.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

### Jacob Feldman replied on Wed, 2012/06/06 - 5:27pm

Geoffrey,

Thank you for sharing a nice problem and its solution with your Drools Planner. I tried to model and solve the same problem using the standard JSR-331 "Constraint Programming API". Assuming that we have Java beans CloudComputer and CloudProcess with your attribute names in place, I added this CloudBalancer:

public class CloudBalancer {

`    static public void balance(CloudComputer[] computers, CloudProcess[] processes) {	long executionStart = System.currentTimeMillis();	Schedule s = ScheduleFactory.newSchedule("CloudBalancing",0,1);	// Create activities for all processes	Activity[] activities = new Activity[processes.length];	for (int i = 0; i < processes.length; i++) {	   activities[i] = s.activity(processes[i].getId(),1);	}	// Create resources for all computer memories and cpuPowers	Resource[] memories = new Resource[computers.length];	Resource[] cpuPowers = new Resource[computers.length];	for (int i = 0; i < computers.length; i++) {           memories[i] = s.resource(computers[i].getId(),computers[i].getMemory());	   cpuPowers[i] = s.resource(computers[i].getId(),computers[i].getCpuPower());	}	// Post constraints between required and available memories and cpuPowers	Var[][] processUsesComputerVars = new Var[processes.length][computers.length];	for (int i = 0; i < processes.length; i++) {	   for (int j = 0; j < computers.length; j++) {	     String name = "Process " + processes[i].getId() + " uses computer "                                               + computers[j].getId();	     processUsesComputerVars[i][j] = s.variable(name,0,1);	     Var requiredMemoryVar =                  processUsesComputerVars[i][j].multiply(processes[i].getRequiredMemory());	     activities[i].requires(memories[j],requiredMemoryVar).post();	     Var requiredCpuPowerVar =                  processUsesComputerVars[i][j].multiply(processes[i].getRequiredCpuPower());	     activities[i].requires(cpuPowers[j],requiredCpuPowerVar).post();	   }	}	// Post constraint "a process uses one and only one computer"	Var[] allVars = new Var[processes.length * computers.length];	Var[] allCostVars = new Var[processes.length * computers.length];	int n = 0;	for (int i = 0; i < processes.length; i++) {           Var[] assignedComputers = new Var[computers.length];	   for (int j = 0; j < computers.length; j++) {	      assignedComputers[j] = processUsesComputerVars[i][j];	      allCostVars[n] = processUsesComputerVars[i][j].multiply(computers[j].getCost());	      allVars[n++] = processUsesComputerVars[i][j];	   }	   s.post(assignedComputers, "=", 1);	}	Var totalCostVar = s.sum(allCostVars);	totalCostVar.setName("Total Cost"); 	Solver solver = s.getSolver();	solver.getSearchStrategy().setVars(allVars);	solver.traceSolutions(true);	Solution solution = solver.findOptimalSolution(totalCostVar);	if (solution != null) {	   for (int i = 0; i < allVars.length; i++) {	     if (allVars[i].getValue() == 1)	 	s.log(allVars[i].getName());	     }	} else {	     s.log("No solutions");	} 	long executionTime = System.currentTimeMillis() - executionStart;	System.out.println("Total Execution time: " + executionTime + " msec");    } `
` Here is a simple test:`
```    public static void main(String[] args) {
CloudComputer c1 = new CloudComputer();
c1.setId("1");
c1.setCpuPower(7);
c1.setMemory(6);
c1.setCost(100);
CloudComputer c2 = new CloudComputer();
c2.setId("2");
c2.setCpuPower(6);
c2.setMemory(6);
c2.setCost(80);
CloudComputer c3 = new CloudComputer();
c3.setId("3");
c3.setCpuPower(5);
c3.setMemory(3);
c3.setCost(50);

CloudProcess p1 = new CloudProcess();
p1.setId("A");
p1.setRequiredCpuPower(5);
p1.setRequiredMemory(5);
CloudProcess p2 = new CloudProcess();
p2.setId("B");
p2.setRequiredCpuPower(4);
p2.setRequiredMemory(3);
CloudProcess p3 = new CloudProcess();
p3.setId("C");
p3.setRequiredCpuPower(2);
p3.setRequiredMemory(3);
CloudProcess p4 = new CloudProcess();
p4.setId("D");
p4.setRequiredCpuPower(2);
p4.setRequiredMemory(1);

CloudComputer[] computers = { c1, c2, c3 };
CloudProcess[] processes = { p1, p2, p3, p4 };

CloudBalancer.balance(computers,processes);
} ```
`And here are the execution results:`
```JSR-331 Standard v.1.0.1 (release 6/05/2012)
JSR-331 Implementation based on Constrainer 5.4 (light)
Found a solution with Total Cost[330]
Found a solution with Total Cost[310]
Process A uses computer 1
Process B uses computer 3
Process C uses computer 2
Process D uses computer 2
Total Execution time: 275 msec```

This implementation uses a very basic JSR-331 Scheduler, and quite naturally represents computer's RAM and CPU as Resources while Processes are presented as Activities that require resources with initially unknown capacities.  It's quite easy to add similarly network bandwidth. I expect that the perfomance will stay good even when you deal with 100s or 1000s variables. Please send me your examples of large datasets to try.

It is also easy to model the problem without Scheduler using only basic JSR-331 constructs. I will include these examples in the oncoming  JSR-331 release 1.0.1 so you and other people would be able to try it yourself.

I think your impelmentation along with these ones nicely demonstrate the power of optimization techniques in general, and Constraint Programming in particular.

Best,

Jacob (jacobfeldman@openrules.com)

### Geoffrey De Smet replied on Thu, 2012/06/07 - 3:31am in response to: Jacob Feldman

Hi Jacob,

Thanks for the input and code comparison :)

How would JSR-331 implement a constraint which uses a richer domain model? For example: "Our company has a number of Locations. Every Computer is located in 1 Location. Each Process has an extra network bandwidth requirement based on how far the Process's users are from that location. It's a fast but complex calculation implemented in a method in the class Process: process.getExtraBandwidthFromLocation(Location)."

In Drools Planner, that constraint would look like this:

• Simple Java score implementation:
`networkBandwidthUsage += process.getRequiredNetworkBandwidth()    + process.getExtraBandwidthFromLocation(        computer.getLocation());`
• Or Drools score implementation:

\$computer : CloudComputer(\$networkBandwidth : networkBandwidth,
\$location : location)
\$requiredTotal : Number(intValue > \$networkBandwidth) from accumulate(
CloudProcess(
computer == \$computer,
\$a : requiredNetworkBandwidth),
\$b : getExtraBandwidthFromLocation(\$location)),
sum(\$a + \$b)
)

You can find the larger datasets here. The largest one has only 2400 processes and is easy for Drools Planner. But since CloudBalance is a toy problem, there are much better examples worth comparing:

Instead, compare with one of the real problems implemented in Planner that have faced international research competitions. They have a rich domain model, a higher number of constraints, more complex constraints and - most importantly - several real data sets (*). For example, I 'd love to compare with an ITC2007 examination implementation.

(*) Sometimes, such a dataset even has a LP pathological instance (for example in the nurse rostering competition, file medium_hint01). Such a dataset is very intresting: While a metaheuristics implementation (such as Drools Planner) crunches it like any other problem, a LP implementation can fail to get anywhere near a good result in reasonable time. So I can recommend implementing that example too and see how your implementation fares against that pathological dataset.