第11章 Getting started with Java solvers: A cloud balancing example
An example demonstrates development of a basic Red Hat Business Optimizer solver using Java code.
Suppose your company owns a number of cloud computers and needs to run a number of processes on those computers. You must assign each process to a computer.
The following hard constraints must be fulfilled:
Every computer must be able to handle the minimum hardware requirements of the sum of its processes:
- CPU capacity: The CPU power of a computer must be at least the sum of the CPU power required by the processes assigned to that computer.
- Memory capacity: The RAM memory of a computer must be at least the sum of the RAM memory required by the processes assigned to that computer.
- Network capacity: The network bandwidth of a computer must be at least the sum of the network bandwidth required by the processes assigned to that computer.
The following soft constraints should be optimized:
Each computer that has one or more processes assigned incurs a maintenance cost (which is fixed per computer).
- Cost: Minimize the total maintenance cost.
This problem is a form of bin packing. In the following simplified example, we assign four processes to two computers with two 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 is not optimal, as it does not leave enough room to assign the yellow process D.
Business Optimizer finds a more optimal solution by using additional, smarter algorithms. It also scales: both in data (more processes, more computers) and constraints (more hardware requirements, other constraints).
The following summary applies to this example, as well as to an advanced implementation with more constraints that is described in 「Machine reassignment (Google ROADEF 2012)」:
| Problem size | Computers | Processes | Search space |
|---|---|---|---|
| 2computers-6processes | 2 | 6 | 64 |
| 3computers-9processes | 3 | 9 | 10^4 |
| 4computers-012processes | 4 | 12 | 10^7 |
| 100computers-300processes | 100 | 300 | 10^600 |
| 200computers-600processes | 200 | 600 | 10^1380 |
| 400computers-1200processes | 400 | 1200 | 10^3122 |
| 800computers-2400processes | 800 | 2400 | 10^6967 |
11.1. Domain Model Design リンクのコピーリンクがクリップボードにコピーされました!
Using a domain model helps determine which classes are planning entities and which of their properties are planning variables. It also helps to simplify constraints, improve performance, and increase flexibility for future needs.
11.1.1. Designing a domain model リンクのコピーリンクがクリップボードにコピーされました!
To create a domain model, define all the objects that represent the input data for the problem. In this example, the objects are processes and computers.
A separate object in the domain model must represent a full data set of the problem, which contains the input data as well as a solution. In this example, this object holds a list of computers and a list of processes. Each process is assigned to a computer; the distribution of processes between computers is the solution.
Procedure
- Draw a class diagram of your domain model.
- Normalize it to remove duplicate data.
Write down some sample instances for each class. Sample instances are entity properties that are relevant for planning purposes.
Computer: Represents a computer with certain hardware and maintenance costs.In this example, the sample instances for the
Computerclass arecpuPower,memory,networkBandwidth,cost.Process: Represents a process with a demand. Needs to be assigned to aComputerby Planner.Sample instances for
ProcessarerequiredCpuPower,requiredMemory, andrequiredNetworkBandwidth.CloudBalance: Represents the distribution of processes between computers. Contains everyComputerandProcessfor a certain data set.For an object representing the full data set and solution, a sample instance holding the score must be present. Business Optimizer can calculate and compare the scores for different solutions; the solution with the highest score is the optimal solution. Therefore, the sample instance for
CloudBalanceisscore.
Determine which relationships (or fields) change during planning:
Planning entity: The class (or classes) that Business Optimizer can change during solving. In this example, it is the class
Process, because we can move processes to different computers.- A class representing input data that Business Optimizer can not change is known as a problem fact.
-
Planning variable: The property (or properties) of a planning entity class that changes during solving. In this example, it is the property
computeron the classProcess. -
Planning solution: The class that represents a solution to the problem. This class must represent the full data set and contain all planning entities. In this example that is the class
CloudBalance.
In the UML class diagram below, the Business Optimizer concepts are already annotated:
You can find the class definitions for this example in the examples/sources/src/main/java/org/optaplanner/examples/cloudbalancing/domain directory.
11.1.2. The Computer Class リンクのコピーリンクがクリップボードにコピーされました!
The Computer class is a Java object that stores data, sometimes known as a POJO (Plain Old Java Object). Usually, you will have more of this kind of classes with input data.
例11.1 CloudComputer.java
public class CloudComputer ... {
private int cpuPower;
private int memory;
private int networkBandwidth;
private int cost;
... // getters
}
11.1.3. The Process Class リンクのコピーリンクがクリップボードにコピーされました!
The Process class is the class that is modified during solving.
We need to tell Business Optimizer that it can change the property computer. To do this, annotate the class with @PlanningEntity and annotate the getComputer() getter with @PlanningVariable.
Of course, the property computer needs a setter too, so Business Optimizer can change it during solving.
例11.2 CloudProcess.java
@PlanningEntity(...)
public class CloudProcess ... {
private int requiredCpuPower;
private int requiredMemory;
private int requiredNetworkBandwidth;
private CloudComputer computer;
... // getters
@PlanningVariable(valueRangeProviderRefs = {"computerRange"})
public CloudComputer getComputer() {
return computer;
}
public void setComputer(CloudComputer computer) {
computer = computer;
}
// ************************************************************************
// Complex methods
// ************************************************************************
...
}
Business Optimizer needs to know which values it can choose from to assign to the property computer. Those values are retrieved from the method CloudBalance.getComputerList() on the planning solution, which returns a list of all computers in the current data set.
The @PlanningVariable's valueRangeProviderRefs parameter on CloudProcess.getComputer() needs to match with the @ValueRangeProvider's id on CloudBalance.getComputerList().
You can also use annotations on fields instead of getters.
11.1.4. The CloudBalance Class リンクのコピーリンクがクリップボードにコピーされました!
The CloudBalance class has a @PlanningSolution annotation.
This class holds a list of all computers and processes. It represents both the planning problem and (if it is initialized) the planning solution.
The CloudBalance class has the following key attributes:
It holds a collection of processes that Business Optimizer can change. We annotate the getter
getProcessList()with@PlanningEntityCollectionProperty, so that Business Optimizer can retrieve the processes that it can change. To save a solution, Business Optimizer initializes a new instance of the class with the list of changed processes.-
It also has a
@PlanningScoreannotated propertyscore, which is theScoreof that solution in its current state. Business Optimizer automatically updates it when it calculates aScorefor a solution instance; therefore, this property needs a setter. -
Especially for score calculation with Drools, the property
computerListneeds to be annotated with a@ProblemFactCollectionPropertyso that Business Optimizer can retrieve a list of computers (problem facts) and make it available to the decision engine.
-
It also has a
例11.3 CloudBalance.java
@PlanningSolution
public class CloudBalance ... {
private List<CloudComputer> computerList;
private List<CloudProcess> processList;
private HardSoftScore score;
@ValueRangeProvider(id = "computerRange")
@ProblemFactCollectionProperty
public List<CloudComputer> getComputerList() {
return computerList;
}
@PlanningEntityCollectionProperty
public List<CloudProcess> getProcessList() {
return processList;
}
@PlanningScore
public HardSoftScore getScore() {
return score;
}
public void setScore(HardSoftScore score) {
this.score = score;
}
...
}