Modeling planning problems

1. Is this class a problem fact or planning entity?

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

  • An unrelated class: not used by any of the score constraints. From a planning standpoint, this data is obsolete.

  • A problem fact class: used by the score constraints, but does NOT change during planning (as long as the problem stays the same). For example: Bed, Room, Shift, Employee, Topic, Period, …​ All the properties of a problem fact class are problem properties.

  • A planning entity class: used by the score constraints and changes during planning. For example: BedDesignation, ShiftAssignment, Exam, …​ The properties that change during planning are planning variables. The other properties are problem properties.

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 one planning entity class. Most use cases also have only one planning variable per planning entity class.

In real-time planning, even though the problem itself changes, problem facts do not really change during planning, instead they change between planning (because the Solver temporarily stops to apply the problem fact changes).

To create a good domain model, read the domain modeling guide.

In Timefold Solver, all problem facts and planning entities are plain old JavaBeans (POJOs). Load them from a database, an XML file, a data repository, a REST service, a noSQL cloud, …​ (see integration): it doesn’t matter.

2. Problem fact

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

public class Column {

    private int index;

    // ... getters
}
public class Row {

    private int index;

    // ... getters
}

A problem fact can reference other problem facts of course:

public class Course {

    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 Timefold Solver specific code. For example, you can reuse your domain classes, which might have JPA annotations.

Generally, better designed domain classes lead to simpler and more efficient score constraints. Therefore, when dealing with a messy (denormalized) legacy system, it can sometimes be worthwhile to convert the messy domain model into a Timefold Solver specific model first. For example: if your domain model has two Teacher instances for the same teacher that teaches at two different departments, it is harder to write a correct score constraint that constrains a teacher’s spare time on the original model than on an adjusted model.

Alternatively, you can sometimes also introduce a cached problem fact to enrich the domain model for planning only.

3. Planning entity

3.1. Planning entity annotation

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 is usually only one 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 one or more planning variables (which can be genuine or shadows). It should also have one 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 one course has multiple lectures). Each Lecture needs to be scheduled into a Period and a Room so it has two planning variables (period and room). For example: the course Mathematics has eight 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 needs to declare each planning entity class:

<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
  ...
  <entityClass>ai.timefold.solver.examples.nqueens.domain.Queen</entityClass>
  ...
</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.

Do not create unnecessary planning entity classes. This leads to difficult Move implementations and slower score calculation.

For example, do not create a planning entity class to hold the total free time of a teacher, which needs to be kept up to date as the Lecture planning entities change. Instead, calculate the free time in the score constraints (or as a shadow variable) and put the result per teacher into a logically inserted score object.

If historic data needs to be considered too, then create problem fact to hold the total of the historic assignments up to, but not including, the planning window (so that it does not change when a planning entity changes) and let the score constraints take it into account.

Planning entity hashCode() implementations must remain constant. Therefore entity hashCode() must not depend on any planning variables. Pay special attention when using data structures with auto-generated hashCode() as entities, such as Kotlin data classes or Lombok’s @EqualsAndHashCode.

Planning entity implementations must not be of Java’s enum or record types. Those are immutable by design and therefore cannot change during planning, whereas planning entities will.

3.2. Planning entity difficulty

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.

Do not try to use planning entity difficulty to implement a business constraint. It will not affect the score function: if we have infinite solving time, the returned solution will be the same.

To attain a schedule in which certain entities are scheduled earlier in the schedule, add a score constraint to change the score function so it prefers such solutions. Only consider adding planning entity difficulty too if it can make the solver more efficient.

To allow the heuristics to take advantage of that domain specific information, 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 that 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.

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

Although most algorithms start with the more difficult entities first, they just reverse the ordering.

None of the current planning variable states should be used to compare planning entity difficulty. During Construction Heuristics, those variables are likely to be null anyway. For example, a Queen's row variable should not be used.

4. Planning variable (genuine)

4.1. Planning variable annotation

A planning variable is a JavaBean property (so a getter and setter) on a planning entity. It points to a planning value, which changes during planning. For example, a Queen's row property is a genuine planning variable. Note that even though a Queen's row property changes to another Row during planning, no Row instance itself is changed. Normally planning variables are genuine, but advanced cases can also have shadows.

A genuine planning variable getter needs to be annotated with the @PlanningVariable annotation, optionally with a non-empty valueRangeProviderRefs property.

@PlanningEntity
public class Queen {
    ...

    private Row row;

    @PlanningVariable
    public Row getRow() {
        return row;
    }

    public void setRow(Row row) {
        this.row = row;
    }

}

The optional valueRangeProviderRefs property defines what are the possible planning values for this planning variable. It references one or more @ValueRangeProvider id's. If none are provided, Timefold Solver will attempt to auto-detect matching @ValueRangeProviders.

A @PlanningVariable annotation needs to be on a member in a class with a @PlanningEntity annotation. It is ignored on parent classes or subclasses without that annotation.

Annotating the field instead of the property works too:

@PlanningEntity
public class Queen {
    ...

    @PlanningVariable
    private Row row;

}

For more advanced planning variables used to model precedence relationships, see planning list variable and chained planning variable.

4.2. Nullable planning variable

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 counterproductive. 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;
    }

Constraint Streams filter out planning entities with a null planning variable by default. Use forEachIncludingNullVars() to avoid such unwanted behaviour.

Timefold Solver will automatically add the value null to the value range. There is no need to add null in a collection provided by a ValueRangeProvider.

Using a nullable planning variable implies that your score calculation is responsible for punishing (or even rewarding) variables with a null value.

Currently chained planning variables are not compatible with nullable.

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 filter the entity selector of the placer in the construction heuristic.

<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
  ...
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="entitySelector1">
        <filterClass>...</filterClass>
      </entitySelector>
    </queuedEntityPlacer>
    ...
    <changeMoveSelector>
      <entitySelector mimicSelectorRef="entitySelector1" />
    </changeMoveSelector>
    ...
  </constructionHeuristic>
 ...
</solver>

4.3. When is a planning variable considered initialized?

A planning variable is considered initialized if its value is not null or if the variable is nullable. So a nullable variable is always considered initialized.

A planning entity is initialized if all of its planning variables are initialized.

A solution is initialized if all of its planning entities are initialized.

5. Planning variable (shadow)

A shadow variable is a planning variable whose 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 two locations).

planningVariableListener

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

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

Any class that has at least one shadow variable, is a planning entity class (even if it has no genuine planning variables). That class must be defined in the solver configuration and have a @PlanningEntity annotation.

A genuine planning entity class has at least one genuine planning variable, but can have shadow variables too. A shadow planning entity class has no genuine planning variables and at least one shadow planning variable.

There are several built-in shadow variables:

5.1. Bi-directional variable (inverse relation shadow variable)

Two variables are bi-directional if their instances always point to each other (unless one side points to null and the other side does not exist). So if A references B, then B references A.

bidirectionalVariable

For a non-chained planning variable, the bi-directional relationship must be a many-to-one relationship. To map a bi-directional relationship between two planning variables, annotate the source side (which is the genuine side) as a normal planning variable:

@PlanningEntity
public class CloudProcess {

    @PlanningVariable(...)
    public CloudComputer getComputer() {
        return computer;
    }
    public void setComputer(CloudComputer computer) {...}

}

And then annotate the other side (which is the shadow side) with a @InverseRelationShadowVariable annotation on a Collection (usually a Set or List) property:

@PlanningEntity
public class CloudComputer {

    @InverseRelationShadowVariable(sourceVariableName = "computer")
    public List<CloudProcess> getProcessList() {
        return processList;
    }

}

Register this class as a planning entity, otherwise Timefold Solver won’t detect it and the shadow variable won’t update. The sourceVariableName property is the name of the genuine planning variable on the return type of the getter (so the name of the genuine planning variable on the other side).

The shadow property, which is Collection (usually List, Set or SortedSet), can never be null. If no genuine variable references that shadow entity, then it is an empty collection. Furthermore it must be a mutable Collection because once Timefold Solver starts initializing or changing genuine planning variables, it will add and remove elements to the Collections of those shadow variables accordingly.

For a chained planning variable, the bi-directional relationship is always a one-to-one relationship. In that case, the genuine side looks like this:

@PlanningEntity
public class Customer ... {

    @PlanningVariable(graphType = PlanningVariableGraphType.CHAINED, ...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }
    public void setPreviousStandstill(Standstill previousStandstill) {...}

}

And the shadow side looks like this:

@PlanningEntity
public class Standstill {

    @InverseRelationShadowVariable(sourceVariableName = "previousStandstill")
    public Customer getNextCustomer() {
         return nextCustomer;
    }
    public void setNextCustomer(Customer nextCustomer) {...}

}

Register this class as a planning entity, otherwise Timefold Solver won’t detect it and the shadow variable won’t update.

The input planning problem of a Solver must not violate bi-directional relationships. If A points to B, then B must point to A. Timefold Solver will not violate that principle during planning, but the input must not violate it either.

5.2. Anchor shadow variable

An anchor shadow variable is the anchor of a chained variable.

Annotate the anchor property as a @AnchorShadowVariable annotation:

@PlanningEntity
public class Customer {

    @AnchorShadowVariable(sourceVariableName = "previousStandstill")
    public Vehicle getVehicle() {...}
    public void setVehicle(Vehicle vehicle) {...}

}

This class should already be registered as a planning entity. The sourceVariableName property is the name of the chained variable on the same entity class.

5.3. List variable shadow variables

When the planning entity uses a list variable, its elements can use a number of built-in shadow variables.

5.3.1. Inverse relation shadow variable

Use the same @InverseRelationShadowVariable annotation as with basic or chained planning variable to establish bi-directional relationship between the entity and the elements assigned to its list variable. The type of the inverse shadow variable is the planning entity itself because there is a one-to-many relationship between the entity and the element classes.

The planning entity side has a genuine list variable:

@PlanningEntity
public class Vehicle {

    @PlanningListVariable
    public List<Customer> getCustomers() {
        return customers;
    }

    public void setCustomers(List<Customer> customers) {...}
}

On the element side:

  • Annotate the class with @PlanningEntity to make it a shadow planning entity.

  • Register this class as a planning entity, otherwise Timefold Solver won’t detect it and the shadow variable won’t update.

  • Create a property with the genuine planning entity type.

  • Annotate it with @InverseRelationShadowVariable and set sourceVariableName to the name of the genuine planning list variable.

@PlanningEntity
public class Customer {

    @InverseRelationShadowVariable(sourceVariableName = "customers")
    public Vehicle getVehicle() {
        return vehicle;
    }

    public void setVehicle(Vehicle vehicle) {...}
}

5.3.2. Previous and next element shadow variable

Use @PreviousElementShadowVariable or @NextElementShadowVariable to get a reference to an element that is assigned to the same entity’s list variable one index lower (previous element) or one index higher (next element).

The previous and next element shadow variables may be null even in a fully initialized solution. The first element’s previous shadow variable is null and the last element’s next shadow variable is null.

The planning entity side has a genuine list variable:

@PlanningEntity
public class Vehicle {

    @PlanningListVariable
    public List<Customer> getCustomers() {
        return customers;
    }

    public void setCustomers(List<Customer> customers) {...}
}

On the element side:

@PlanningEntity
public class Customer {

    @PreviousElementShadowVariable(sourceVariableName = "customers")
    public Customer getPreviousCustomer() {
        return previousCustomer;
    }

    public void setPreviousCustomer(Customer previousCustomer) {...}

    @NextElementShadowVariable(sourceVariableName = "customers")
    public Customer getNextCustomer() {
        return nextCustomer;
    }

    public void setNextCustomer(Customer nextCustomer) {...}

5.4. Custom VariableListener

To update a shadow variable, Timefold Solver uses a VariableListener. To define a custom shadow variable, write a custom VariableListener: implement the interface and annotate it on the shadow variable that needs to change.

    @PlanningVariable(...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    @ShadowVariable(
            variableListenerClass = VehicleUpdatingVariableListener.class,
            sourceVariableName = "previousStandstill")
    public Vehicle getVehicle() {
        return vehicle;
    }

Register this class as a planning entity if it isn’t already. Otherwise Timefold Solver won’t detect it and the shadow variable won’t update.

The sourceVariableName is the (genuine or shadow) variable that triggers changes to the annotated shadow variable. If the source variable is declared on a different class than the annotated shadow variable’s class, also specify the sourceEntityClass and make sure the shadow variable’s class is registered as a planning entity.

Implement the VariableListener interface. 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<VehicleRoutingSolution, Customer> {

    public void afterEntityAdded(ScoreDirector<VehicleRoutingSolution> scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }

    public void afterVariableChanged(ScoreDirector<VehicleRoutingSolution> scoreDirector, Customer customer) {
        updateVehicle(scoreDirector, customer);
    }

    ...

    protected void updateVehicle(ScoreDirector<VehicleRoutingSolution> 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();
        }
    }

}

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

Any change of a shadow variable must be told to the ScoreDirector with before*() and after*() methods.

5.4.1. Multiple source variables

If your custom variable listener needs multiple source variables to compute the shadow variable, annotate the shadow variable with multiple @ShadowVariable annotations, one per each source variable.

    @PlanningVariable(...)
    public ExecutionMode getExecutionMode() {
        return executionMode;
    }

    @PlanningVariable(...)
    public Integer getDelay() {
        return delay;
    }

    @ShadowVariable(
            variableListenerClass = PredecessorsDoneDateUpdatingVariableListener.class,
            sourceVariableName = "executionMode")
    @ShadowVariable(
            variableListenerClass = PredecessorsDoneDateUpdatingVariableListener.class,
            sourceVariableName = "delay")
    public Integer getPredecessorsDoneDate() {
        return predecessorsDoneDate;
    }

5.4.2. Piggyback shadow variable

If one VariableListener changes two or more shadow variables (because having two separate VariableListeners would be inefficient), then annotate only the first shadow variable with @ShadowVariable and specify the variableListenerClass there. Use @PiggybackShadowVariable on each shadow variable updated by that variable listener and reference the first shadow variable:

    @PlanningVariable(...)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    @ShadowVariable(
            variableListenerClass = TransportTimeAndCapacityUpdatingVariableListener.class,
            sourceVariableName = "previousStandstill")
    public Integer getTransportTime() {
        return transportTime;
    }

    @PiggybackShadowVariable(shadowVariableName = "transportTime")
    public Integer getCapacity() {
        return capacity;
    }

5.4.3. Shadow variable cloning

A shadow variable’s value (just like a genuine variable’s value) isn’t planning cloned by the default solution cloner, unless it can easily prove that it must be planning cloned (for example the property type is a planning entity class). Specifically shadow variables of type List, Set, Collection or Map usually need to be planning cloned to avoid corrupting the best solution when the working solution changes. To planning clone a shadow variable, add @DeepPlanningClone annotation:

    @DeepPlanningClone
    @ShadowVariable(...)
    private Map<LocalDateTime, Integer> usedManHoursPerDayMap;

5.5. VariableListener triggering order

All shadow variables are triggered by a VariableListener, regardless if it’s a built-in or a custom shadow variable. The genuine and shadow variables form a graph, that determines the order in which the afterEntityAdded(), afterVariableChanged() and afterEntityRemoved() methods are called:

shadowVariableOrder

In the example above, D could have also been ordered after E (or F) because there is no direct or indirect dependency between D and E (or F).

Timefold Solver guarantees that:

  • The first VariableListener's after*() methods trigger after the last genuine variable has changed. Therefore the genuine variables (A and B in the example above) are guaranteed to be in a consistent state across all its instances (with values A1, A2 and B1 in the example above) because the entire Move has been applied.

  • The second VariableListener's after*() methods trigger after the last first shadow variable has changed. Therefore the first shadow variable (C in the example above) are guaranteed to be in a consistent state across all its instances (with values C1 and C2 in the example above). And of course the genuine variables too.

  • And so forth.

Timefold Solver does not guarantee the order in which the after*() methods are called for the sameVariableListener with different parameters (such as A1 and A2 in the example above), although they are likely to be in the order in which they were affected.

By default, Timefold Solver does not guarantee that the events are unique. For example, if a shadow variable on an entity is changed twice in the same move (for example by two different genuine variables), then that will cause the same event twice on the VariableListeners that are listening to that original shadow variable. To avoid dealing with that complexity, overwrite the method requiresUniqueEntityEvents() to receive unique events at the cost of a small performance penalty:

public class StartTimeUpdatingVariableListener implements VariableListener<TaskAssigningSolution, Task> {

    @Override
    public boolean requiresUniqueEntityEvents() {
        return true;
    }

    ...
}

6. Planning value and planning value range

6.1. Planning value

A planning value is a possible value for a genuine planning variable. Usually, a planning value is a problem fact, but it can also be any object, for example an Integer. It can even be another planning entity or even an interface implemented by both a planning entity and a problem fact.

Primitive types (such as int) are not allowed.

A planning value range is the set of possible planning values for a planning variable. This set can be a countable (for example row 1, 2, 3 or 4) or uncountable (for example any double between 0.0 and 1.0).

6.2. Planning value range provider

6.2.1. Overview

The value range of a planning variable is defined with the @ValueRangeProvider annotation. A @ValueRangeProvider may carry a property id, which is referenced by the @PlanningVariable's property valueRangeProviderRefs.

This annotation can be located on two types of methods:

  • On the Solution: All planning entities share the same value range.

  • On the planning entity: The value range differs per planning entity. This is less common.

A @ValueRangeProvider annotation needs to be on a member in a class with a @PlanningSolution or a @PlanningEntity annotation. It is ignored on parent classes or subclasses without those annotations.

The return type of that method can be three types:

  • Collection: The value range is defined by a Collection (usually a List) of its possible values.

  • Array: The value range is defined by an array of its possible values.

  • ValueRange: The value range is defined by its bounds. This is less common.

6.2.2. ValueRangeProvider on the solution

All instances of the same planning entity class share the same set of possible planning values for that planning variable. This is the most common way to configure a value range.

The @PlanningSolution implementation has method that returns a Collection (or a ValueRange). Any value from that Collection is a possible planning value for this planning variable.

    @PlanningVariable
    public Row getRow() {
        return row;
    }
@PlanningSolution
public class NQueens {
    ...

    @ValueRangeProvider
    public List<Row> getRowList() {
        return rowList;
    }

}

That Collection (or ValueRange) must not contain the value null, not even for a nullable planning variable.

Annotating the field instead of the property works too:

@PlanningSolution
public class NQueens {
    ...

    @ValueRangeProvider
    private List<Row> rowList;

}

6.2.3. ValueRangeProvider on the Planning Entity

Each planning entity has its own value range (a set of possible planning values) for the 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
    public Room getRoom() {
        return room;
    }

    @ValueRangeProvider
    public List<Room> getPossibleRoomList() {
        return getCourse().getTeacher().getDepartment().getRoomList();
    }

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

By limiting the value range specifically of one planning entity, you are effectively creating a built-in hard constraint. This can have the benefit of severely lowering the number of possible solutions; however, it can also take away the freedom of the optimization algorithms to temporarily break that constraint in order to escape from a local optimum.

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

Every entity has its own List instance, unless multiple entities have the same value range. For example, if teacher A and B belong to the same department, they use the same List<Room> instance. Furthermore, each List contains a subset of the same set of planning value instances. For example, if department A and B can both use room X, then their List<Room> instances contain the same Room instance.

A ValueRangeProvider on the planning entity consumes more memory than ValueRangeProvider on the Solution and disables certain automatic performance optimizations.

A ValueRangeProvider on the planning entity is not currently compatible with a chained variable.

A ValueRangeProvider on the planning entity is not compatible with a list variable.

6.2.4. Referencing ValueRangeProviders

There are two ways how to match a planning variable to a value range provider. The simplest way is to have value range provider auto-detected. Another way is to explicitly reference the value range provider.

Anonymous ValueRangeProviders

We already described the first approach. By not providing any valueRangeProviderRefs on the @PlanningVariable annotation, Timefold Solver will go over every @ValueRangeProvider-annotated method or field which does not have an id property set, and will match planning variables with value ranges where their types match.

In the following example, the planning variable car will be matched to the value range returned by getCompanyCarList(), as they both use the Car type. It will not match getPersonalCarList(), because that value range provider is not anonymous; it specifies an id.

    @PlanningVariable
    public Car getCar() {
        return car;
    }

    @ValueRangeProvider
    public List<Car> getCompanyCarList() {
        return companyCarList;
    }

    @ValueRangeProvider(id = "personalCarRange")
    public List<Car> getPersonalCarList() {
        return personalCarList;
    }

Automatic matching also accounts for polymorphism. In the following example, the planning variable car will be matched to getCompanyCarList() and getPersonalCarList(), as both CompanyCar and PersonalCar are Cars. It will not match getAirplanes(), as an Airplane is not a Car.

    @PlanningVariable
    public Car getCar() {
        return car;
    }

    @ValueRangeProvider
    public List<CompanyCar> getCompanyCarList() {
        return companyCarList;
    }

    @ValueRangeProvider
    public List<PersonalCar> getPersonalCarList() {
        return personalCarList;
    }

    @ValueRangeProvider
    public List<Airplane> getAirplanes() {
        return airplaneList;
    }
Explicitly referenced ValueRangeProviders

In more complicated cases where auto-detection is not sufficient or where clarity is preferred over simplicity, value range providers can also be referenced explicitly.

In the following example, the car planning variable will only be matched to value range provided by methods getCompanyCarList().

    @PlanningVariable(valueRangeProviderRefs = {"companyCarRange"})
    public Car getCar() {
        return car;
    }

    @ValueRangeProvider(id = "companyCarRange")
    public List<CompanyCar> getCompanyCarList() {
        return companyCarList;
    }

    @ValueRangeProvider(id = "personalCarRange")
    public List<PersonalCar> getPersonalCarList() {
        return personalCarList;
    }

Explicitly referenced value range providers can also be combined, for example:

    @PlanningVariable(valueRangeProviderRefs = { "companyCarRange", "personalCarRange" })
    public Car getCar() {
        return car;
    }

    @ValueRangeProvider(id = "companyCarRange")
    public List<CompanyCar> getCompanyCarList() {
        return companyCarList;
    }

    @ValueRangeProvider(id = "personalCarRange")
    public List<PersonalCar> getPersonalCarList() {
        return personalCarList;
    }

6.2.5. ValueRangeFactory

Instead of a Collection, you can also return a ValueRange or CountableValueRange, built by the ValueRangeFactory:

    @ValueRangeProvider
    public CountableValueRange<Integer> getDelayRange() {
        return ValueRangeFactory.createIntValueRange(0, 5000);
    }

A ValueRange uses far less memory, because it only holds the bounds. In the example above, a Collection would need to hold all 5000 ints, instead of just the two bounds.

Furthermore, an incrementUnit can be specified, for example if you have to buy stocks in units of 200 pieces:

    @ValueRangeProvider
    public CountableValueRange<Integer> getStockAmountRange() {
         // Range: 0, 200, 400, 600, ..., 9999600, 9999800, 10000000
        return ValueRangeFactory.createIntValueRange(0, 10000000, 200);
    }

Return CountableValueRange instead of ValueRange whenever possible (so Timefold Solver knows that it’s countable).

The ValueRangeFactory has creation methods for several value class types:

  • boolean: A boolean range.

  • int: A 32bit integer range.

  • long: A 64bit integer range.

  • double: A 64bit floating point range which only supports random selection (because it does not implement CountableValueRange).

  • BigInteger: An arbitrary-precision integer range.

  • BigDecimal: A decimal point range. By default, the increment unit is the lowest non-zero value in the scale of the bounds.

  • Temporal (such as LocalDate, LocalDateTime, …​): A time range.

6.3. Planning value strength

Some optimization algorithms work a bit 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. Usually, the efficiency gain of planning value strength is far less than that of planning entity difficulty.

Do not try to use planning value strength to implement a business constraint. It will not affect the score function: if we have infinite solving time, the returned solution will be the same.

To affect the score function, add a score constraint. Only consider adding planning value strength too if it can make the solver more efficient.

To allow the heuristics to take advantage of that domain specific information, set a strengthComparatorClass to the @PlanningVariable annotation:

    @PlanningVariable(..., strengthComparatorClass = CloudComputerStrengthComparator.class)
    public CloudComputer getComputer() {
        return computer;
    }
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();
    }

}

If you have multiple planning value classes in the same value range, the strengthComparatorClass needs to implement a Comparator of a common superclass (for example Comparator<Object>) and be able to handle comparing instances of those different classes.

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() {
        return row;
    }

See sorted selection for more information.

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. For example, none of the row variables of any Queen may be used to determine the strength of a Row.

7. Planning list variable (VRP, Task assigning, …​)

Use the planning list variable to model problems where the goal is to distribute a number of workload elements among limited resources in a specific order. This includes, for example, vehicle routing, traveling salesman, task assigning, and similar problems, that have previously been modeled using the chained planning variable.

The planning list variable is a successor to the chained planning variable and provides a more intuitive way to express the problem domain with Java classes.

Planning list variable does not yet support all the advanced planning features that work with the chained planning variable. Use a chained planning variable instead of a planning list variable, if you need any of the following planning techniques:

For example, the vehicle routing problem can be modeled as follows:

vehicleRoutingClassDiagram

This model is closer to the reality than the chained model. Each vehicle has a list of customers to go to in the order given by the list. And indeed, the object model matches the natural language description of the problem:

@PlanningEntity
class Vehicle {

    int capacity;
    Depot depot;

    @PlanningListVariable
    List<Customer> customers = new ArrayList<>();
}

Planning list variable can be used if the domain meets the following criteria:

  1. There is a one-to-many relationship between the planning entity and the planning value.

  2. The order in which planning values are assigned to an entity’s list variable is significant.

  3. Each planning value is assigned to exactly one planning entity. No planning value may appear in multiple entities.

8. Chained planning variable (TSP, VRP, …​)

Chained planning variable is one way to implement the Chained Through Time pattern. This pattern is used for some use cases, such as TSP and vehicle routing. Use the chained planning variable to implement this pattern if you plan to use some of the advanced planning features, that are not yet supported by the planning list variable.

Chained planning variable allows the planning entities to 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:

  • Directly points to a problem fact (or planning entity), which is called an anchor.

  • Points to another planning entity with the same planning variable, which recursively points to an anchor.

Here are some examples of valid and invalid chains:

chainPrinciples

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

  • A chain is never a loop. The tail is always open.

  • Every chain always has exactly one anchor. The anchor is never an instance of the planning entity class that contains the chained planning variable.

  • A chain is never a tree, it is always a line. Every anchor or planning entity has at most one trailing planning entity.

  • Every initialized planning entity is part of a chain.

  • An anchor with no planning entities pointing to it, is also considered a chain.

A planning problem instance given to the Solver must be valid.

If your constraints dictate a closed chain, model it as an open-ended chain (which is easier to persist in a database) and implement a score constraint for the last entity back to the anchor.

The optimization algorithms and built-in Moves do chain correction to guarantee that the model stays valid:

chainCorrection

A custom Move implementation must leave the model in a valid state.

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:

@PlanningEntity
public class Visit ... implements Standstill {
    ...

    public City getCity() {...}

    @PlanningVariable(graphType = PlanningVariableGraphType.CHAINED)
    public Standstill getPreviousStandstill() {
        return previousStandstill;
    }

    public void setPreviousStandstill(Standstill previousStandstill) {
        this.previousStandstill = previousStandstill;
    }

}

Notice how two value range providers are usually combined:

  • The value range provider that holds the anchors, for example domicileList.

  • The value range provider that holds the initialized planning entities, for example visitList.

9. Planning problem and planning solution

9.1. Planning problem instance

A dataset for a planning problem needs to be wrapped in a class for the Solver to solve. That solution class represents both the planning problem and (if solved) a solution. It is annotated with a @PlanningSolution annotation. For example in n queens, the solution class is the NQueens class, which contains a Column list, a Row list, and a Queen list.

A planning problem is actually an unsolved planning solution or - stated differently - an uninitialized solution. For example in n queens, that NQueens class has the @PlanningSolution annotation, yet every Queen in an unsolved NQueens class is not yet assigned to a Row (their row property is null). That’s not a feasible solution. It’s not even a possible solution. It’s an uninitialized solution.

9.2. Solution class

A solution class holds all problem facts, planning entities and a score. It is annotated with a @PlanningSolution annotation. For example, an NQueens instance holds a list of all columns, all rows and all Queen instances:

@PlanningSolution
public class NQueens {

    // Problem facts
    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    // Planning entities
    private List<Queen> queenList;

    private SimpleScore score;

    ...
}

The solver configuration needs to declare the planning solution class:

<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
  ...
  <solutionClass>ai.timefold.solver.examples.nqueens.domain.NQueens</solutionClass>
  ...
</solver>

Solution class must not be of Java’s enum or record types. Those are immutable by design and therefore cannot change during planning, whereas a planning solution will.

9.3. Planning entities of a solution (@PlanningEntityCollectionProperty)

Timefold Solver needs to extract the entity instances from the solution instance. It gets those collection(s) by calling every getter (or field) that is annotated with @PlanningEntityCollectionProperty:

@PlanningSolution
public class NQueens {
    ...

    private List<Queen> queenList;

    @PlanningEntityCollectionProperty
    public List<Queen> getQueenList() {
        return queenList;
    }

}

There can be multiple @PlanningEntityCollectionProperty annotated members. Those can even return a Collection with the same entity class type. Instead of Collection, it can also return an array.

A @PlanningEntityCollectionProperty annotation needs to be on a member in a class with a @PlanningSolution annotation. It is ignored on parent classes or subclasses without that annotation.

In rare cases, a planning entity might be a singleton: use @PlanningEntityProperty on its getter (or field) instead.

Both annotations can also be auto discovered if enabled.

9.4. Score of a Solution (@PlanningScore)

A @PlanningSolution class requires a score property (or field), which is annotated with a @PlanningScore annotation. The score property is null if the score hasn’t been calculated yet. The score property is typed to the specific Score implementation of your use case. For example, NQueens uses a SimpleScore:

@PlanningSolution
public class NQueens {
    ...

    private SimpleScore score;

    @PlanningScore
    public SimpleScore getScore() {
        return score;
    }
    public void setScore(SimpleScore score) {
        this.score = score;
    }

}

Most use cases use a HardSoftScore instead:

@PlanningSolution
public class CloudBalance {
    ...

    private HardSoftScore score;

    @PlanningScore
    public HardSoftScore getScore() {
        return score;
    }

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

}

Some use cases use other score types.

This annotation can also be auto discovered if enabled.

9.5. Problem facts of a solution (@ProblemFactCollectionProperty)

For Constraint Streams, Timefold Solver needs to extract the problem fact instances from the solution instance. It gets those collection(s) by calling every method (or field) that is annotated with @ProblemFactCollectionProperty. All objects returned by those methods are available to use by Constraint Streams. For example in NQueens all Column and Row instances are problem facts.

@PlanningSolution
public class NQueens {
    ...

    private List<Column> columnList;
    private List<Row> rowList;

    @ProblemFactCollectionProperty
    public List<Column> getColumnList() {
        return columnList;
    }

    @ProblemFactCollectionProperty
    public List<Row> getRowList() {
        return rowList;
    }

}

All planning entities are automatically inserted into the working memory. Do not add an annotation on their properties.

The problem facts methods are not called often: at most only once per solver phase per solver thread.

There can be multiple @ProblemFactCollectionProperty annotated members. Those can even return a Collection with the same class type, but they shouldn’t return the same instance twice. Instead of Collection, it can also return an array.

A @ProblemFactCollectionProperty annotation needs to be on a member in a class with a @PlanningSolution annotation. It is ignored on parent classes or subclasses without that annotation.

In rare cases, a problem fact might be a singleton: use @ProblemFactProperty on its method (or field) instead.

Both annotations can also be auto discovered if enabled.

9.5.1. Cached problem fact

A cached problem fact is a problem fact that does not exist in the real domain model, but is calculated before the Solver really starts solving. The problem facts methods have the opportunity 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 two Topics which share at least one Student.

    @ProblemFactCollectionProperty
    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;
    }

Where a score constraint needs to check that no two exams with a topic that shares a student are scheduled close together (depending on the constraint: at the same time, in a row, or in the same day), the TopicConflict instance can be used as a problem fact, rather than having to combine every two Student instances.

9.6. Auto discover solution properties

Instead of configuring each property (or field) annotation explicitly, some can also be deduced automatically by Timefold Solver. For example, on the cloud balancing example:

@PlanningSolution(autoDiscoverMemberType = AutoDiscoverMemberType.FIELD)
public class CloudBalance {

    // Auto discovered as @ProblemFactCollectionProperty
    @ValueRangeProvider
    private List<CloudComputer> computerList;

    // Auto discovered as @PlanningEntityCollectionProperty
    private List<CloudProcess> processList;

    // Auto discovered as @PlanningScore
    private HardSoftScore score;

    ...
}

The AutoDiscoverMemberType can be:

  • NONE: No auto discovery.

  • FIELD: Auto discover all fields on the @PlanningSolution class

  • GETTER: Auto discover all getters on the @PlanningSolution class

The automatic annotation is based on the field type (or getter return type):

  • @ProblemFactProperty: when it isn’t a Collection, an array, a @PlanningEntity class or a Score

  • @ProblemFactCollectionProperty: when it’s a Collection (or array) of a type that isn’t a @PlanningEntity class

  • @PlanningEntityProperty: when it is a configured @PlanningEntity class or subclass

  • @PlanningEntityCollectionProperty: when it’s a Collection (or array) of a type that is a configured @PlanningEntity class or subclass

  • @PlanningScore: when it is a Score or subclass

These automatic annotations can still be overwritten per field (or getter). Specifically, a BendableScore always needs to override with an explicit @PlanningScore annotation to define the number of hard and soft levels.

9.7. Cloning a solution

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.

There are many ways to clone, such as a shallow clone, deep clone, …​ This context focuses on a planning clone.

A planning clone of a solution must fulfill these requirements:

  • The clone must represent the same planning problem. Usually it reuses the same instances of the problem facts and problem fact collections as the original.

  • The clone must use different, cloned instances of the entities and entity collections. Changes to an original solution entity’s variables must not affect its clone.

solutionCloning

Implementing a planning clone method is hard, therefore you do not need to implement it.

9.7.1. FieldAccessingSolutionCloner

This SolutionCloner is used by default. It works well for most use cases.

When the FieldAccessingSolutionCloner clones one of your collections or maps, it may not recognize the implementation and replace it with ArrayList, LinkedHashSet, TreeSet, LinkedHashMap or TreeMap (whichever is more applicable) . It recognizes most of the common JDK collection and map implementations.

The FieldAccessingSolutionCloner does not clone problem facts by default. If any of your problem facts needs to be deep cloned for a planning clone, for example if the problem fact references a planning entity or the planning solution, mark its class with a @DeepPlanningClone annotation:

@DeepPlanningClone
public class SeatDesignationDependency {
    private SeatDesignation leftSeatDesignation; // planning entity
    private SeatDesignation rightSeatDesignation; // planning entity
    ...
}

In the example above, because SeatDesignationDependency references the planning entity SeatDesignation (which is deep planning cloned automatically), it should also be deep planning cloned.

Alternatively, the @DeepPlanningClone annotation also works on a getter method or a field to planning clone it. If that property is a Collection or a Map, it will shallow clone it and deep planning clone any element thereof that is an instance of a class that has a @DeepPlanningClone annotation.

Values of Java’s enum and record types are never deep-cloned. They are immutable by design and shouldn’t be used to store mutable state, such as planning entities.

9.7.2. Custom cloning with a SolutionCloner

To use a custom cloner, configure it on the planning solution:

@PlanningSolution(solutionCloner = NQueensSolutionCloner.class)
public class NQueens {
    ...
}

For example, a NQueens planning clone only deep clones all Queen instances. So when the original solution changes (later on during planning) and one or more Queen instances change, the planning clone isn’t affected.

public class NQueensSolutionCloner implements SolutionCloner<NQueens> {

    @Override
    public NQueens cloneSolution(CloneLedger ledger, NQueens original) {
        NQueens clone = new NQueens();
        ledger.registerClone(original, clone);
        clone.setId(original.getId());
        clone.setN(original.getN());
        clone.setColumnList(original.getColumnList());
        clone.setRowList(original.getRowList());
        List<Queen> queenList = original.getQueenList();
        List<Queen> clonedQueenList = new ArrayList<Queen>(queenList.size());
        for (Queen originalQueen : queenList) {
            Queen cloneQueen = new Queen();
            ledger.registerClone(originalQueen, cloneQueen);
            cloneQueen.setId(originalQueen.getId());
            cloneQueen.setColumn(originalQueen.getColumn());
            cloneQueen.setRow(originalQueen.getRow());
            clonedQueenList.add(cloneQueen);
        }
        clone.setQueenList(clonedQueenList);
        clone.setScore(original.getScore());
        return clone;
    }

}

The cloneSolution() 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 the problem facts were cloned too, then you would have to make sure that the new planning entity clones also refer to the new problem facts clones used by the cloned solution. For example, if you were to clone all Row instances, then each Queen clone and the NQueens clone itself should refer to those new Row clones.

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 its variable must point to the clone of B, not the original B.

9.8. Create an uninitialized solution

Create a @PlanningSolution instance to represent your planning problem’s dataset, so it can be set 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 = 0L;
        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;
    }
uninitializedNQueens04
Figure 1. Uninitialized Solution for the Four Queens Puzzle

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());
            long id = 0L;
            for (Course course : courseList) {
                for (int i = 0; i < course.getLectureSize(); i++) {
                    Lecture lecture = new Lecture();
                    lecture.setId(id);
                    id++;
                    lecture.setCourse(course);
                    lecture.setLectureIndexInCourse(i);
                    // Notice that we leave the PlanningVariable properties (period and room) on null
                    lectureList.add(lecture);
                }
            }
            schedule.setLectureList(lectureList);
        }