JBoss.orgCommunity Documentation

Chapter 4. Planner configuration

4.1. Overview
4.2. Solver configuration
4.2.1. Solver configuration by XML file
4.2.2. Solver configuration by Java API
4.3. Model your planning problem
4.3.1. Is this class a problem fact or planning entity?
4.3.2. Problem fact
4.3.3. Planning entity
4.3.4. Planning variable
4.3.5. Planning value and planning value ranges
4.3.6. Planning problem and planning solution
4.4. Use the Solver
4.4.1. The Solver interface
4.4.2. Solving a problem
4.4.3. Environment mode: Are there bugs in my code?
4.4.4. Logging level: What is the Solver doing?
4.4.5. Random number generator

Solving a planning problem with OptaPlanner consists out of 5 steps:

Build a Solver instance with the SolverFactory. Configure it with a solver configuration XML file, provided as a classpath resource (as definied by ClassLoader.getResource()):

       SolverFactory solverFactory = SolverFactory.createFromXmlResource(

               "org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml");
       Solver solver = solverFactory.buildSolver();

In a typical project (following the Maven directory structure), that solverConfig XML file would be located at $PROJECT_DIR/src/main/resources/org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml. Alternatively, a SolverFactory can be created from a File, an InputStream or a Reader with methods such as SolverFactory.createFromXmlFile(). However, for portability reasons, a classpath resource is recommended.

A solver configuration file looks something like this:


<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Define the model -->
  <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass>
  <planningEntityClass>org.optaplanner.examples.nqueens.domain.Queen</planningEntityClass>

  <!-- Define the score function -->
  <scoreDirectorFactory>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>

  <!-- Configure the optimization algorithm(s) -->
  <termination>
    ...
  </termination>
  <constructionHeuristic>
    ...
  </constructionHeuristic>
  <localSearch>
    ...
  </localSearch>
</solver>

Notice the 3 parts in it:

These various parts of a configuration are explained further in this manual.

OptaPlanner makes it relatively easy to switch optimization algorithm(s) just by changing the configuration. There's even a Benchmark utility which allows you to play out different configurations against each other and report the most appropriate configuration for your problem. You could for example play out tabu search versus simulated annealing, on 4 queens and 64 queens.

Look at a dataset of your planning problem. You 'll recognize domain classes in there, each of which can be categorized as one of these:

Ask yourself: What class changes during planning? Which class has variables that I want the Solver to change for me? That class is a planning entity. Most use cases have only 1 planning entity class.

Note

In real-time planning, problem facts can change during planning, because the problem itself changes. However, that doesn't make them planning entities.

A good model can greatly improve the success of your planning implementation. For inspiration, take a look at how the examples modeled their domain:

When in doubt, it's usually the many side of a many to one relationship that is the planning entity. For example in employee rostering, the planning entity class is ShiftAssignment, not Employee. Vehicle routing is special, because it uses a chained planning variable.

In OptaPlanner all problems facts and planning entities are plain old JavaBeans (POJO's). You can load them from a database (JDBC/JPA/JDO), an XML file, a data repository, a noSQL cloud, ...: OptaPlanner doesn't care.

A problem fact is any JavaBean (POJO) with getters that does not change during planning. Implementing the interface Serializable is recommended (but not required). For example in n queens, the columns and rows are problem facts:

public class Column implements Serializable {


    private int index;
    // ... getters
}
public class Row implements Serializable {


    private int index;
    // ... getters
}

A problem fact can reference other problem facts of course:

public class Course implements Serializable {


    private String code;
    private Teacher teacher; // Other problem fact
    private int lectureSize;
    private int minWorkingDaySize;
    private List<Curriculum> curriculumList; // Other problem facts
    private int studentSize;
    // ... getters
}

A problem fact class does not require any Planner specific code. For example, you can reuse your domain classes, which might have JPA annotations.

A planning entity is a JavaBean (POJO) that changes during solving, for example a Queen that changes to another row. A planning problem has multiple planning entities, for example for a single n queens problem, each Queen is a planning entity. But there's usually only 1 planning entity class, for example the Queen class.

A planning entity class needs to be annotated with the @PlanningEntity annotation.

Each planning entity class has 1 or more planning variables. It usually also has 1 or more defining properties. For example in n queens, a Queen is defined by its Column and has a planning variable Row. This means that a Queen's column never changes during solving, while its row does change.

@PlanningEntity

public class Queen {
    private Column column;
    // Planning variables: changes during planning, between score calculations.
    private Row row;
    // ... getters and setters
}

A planning entity class can have multiple planning variables. For example, a Lecture is defined by its Course and its index in that course (because 1 course has multiple lectures). Each Lecture needs to be scheduled into a Period and a Room so it has 2 planning variables (period and room). For example: the course Mathematics has 8 lectures per week, of which the first lecture is Monday morning at 08:00 in room 212.

@PlanningEntity

public class Lecture {
    private Course course;
    private int lectureIndexInCourse;
    // Planning variables: changes during planning, between score calculations.
    private Period period;
    private Room room;
    // ...
}

The solver configuration also needs to be made aware of each planning entity class:

<solver>

  ...
  <planningEntityClass>org.optaplanner.examples.nqueens.domain.Queen</planningEntityClass>
  ...
</solver>

Some uses cases have multiple planning entity classes. For example: route freight and trains into railway network arcs, where each freight can use multiple trains over its journey and each train can carry multiple freights per arc. Having multiple planning entity classes directly raises the implementation complexity of your use case.

Some optimization algorithms work more efficiently if they have an estimation of which planning entities are more difficult to plan. For example: in bin packing bigger items are harder to fit, in course scheduling lectures with more students are more difficult to schedule and in n queens the middle queens are more difficult to fit on the board.

Therefore, you can set a difficultyComparatorClass to the @PlanningEntity annotation:

@PlanningEntity(difficultyComparatorClass = CloudProcessDifficultyComparator.class)

public class CloudProcess {
    // ...
}
public class CloudProcessDifficultyComparator implements Comparator<CloudProcess> {


    public int compare(CloudProcess a, CloudProcess b) {
        return new CompareToBuilder()
                .append(a.getRequiredMultiplicand(), b.getRequiredMultiplicand())
                .append(a.getId(), b.getId())
                .toComparison();
    }
}

Alternatively, you can also set a difficultyWeightFactoryClass to the @PlanningEntity annotation, so you have access to the rest of the problem facts from the Solution too:

@PlanningEntity(difficultyWeightFactoryClass = QueenDifficultyWeightFactory.class)

public class Queen {
    // ...
}

See sorted selection for more information.

Important

Difficulty should be implemented ascending: easy entities are lower, difficult entities are higher. For example in bin packing: small item < medium item < big item.

Even though some algorithms start with the more difficult entities first, they just reverse the ordering.

None of the current planning variable state should be used to compare planning entity difficult. During construction heuristics, those variables are likely to be null anyway. For example, a Queen's row variable should not be used.

By default, an initialized planning variable cannot be null, so an initialized solution will never use null for any of its planning variables. In an over-constrained use case, this can be contra productive. For example: in task assignment with too many tasks for the workforce, we would rather leave low priority tasks unassigned instead of assigning them to an overloaded worker.

To allow an initialized planning variable to be null, set nullable to true:

    @PlanningVariable(..., nullable = true)

    public Worker getWorker() {
        return worker;
    }

Repeated planning (especially real-time planning) does not mix well with a nullable planning variable: every time the Solver starts or a problem fact change is made, the construction heuristics will try to initialize all the null variables again, which can be a huge waste of time. One way to deal with this, is to change when a planning entity should be reinitialized with an reinitializeVariableEntityFilter:

    @PlanningVariable(..., nullable = true, reinitializeVariableEntityFilter = ReinitializeTaskFilter.class)

    public Worker getWorker() {
        return worker;
    }

Each planning entity has its own set of possible planning values for a planning variable. For example, if a teacher can never teach in a room that does not belong to his department, lectures of that teacher can limit their room value range to the rooms of his department.

    @PlanningVariable(valueRangeProviderRefs = {"possibleRoomRange"})

    public Room getRoom() {
        return room;
    }
    @ValueRangeProvider(id = "possibleRoomRange")
    public List<Room> getPossibleRoomList() {
        return getCourse().getTeacher().getPossibleRoomList();
    }

Never use this to enforce a soft constraint (or even a hard constraint when the problem might not have a feasible solution). For example: Unless there is no other way, a teacher can not teach in a room that does not belong to his department. In this case, the teacher should not be limited in his room value range (because sometimes there is no other way).

A planning entity should not use other planning entities to determinate its value range. That would only try to make it solve the planning problem itself and interfere with the optimization algorithms.

Some optimization algorithms work more efficiently if they have an estimation of which planning values are stronger, which means they are more likely to satisfy a planning entity. For example: in bin packing bigger containers are more likely to fit an item and in course scheduling bigger rooms are less likely to break the student capacity constraint.

Therefore, you can set a strengthComparatorClass to the @PlanningVariable annotation:

    @PlanningVariable(..., strengthComparatorClass = CloudComputerStrengthComparator.class)

    public CloudComputer getComputer() {
        // ...
    }
public class CloudComputerStrengthComparator implements Comparator<CloudComputer> {


    public int compare(CloudComputer a, CloudComputer b) {
        return new CompareToBuilder()
                .append(a.getMultiplicand(), b.getMultiplicand())
                .append(b.getCost(), a.getCost()) // Descending (but this is debatable)
                .append(a.getId(), b.getId())
                .toComparison();
    }
}

Alternatively, you can also set a strengthWeightFactoryClass to the @PlanningVariable annotation, so you have access to the rest of the problem facts from the solution too:

    @PlanningVariable(..., strengthWeightFactoryClass = RowStrengthWeightFactory.class)

    public Row getRow() {
        // ...
    }

See sorted selection for more information.

Important

Strength should be implemented ascending: weaker values are lower, stronger values are higher. For example in bin packing: small container < medium container < big container.

None of the current planning variable state in any of the planning entities should be used to compare planning values. During construction heuristics, those variables are likely to be null anyway. For example, none of the row variables of any Queen may be used to determine the strength of a Row.

Some use cases, such as TSP and Vehicle Routing, require chaining. This means the planning entities point to each other and form a chain. By modeling the problem as a set of chains (instead of a set of trees/loops), the search space is heavily reduced.

A planning variable that is chained either:

Here are some example of valid and invalid chains:

Every initialized planning entity is part of an open-ended chain that begins from an anchor. A valid model means that:

The optimization algorithms and build-in Move's do chain correction to guarantee that the model stays valid:

For example, in TSP the anchor is a Domicile (in vehicle routing it is Vehicle):

public class Domicile ... implements Standstill {


    ...
    public City getCity() {...}
}

The anchor (which is a problem fact) and the planning entity implement a common interface, for example TSP's Standstill:

public interface Standstill {


    City getCity();
}

That interface is the return type of the planning variable. Furthermore, the planning variable is chained. For example TSP's Visit (in vehicle routing it is Customer):

@PlanningEntity

public class Visit ... implements Standstill {
    ...
    public City getCity() {...}
    @PlanningVariable(chained = true, valueRangeProviderRefs = {"domicileRange", "visitRange"})
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }
    public void setPreviousStandstill(Standstill previousStandstill) {
        this.previousStandstill = previousStandstill;
    }
}

Notice how 2 value range providers are usually combined:

A shadow variable is a variables who's correct value can be deduced from the state of the genuine planning variables. Even though such a variable violates the principle of normalization by definition, in some use cases it can be very practical to use a shadow variable, especially to express the constraints more naturally. For example in vehicle routing with time windows: the arrival time at a customer for a vehicle can be calculated based on the previously visited customers of that vehicle (and the known travel times between 2 locations).

As the customers for a vehicle change, the arrival time is automatically adjusted. For more information, see the vehicle routing domain model.

To use custom VariableListener, implement the interface and annotate it on the genuine planning variable(s) that trigger changes in the shadow variable(s):

    @PlanningVariable(..., variableListenerClasses = {VehicleUpdatingVariableListener.class, ArrivalTimeUpdatingVariableListener.class})

    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

For example, the VehicleUpdatingVariableListener assures that every Customer in a chain has the same Vehicle, namely the chain's anchor.

public class VehicleUpdatingVariableListener implements VariableListener<Customer> {


    public void afterEntityAdded(ScoreDirector scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }
    public void afterVariableChanged(ScoreDirector scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }
    ...
    protected void updateVehicle(ScoreDirector scoreDirector, Customer sourceCustomer) {
        Standstill previousStandstill = sourceCustomer.getPreviousStandstill();
        Vehicle vehicle = previousStandstill == null ? null : previousStandstill.getVehicle();
        Customer shadowCustomer = sourceCustomer;
        while (shadowCustomer != null && shadowCustomer.getVehicle() != vehicle) {
            scoreDirector.beforeVariableChanged(shadowCustomer, "vehicle");
            shadowCustomer.setVehicle(vehicle);
            scoreDirector.afterVariableChanged(shadowCustomer, "vehicle");
            shadowCustomer = shadowCustomer.getNextCustomer();
        }
    }
}

Any class that has a shadow variable, is a planning entity class, even it has no genuine planning variables.

Warning

A VariableListener can only change shadow variables. It must never change a genuine planning variable or a problem fact.

Warning

Any change of a shadow variable must be told to the ScoreDirector.

From a score calculation perspective, a shadow variable is like any other planning variable. From an optimization perspective, Planner effectively only optimizes the genuine variables (and mostly ignores the shadow variables): it just assures that when a genuine variable changes, it changes any dependent shadow variables accordingly.

A cached problem fact is a problem fact that doesn't exist in the real domain model, but is calculated before the Solver really starts solving. The method getProblemFacts() has the chance to enrich the domain model with such cached problem facts, which can lead to simpler and faster score constraints.

For example in examination, a cached problem fact TopicConflict is created for every 2 Topic's which share at least 1 Student.

    public Collection<? extends Object> getProblemFacts() {

        List<Object> facts = new ArrayList<Object>();
        // ...
        facts.addAll(calculateTopicConflictList());
        // ...
        return facts;
    }
    private List<TopicConflict> calculateTopicConflictList() {
        List<TopicConflict> topicConflictList = new ArrayList<TopicConflict>();
        for (Topic leftTopic : topicList) {
            for (Topic rightTopic : topicList) {
                if (leftTopic.getId() < rightTopic.getId()) {
                    int studentSize = 0;
                    for (Student student : leftTopic.getStudentList()) {
                        if (rightTopic.getStudentList().contains(student)) {
                            studentSize++;
                        }
                    }
                    if (studentSize > 0) {
                        topicConflictList.add(new TopicConflict(leftTopic, rightTopic, studentSize));
                    }
                }
            }
        }
        return topicConflictList;
    }

Any score constraint that needs to check if no 2 exams have a topic which share a student are being scheduled close together (depending on the constraint: at the same time, in a row or in the same day), can simply use the TopicConflict instance as a problem fact, instead of having to combine every 2 Student instances.

Most (if not all) optimization algorithms clone the solution each time they encounter a new best solution (so they can recall it later) or to work with multiple solutions in parallel.

A planning clone of a Solution must fulfill these requirements:

Implementing a planning clone method is hard, therefore you don't need to implement it.

If your Solution implements PlanningCloneable, Planner will automatically choose to clone it by calling the method planningClone().

public interface PlanningCloneable<T> {


    T planningClone();
}

For example: If NQueens implements PlanningCloneable, it would only deep clone all Queen instances. When the original solution is changed during planning, by changing a Queen, the clone stays the same.

public class NQueens implements Solution<...>, PlanningCloneable<NQueens> {

    ...
    /**
     * Clone will only deep copy the {@link #queenList}.
     */
    public NQueens planningClone() {
        NQueens clone = new NQueens();
        clone.id = id;
        clone.= n;
        clone.columnList = columnList;
        clone.rowList = rowList;
        List<Queen> clonedQueenList = new ArrayList<Queen>(queenList.size());
        for (Queen queen : queenList) {
            clonedQueenList.add(queen.planningClone());
        }
        clone.queenList = clonedQueenList;
        clone.score = score;
        return clone;
    }
}

The planningClone() method should only deep clone the planning entities. Notice that the problem facts, such as Column and Row are normally not cloned: even their List instances are not cloned. If you were to clone the problem facts too, then you'd have to make sure that the new planning entity clones also refer to the new problem facts clones used by the solution. For example, if you would clone all Row instances, then each Queen clone and the NQueens clone itself should refer to those new Row clones.

Warning

Cloning an entity with a chained variable is devious: a variable of an entity A might point to another entity B. If A is cloned, then it's variable must point to the clone of B, not the original B.

Build a Solution instance to represent your planning problem, so you can set it on the Solver as the planning problem to solve. For example in n queens, an NQueens instance is created with the required Column and Row instances and every Queen set to a different column and every row set to null.

    private NQueens createNQueens(int n) {

        NQueens nQueens = new NQueens();
        nQueens.setId(0L);
        nQueens.setN(n);
        nQueens.setColumnList(createColumnList(nQueens));
        nQueens.setRowList(createRowList(nQueens));
        nQueens.setQueenList(createQueenList(nQueens));
        return nQueens;
    }
    private List<Queen> createQueenList(NQueens nQueens) {
        int n = nQueens.getN();
        List<Queen> queenList = new ArrayList<Queen>(n);
        long id = 0;
        for (Column column : nQueens.getColumnList()) {
            Queen queen = new Queen();
            queen.setId(id);
            id++;
            queen.setColumn(column);
            // Notice that we leave the PlanningVariable properties on null
            queenList.add(queen);
        }
        return queenList;
    }

Usually, most of this data comes from your data layer, and your Solution implementation just aggregates that data and creates the uninitialized planning entity instances to plan:

        private void createLectureList(CourseSchedule schedule) {

            List<Course> courseList = schedule.getCourseList();
            List<Lecture> lectureList = new ArrayList<Lecture>(courseList.size());
            for (Course course : courseList) {
                for (int i = 0; i < course.getLectureSize(); i++) {
                    Lecture lecture = new Lecture();
                    lecture.setCourse(course);
                    lecture.setLectureIndexInCourse(i);
                    // Notice that we leave the PlanningVariable properties (period and room) on null
                    lectureList.add(lecture);
                }
            }
            schedule.setLectureList(lectureList);
        }

The environment mode allows you to detect common bugs in your implementation. It does not affect the logging level.

You can set the environment mode in the solver configuration XML file:


<solver>
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
</solver>

A solver has a single Random instance. Some solver configurations use the Random instance a lot more than others. For example simulated annealing depends highly on random numbers, while tabu search only depends on it to deal with score ties. The environment mode influences the seed of that Random instance.

There are 4 environment modes:

The best way to illuminate the black box that is a Solver, is to play with the logging level:

For example, set it to debug logging, to see when the phases end and how fast steps are taken:

INFO  Solving started: time spent (3), best score (uninitialized/0), random (JDK with seed 0).
DEBUG     CH step (0), time spent (5), score (0), selected move count (1), picked move (col2@null => row0).
DEBUG     CH step (1), time spent (7), score (0), selected move count (3), picked move (col1@null => row2).
DEBUG     CH step (2), time spent (10), score (0), selected move count (4), picked move (col3@null => row3).
DEBUG     CH step (3), time spent (12), score (-1), selected move count (4), picked move (col0@null => row1).
INFO  Construction Heuristic phase (0) ended: step total (4), time spent (12), best score (-1).
DEBUG     LS step (0), time spent (19), score (-1),     best score (-1), accepted/selected move count (12/12), picked move (col1@row2 => row3).
DEBUG     LS step (1), time spent (24), score (0), new best score (0), accepted/selected move count (9/12), picked move (col3@row3 => row2).
INFO  Local Search phase (1) ended: step total (2), time spent (24), best score (0).
INFO  Solving ended: time spent (24), best score (0), average calculate count per second (1625).

All time spent values are in milliseconds.

Everything is logged to SLF4J, which is a simple logging facade which delegates every log message to Logback, Apache Commons Logging, Log4j or java.util.logging. Add a dependency to the logging adaptor for your logging framework of choice.

If you're not using any logging framework yet, use Logback by adding this Maven dependency (there is no need to add an extra bridge dependency):


    <dependency>
      <groupId>ch.qos.logback</groupId>
      <artifactId>logback-classic</artifactId>
      <version>1.x</version>
    </dependency>

Configure the logging level on the package org.optaplanner in your logback.xml file:


<configuration>

  <logger name="org.optaplanner" level="debug"/>

  ...

<configuration>

If instead, you're still using Log4J (and you don't want to switch to its faster successor, Logback), add the bridge dependency:


    <dependency>
      <groupId>org.slf4j</groupId>
      <artifactId>slf4j-log4j12</artifactId>
      <version>1.x</version>
    </dependency>

And configure the logging level on the package org.optaplanner in your log4j.xml file:


<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">

  <category name="org.optaplanner">
    <priority value="debug" />
  </category>

  ...

</log4j:configuration>