JBoss.orgCommunity Documentation

Chapter 2. Quick start

2.1. Cloud balancing tutorial
2.1.1. Problem statement
2.1.2. Domain model
2.1.3. Main method
2.1.4. Solver configuration
2.1.5. Domain model
2.1.6. Score configuration
2.1.7. Beyond this tutorial

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.


This code above basically does this:

  • Build the Solver.

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

  • Solve the problem.

  • Display the result.

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

Take a look at the solver configuration:

Example 2.2. 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 consists out of 3 parts:

  • Domain model configuration: What can Planner change?

  • Score configuration: What should Planner optimize?

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

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

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


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:


The values that Planner can chose from for the field computer, are retrieved from a method on the Solution implementation: CloudBalance.getComputerList().

The class CloudBalance implements the Solution interface. It holds a list of all computers and processes. It has a property score which is the Score of that Solution instance in it's current state:

Example 2.5. 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>();
        facts.addAll(computerList);
        // 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();
            clonedProcessList.add(clonedProcess);
        }
        clone.processList = clonedProcessList;
        clone.score = score;
        return clone;
    }
    ...
}

The method getProblemFacts() is only needed for score calculation with Drools. It's not needed with 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.

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 (hardware requirements) and as little as possible soft constraints broken (maintenance cost).

There are several ways to implement the score function:

Let's look at 2 of those:

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.

Example 2.6. CloudBalance.java

public class CloudBalancingSimpleScoreCalculator implements SimpleScoreCalculator<CloudBalance> {


    public Score calculateScore(CloudBalance cloudBalance) {
        Map<CloudComputer, Integer> cpuPowerUsageMap = new HashMap<>();
        ...
        for (CloudComputer computer : cloudBalance.getComputerList()) {
            cpuPowerUsageMap.put(computer, 0);
            ...
        }
        Set<CloudComputer> usedComputerSet = new HashSet<>();
        visitProcessList(cpuPowerUsageMap, ...,
                usedComputerSet, cloudBalance.getProcessList());
        int hardScore = sumHardScore(cpuPowerUsageMap, ...);
        int softScore = sumSoftScore(usedComputerSet);
        return DefaultHardAndSoftScore.valueOf(hardScore, softScore);
    }
    private void visitProcessList(Map<CloudComputer, Integer> cpuPowerUsageMap, ...
            Set<CloudComputer> usedComputerSet, List<CloudProcess> processList) {
        // We loop through the processList only once for performance
        for (CloudProcess process : processList) {
            CloudComputer computer = process.getComputer();
            if (computer != null) {
                int cpuPowerUsage = cpuPowerUsageMap.get(computer) + process.getRequiredCpuPower();
                cpuPowerUsageMap.put(computer, cpuPowerUsage);
                ...
                usedComputerSet.add(computer);
            }
        }
    }
    private int sumHardScore(Map<CloudComputer, Integer> cpuPowerUsageMap, ...) {
        int hardScore = 0;
        for (Map.Entry<CloudComputer, Integer> usageEntry : cpuPowerUsageMap.entrySet()) {
            CloudComputer computer = usageEntry.getKey();
            int cpuPowerAvailable = computer.getCpuPower() - usageEntry.getValue();
            if (cpuPowerAvailable < 0) {
                hardScore += cpuPowerAvailable;
            }
        }
        ...
        return hardScore;
    }
    private int sumSoftScore(Set<CloudComputer> usedComputerSet) {
        int softScore = 0;
        for (CloudComputer usedComputer : usedComputerSet) {
            softScore -= usedComputer.getCost();
        }
        return softScore;
    }
}

Despite that the code above is optimized with Maps to only go through the processList 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.

To use Drools 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:

Example 2.7. 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: