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 objects. 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 object with getters that does not change during planning. In school timetabling, the timeslots and rooms are problem facts:

Java
Python

public class Timeslot {

    DayOfWeek dayOfWeek;
    LocalTime startTime;
    LocalTime endTime;

    ...
}

@dataclass
class Timeslot:
    day_of_week: str
    start_time: time
    end_time: time
    ...

Java
Python

public class Room {

    String name;

    ...
}

@dataclass
class Room:
    name: str
    ...

A problem fact can reference other problem facts:

Java
Python

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
}

@dataclass
class Course:
    code: str

    teacher: Teacher  # Other problem fact
    lecture_size: int
    min_working_day_size: int

    curriculum_list: list[Curriculum]  # Other problem facts
    student_size: int
    # ... methods

A problem fact class does not require any Timefold Solver specific code. For example, you can reuse your domain classes, which might have JPA or Pydantic 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.

2.1. `@PlanningId`

For some functionality (such as multi-threaded solving and real-time planning), Timefold Solver needs to map problem facts and planning entities to an ID. Timefold Solver uses that ID to rebase a move from one thread’s solution state to another’s.

To enable such functionality, specify the @PlanningId annotation on the identification field or getter method, for example on the database ID:

Java
Python

public class Visit {

    @PlanningId
    private String username;

    ...
}

class Visit:
    username: Annotated[str, PlanningId]
    ...

A @PlanningId property must be:

Unique for that specific class
- It does not need to be unique across different problem fact classes (unless in that rare case that those classes are mixed in the same value range or planning entity collection).
An instance of a type that implements Object.hashCode() and Object.equals().
- It’s recommended to use the type Integer, int, Long, long, String or UUID.
Never null by the time Solver.solve() is called.

3. Planning entity

3.1. Planning entity annotation

A planning entity is a JavaBean (POJO) that changes during solving, for example a Lesson that changes timeslots. A planning problem has multiple planning entities; in school timetabling for example, each Lesson is a planning entity. But there is usually only one planning entity class, for example the Lesson 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. In school timetabling, a Lesson is defined by its subject, teacher and a student group, and has planning variables for its timeslot and room. This means that `Lesson’s subject, teacher and student group never changes during solving, while its timeslot and room do.

Java
Python

@PlanningEntity
public class Lesson {

    private String subject;
    private String teacher;
    private String studentGroup;

    // Planning variables: changes during planning, between score calculations.
    @PlanningVariable
    private Timeslot timeslot;
    @PlanningVariable
    private Room room;

    // ... getters and setters
}

@planning_entity
@dataclass
class Lesson:
    subject: str
    teacher: str
    student_group: str

    # Planning variables: changes during planning, between score calculations.
    timeslot: Annotated[Timeslot | None, PlanningVariable] = field(default=None)
    room: Annotated[Room | None, PlanningVariable] = field(default=None)
}

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>org.acme.schooltimetabling.domain.Lesson</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 move evaluation.

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

This feature is currently unsupported in Timefold Solver for Python.

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.

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 = VisitDifficultyComparator.class)
public class Visit {
    // ...
}

public class VisitDifficultyComparator implements Comparator<Visit> {

    public int compare(Visit a, Visit b) {
        return new CompareToBuilder()
                .append(a.getServiceDuration(), b.getServiceDuration())
                .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.

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 Lesson's timeslot 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 Lesson's timeslot property is a genuine planning variable. Note that even though a Lesson's timeslot property changes to another Timeslot during planning, no Timeslot 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 Lesson {
    ...

    private Timeslot timeslot;

    @PlanningVariable
    public Timeslot getTimeslot() {
        return timestlot;
    }

    public void setTimeslot(Timeslot timeslot) {
        this.timestlot = timeslot;
    }

    ...

}

Timefold Solver for Python does not currently support annotating method pairs for variables.

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:

Java
Python

@PlanningEntity
public class Lesson {
    ...

    @PlanningVariable
    private Timeslot timeslot;

    ...

}

@planning_entity
class Lesson:
    timeslot: Annotated[Timeslot | None, PlanningVariable]
    ...

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

4.2. Allowing unassigned values

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 allowsUnassigned to true:

Java
Python

    @PlanningVariable(..., allowsUnassigned = true)
    public Worker getWorker() {
        return worker;
    }

worker: Annotated[Worker, PlanningVariable(allows_unassigned=True)]

Constraint Streams filter out planning entities with a null planning variable by default. Use forEachIncludingUnassigned() 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 planning variable with unassigned values implies that your score calculation is responsible for punishing (or even rewarding) variables with a null value.

Failure to penalize unassigned variables can cause a solution with all variables unassigned to be the best solution. See the overconstrained planning with null variable values section in the docs for more infomation.

Currently chained planning variables are not compatible with allowsUnassigned.

Repeated planning (especially real-time planning) does not mix well with a planning variable that allows unassigned values. 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 allowsUnassigned. So a variable which allows unassigned values 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. 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).

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.

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:

Java
Python

@PlanningEntity
public class Lesson {

    @PlanningVariable(...)
    public Timeslot timeslot;

    ...

}

@planning_entity
class Lesson:
    timeslot: Annotated['Timeslot', PlanningVariable]
    ...

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

Java
Python

@PlanningEntity
public class Timeslot {

    @InverseRelationShadowVariable(sourceVariableName = "timeslot")
    public List<Lesson> lessons;

    ...

}

@planning_entity
class Timeslot:
    lesson_list: Annotated[list[Lesson], InverseRelationShadowVariable(source_variable_name ="timeslot")]
    ...

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:

Java
Python

@PlanningEntity
public class Customer ... {

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

}

@planning_entity
class Customer(Standstill):
    previous_standstill: Annotated[Standstill, PlanningVariable(graph_type=PlanningVariableGraphType.CHAINED, ...)]
    ...

And the shadow side looks like this:

Java
Python

@PlanningEntity
public class Standstill {

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

}

@planning_entity
class Standstill:
    next_customer: Annotated['Customer', InverseRelationShadowVariable(source_variable_name='previous_standstill')]
    ...

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:

Java
Python

@PlanningEntity
public class Customer {

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

}

@planning_entity
class Customer:
    vehicle: Annotated[Vehicle, AnchorShadowVariable(source_variable_name="previous_standstill")]

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

Java
Python

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

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

previous_standstill: Annotated[Standstill, PlanningVariable(...)]
vehicle: Annotated[Vehicle,
                   ShadowVariable(variable_listener_class=VehicleUpdatingVariableListener,
                                  source_variable_name = "previous_standstill")]

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.

Java
Python

public class VehicleUpdatingVariableListener implements VariableListener<VehicleRoutePlan, Customer> {

    public void afterEntityAdded(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit customer) {
        updateVehicle(scoreDirector, customer);
    }

    public void afterVariableChanged(ScoreDirector<VehicleRoutePlan> scoreDirector, Visit customer) {
        updateVehicle(scoreDirector, customer);
    }

    ...

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

}

class VehicleUpdatingVariableListener(VariableListener):
    def after_entity_added(self, score_director: ScoreDirector, customer):
        self.update_vehicle(score_director, customer)

    def after_variable_changed(self, score_director: ScoreDirector, customer):
        self.update_vehicle(score_director, customer)

    ...

    def update_vehicle(self, score_director: ScoreDirector, source_customer):
        previous_standstill = source_customer.previous_standstill
        vehicle = previous_standstill.vehicle if previous_standstill is not None else None
        shadow_customer = source_customer
        while shadow_customer is not None and shadow_customer.vehicle is not vehicle:
            score_director.before_variable_changed(shadow_customer, "vehicle")
            shadow_customer.vehicle = vehicle
            score_director.after_variable_changed(shadow_customer, "vehicle")
            shadow_customer = shadow_customer.next_customer

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

Java
Python

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

execution_mode: Annotated[ExecutionMode, PlanningVariable(...)]
delay: Annotated[int, PlanningVariable(...)]
predecessors_done_date: Annotated[int,
                                  ShadowVariable(variable_listener_class=PredecessorsDoneDateUpdatingVariableListener, source_variable_name="execution_mode"),
                                  ShadowVariable(variable_listener_class=PredecessorsDoneDateUpdatingVariableListener, source_variable_name="delay")
                                 ]

5.3.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:

Java
Python

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

previous_standstill: Annotated[Standstill, PlanningVariable(...)]
transport_time: Annotated[int,
                          ShadowVariable(variable_listener_class=TransportTimeAndCapacityUpdatingVariableListener,
                                         source_variable_name="previous_standstill")]
capacity: Annotated[int, PiggybackShadowVariable(shadow_variable_name="transport_time")]

5.3.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:

Java
Python

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

used_man_hours_per_day_map: Annotated[dict[datetime, int], DeepPlanningClone, ShadowVariable(...)]

5.4. 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:

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 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:

Java
Python

public class StartTimeUpdatingVariableListener implements VariableListener<TaskAssigningSolution, Task> {

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

    ...
}

class StartTimeUpdatingVariableListener(VariableListener):
    def requires_unique_entity_events(self):
        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. This does not apply to Timefold Solver for Python, since Python does not have primitive types.

A planning value range is the set of possible planning values for a planning variable. Planning value ranges need to come from a finite collection.

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.

Java
Python

    @PlanningVariable
    public Timeslot getTimeslot() {
        return timeslot;
    }

@PlanningSolution
public class Timetable {
    ...

    @ValueRangeProvider
    public List<Timeslot> getTimeslots() {
        return timeslots;
    }

}

timeslot: Annotated[Timeslot, PlanningVariable]

@planning_solution
class Timetable:
    ...
    def get_timeslots(self) -> Annotated[list[Timeslot], ValueRangeProvider]:
        ...

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

Annotating the field instead of the property works too:

Java
Python

@PlanningSolution
public class Timetable {
    ...

    @ValueRangeProvider
    private List<Timeslot> timeslots;

}

@planning_solution
class Timetable:
    timeslots: Annotated[list[Timeslot], ValueRangeProvider]

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.

Java
Python

    @PlanningVariable
    public Room getRoom() {
        return room;
    }

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

room: Annotated[Room, PlanningVariable]

def get_possible_room_list(self) -> Annotated[list[Room], ValueRangeProvider]:
    return self.course.teacher.department.room_list

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 `ValueRangeProvider`s

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 `ValueRangeProvider`s

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.

Java
Python

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

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

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

car: Annotated[Car, PlanningVariable]

def get_company_car_list(self) -> Annotated[list[Car], ValueRangeProvider]:
    return self.company_car_list

def get_personal_car_list(self) -> Annotated[list[Car], ValueRangeProvider(id="personal_car_range")]:
    return self.personal_car_list

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.

Java
Python

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

car: Annotated[Car, PlanningVariable]

def get_company_car_list(self) -> Annotated[list[CompanyCar], ValueRangeProvider]:
    return self.company_car_list

def get_personal_car_list(self) -> Annotated[list[PersonalCar], ValueRangeProvider]:
    return self.personal_car_list

def get_airplanes(self) -> Annotated[list[Airplane], ValueRangeProvider]:
    return self.airplane_list

Explicitly referenced `ValueRangeProvider`s

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

Java
Python

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

car: Annotated[Car, PlanningVariable(value_range_provider_refs = ["company_car_range"])]

def get_company_car_list(self) -> Annotated[list[CompanyCar], ValueRangeProvider(id = "company_car_range")]:
    return self.company_car_list

def get_personal_car_list(self) -> Annotated[list[PersonalCar], ValueRangeProvider(id = "personal_car_range")]:
    return self.personal_car_list

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

Java
Python

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

car: Annotated[Car, PlanningVariable(value_range_provider_refs = ["company_car_range", "personal_car_range"])]

def get_company_car_list(self) -> Annotated[list[CompanyCar], ValueRangeProvider(id = "company_car_range")]:
    return self.company_car_list

def get_personal_car_list(self) -> Annotated[list[PersonalCar], ValueRangeProvider(id = "personal_car_range")]:
    return self.personal_car_list

6.2.5. `ValueRangeFactory`

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

Java
Python

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

def get_delay_range(self) -> Annotated[CountableValueRange, ValueRangeProvider]:
    return ValueRangeFactory.create_int_value_range(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:

Java
Python

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

def get_stock_amount_range(self) -> Annotated[CountableValueRange, ValueRangeProvider]:
    # Range: 0, 200, 400, 600, ..., 9999600, 9999800, 10000000
    return ValueRangeFactory.create_int_value_range(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

This feature is currently unsupported in Timefold Solver for Python.

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. 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 = VehicleStrengthComparator.class)
    public Vehicle getVehicle() {
        return vehicle;
    }

public class VehicleStrengthComparator implements Comparator<Vehicle> {

    public int compare(Vehicle a, Vehicle b) {
        return new CompareToBuilder()
                .append(a.getCapacity(), b.getCapacity())
                .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.

See sorted selection for more information.

Strength should be implemented ascending: weaker values are lower, stronger values are higher. 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 timeslot variables of any Lesson may be used to determine the strength of a Timeslot.

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.

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:

planning entity difficulty comparison or planning value strength comparison,
exhaustive search,
partitioned search,
coexistence with another list or basic planning variable.

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

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:

Java
Python

@PlanningEntity
class Vehicle {

    int capacity;
    Depot depot;

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

@planning_entity
@dataclass
class Vehicle:
    capacity: int
    depot: Depot
    customers: Annotated[list[Customer], PlanningListVariable] = field(default_factory=list)

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

There is a one-to-many relationship between the planning entity and the planning value.
The order in which planning values are assigned to an entity’s list variable is significant.
Each planning value is assigned to exactly one planning entity. No planning value may appear in multiple entities.

7.1. Allowing unassigned values

By default, all planning values have to be assigned to exactly one list variable across the entire planning model. 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 a planning value to be unassigned, set allowsUnassignedValues to true:

Java
Python

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

customers: Annotated[list[Customer], PlanningListVariable(allows_unassigned_values=True)] = field(default_factory=list)

Constraint Streams filter out unassigned planning values by default. Use forEachIncludingUnassigned() to avoid such unwanted behaviour. Using a planning list variable with unassigned values implies that your score calculation is responsible for punishing (or even rewarding) these unassigned values.

Failure to penalize unassigned values can cause a solution with all values unassigned to be the best solution. See the overconstrained planning with null variable values section in the docs for more infomation.

Repeated planning (especially real-time planning) does not mix well with a planning list variable that allows unassigned values. 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>
    <queuedValuePlacer>
      <valueSelector id="selector1">
        <filterClass>...</filterClass>
      </valueSelector>
    </queuedValuePlacer>
    ...
    <listChangeMoveSelector>
      <valueSelector mimicSelectorRef="selector1" />
    </listChangeMoveSelector>
    ...
  </constructionHeuristic>
 ...
</solver>

7.2. List variable shadow variables

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

7.2.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:

Java
Python

@PlanningEntity
public class Vehicle {

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

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

@planning_entity
@dataclass
class Vehicle:
    customers: Annotated[list[Customer], PlanningListVariable] = field(default_factory=list)

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.

Java
Python

@PlanningEntity
public class Customer {

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

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

@planning_entity
class Customer:
    vehicle: Annotated['Vehicle', InverseRelationShadowVariable(source_variable_name="customers")]

7.2.2. Index shadow variable

While the @InverseRelationShadowVariable allows to establish the bi-directional relationship between the entity and the elements assigned to its list variable, @IndexShadowVariable provides a pointer into the entity’s list variable where the element is assigned.

The planning entity side has a genuine list variable:

Java
Python

@PlanningEntity
public class Vehicle {

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

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

@planning_entity
@dataclass
class Vehicle:
    customers: Annotated[list[Customer], PlanningListVariable] = field(default_factory=list)

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 which returns an Integer. Integer is required instead of int, as the index may be null if the element is not yet assigned to the list variable.
Annotate it with @IndexShadowVariable and set sourceVariableName to the name of the genuine planning list variable.

Java
Python

@PlanningEntity
public class Customer {

    @IndexShadowVariable(sourceVariableName = "customers")
    public Integer getIndexInVehicle() {
        return indexInVehicle;
    }

}

@planning_entity
class Customer:
    index_in_vehicle: Annotated[int, IndexShadowVariable(source_variable_name="customers")]

7.2.3. 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:

Java
Python

@PlanningEntity
public class Vehicle {

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

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

@planning_entity
@dataclass
class Vehicle:
    customers: Annotated[list[Customer], PlanningListVariable] = field(default_factory=list)

On the element side:

Java
Python

@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) {...}

@planning_entity
class Customer:
    previous_customer: Annotated['Customer', PreviousElementShadowVariable(source_variable_name="customers")]
    next_customer: Annotated['Customer', NextElementShadowVariable(source_variable_name="customers")]

7.3. Updating tail chains

The annotation @CascadingUpdateShadowVariable provides a built-in listener that updates a set of connected elements. Timefold Solver triggers a user-defined logic after all events are processed. Hence, the related listener is the final one executed during the event lifecycle. Moreover, it automatically propagates changes to the subsequent elements in the list when the value of the related shadow variable changes.

The planning entity side has a genuine list variable:

Java
Python

@PlanningEntity
public class Vehicle {

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

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

@planning_entity
@dataclass
class Vehicle:
    customers: Annotated[list[Customer], PlanningListVariable] = field(default_factory=list)

On the element side:

Java
Python

@PlanningEntity
public class Customer {

    @InverseRelationShadowVariable(sourceVariableName = "customers")
    private Vehicle vehicle;
    @PreviousElementShadowVariable(sourceVariableName = "customers")
    private Customer previousCustomer;
    @CascadingUpdateShadowVariable(targetMethodName = "updateArrivalTime")
    private LocalDateTime arrivalTime;

    ...

    public void updateArrivalTime() {...}

@planning_entity
class Customer:
    vehicle: Annotated['Vehicle', InverseRelationShadowVariable(source_variable_name="customers")]
    previous_customer: Annotated['Customer', PreviousElementShadowVariable(source_variable_name="customers")]
    arrival_time: Annotated[datetime, CascadingUpdateShadowVariable(target_method_name = "update_arrival_time")]

    def update_arrival_time(self) -> None:
        ...

The targetMethodName refers to the user-defined logic that updates the annotated shadow variable. The method must be implemented in the defining entity class, be non-static, and not include any parameters.

In the previous example, the cascade update listener calls updateArrivalTime after all shadow variables have been updated, including vehicle and previousCustomer. It then automatically calls updateArrivalTime for the subsequent customers and stops when the arrivalTime value does not change after running target method or when it reaches the end.

A user-defined logic can only change shadow variables. Changing a genuine planning variable or a problem fact will result in score corruption.

When distinct target methods are used by separate @CascadingUpdateShadowVariable variables in the same model, the order of their execution is undefined.

7.3.1. Multiple sources

If the user-defined logic requires updating multiple shadow variables, apply the @CascadingUpdateShadowVariable to all shadow variables.

Java
Python

@PlanningEntity
public class Customer {

    @PreviousElementShadowVariable(sourceVariableName = "customers")
    private Customer previousCustomer;
    @NextElementShadowVariable(sourceVariableName = "customers")
    private Customer nextCustomer;
    @CascadingUpdateShadowVariable(targetMethodName = "updateWeightAndArrivalTime")
    private LocalDateTime arrivalTime;
    @CascadingUpdateShadowVariable(targetMethodName = "updateWeightAndArrivalTime")
    private Integer weightAtVisit;
    ...

    public void updateWeightAndArrivalTime() {...}

@planning_entity
class Customer:
    previous_customer: Annotated['Customer', PreviousElementShadowVariable(source_variable_name="customers")]
    next_customer: Annotated['Customer', NextElementShadowVariable(source_variable_name="customers")]
    arrival_time: Annotated[datetime, CascadingUpdateShadowVariable(target_method_name = "update_weight_and_arrival_time")]
    weight_at_visit: Annotated[int, CascadingUpdateShadowVariable(target_method_name = "update_weight_and_arrival_time")]

    def update_weight_and_arrival_time(self) -> None:
        ...

Timefold Solver triggers a single listener to run the user-defined logic at the end of the event lifecycle. It stops when both arrivalTime and weightAtVisit values do not change or when it reaches the end.

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. Only 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:

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:

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):

Java
Python

public class Domicile ... implements Standstill {
    ...

    public City getCity() {...}

}

class Domicile(Standstill):
    def get_city(self) -> City:
        ...

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

Java
Python

public interface Standstill {

    City getCity();

}

class Standstill(ABC):
    @abstractmethod
    def get_city(self) -> City:
        ...

That interface is the return type of the planning variable. Furthermore, the planning variable is chained. For example, TSP’s Visit would look like this:

Java
Python

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

}

@planning_entity
class Visit(Standstill):
    previous_standstill: Annotated[Standstill, PlanningVariable(graph_type=PlanningVariableGraphType.CHAINED)]
    ...

    def get_city(self) -> City:
        ...

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.

Since Domicile and Visit both implement Standstill, an anonymous value range on Standstill will combine both value ranges.

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. In school timetabling, the solution class is the Timetable class, which contains a Timeslot list, a Room list, and a Lesson list.

A planning problem is actually an unsolved planning solution or - stated differently - an uninitialized solution. In school timetabling, that Timetable class has the @PlanningSolution annotation, yet every Lesson in an unsolved Timetable class is not yet assigned to a Timeslot (their timeslot 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 Timetable instance holds a list of all timeslots, all rooms and all Lesson instances:

Java
Python

@PlanningSolution
public class Timetable {

    private String name;

    // Problem facts
    private List<Timeslot> timeslots;
    private List<Room> rooms;

    // Planning entities
    private List<Lesson> lessons;

    private HardSoftScore score;

    ...
}

@planning_solution
class Timetable:
    name: str

    # Problem facts
    timeslots: Annotated[list[Timeslot], ProblemFactCollectionProperty]
    rooms: Annotated[list[Room], ProblemFactCollectionProperty]

    # Planning entities
    lessons: Annotated[list[Lesson], PlanningEntityCollectionProperty]

    score: Annotated[HardSoftScore | None, PlanningScore]
    ...

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>org.acme.schooltimetabling.Timetable</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:

Java
Python

@PlanningSolution
public class Timetable {
    ...

    private List<Lesson> lessons;

    @PlanningEntityCollectionProperty
    public List<Lesson> getLessons() {
        return lessons;
    }

}

@planning_solution
class Timetable:
    ...
    lessons: Annotated[list[Lesson], PlanningEntityCollectionProperty]
    ...

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. Most use cases use a HardSoftScore:

Java
Python

@PlanningSolution
public class Timetable {

    ...

    @PlanningScore
    private HardSoftScore score;

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

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

    ...

}

@planning_solution
class Timetable:
    ...
    score: Annotated[HardSoftScore | None, PlanningScore]
    ...

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 Timetable all Timeslot and Room instances are problem facts.

Java
Python

@PlanningSolution
public class Timetable {

    ...

    @ProblemFactCollectionProperty
    @ValueRangeProvider
    private List<Timeslot> timeslots;

    @ProblemFactCollectionProperty
    @ValueRangeProvider
    private List<Room> rooms;

    ...

}

@planning_solution
class Timetable:
    ...
    timeslots: Annotated[list[Timeslot], ProblemFactCollectionProperty]
    rooms: Annotated[list[Room], ProblemFactCollectionProperty]
    ...

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.

Java
Python

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

    def calculate_topic_conflict_list(self) -> Annotated[list[TopicConflict], ProblemFactCollectionProperty]:
        return [
            TopicConflict(left_topic, right_topic, student_size)
            for left_topic in self.topics
            for right_topic in self.topics
            if left_topic.id < right_topic.id
            and (student_size := len({
                student
                for student in left_topic.students
                if student in right_topic.students
            })) > 0
        ]

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:

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

        ...

}

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.

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`

This feature is not supported in Timefold Solver for Python.

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

@PlanningSolution(solutionCloner = TimetableSolutionCloner.class)
public class Timetable {
    ...
}

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

The cloneSolution() method should only deep clone the planning entities. The problem facts, such as Timeslot and Room 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 Timeslot instances, then each Lesson clone and the Timetable clone itself should refer to those new Timeslot 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.

In school timetabling, a Timetable instance is created with the required Room and Timeslot instances and every Lesson has its planning variables set to null:

Java
Python

    public static Timetable generateDemoData(DemoData demoData) {
        List<Timeslot> timeslots = new ArrayList<>(10);
        long nextTimeslotId = 0L;
        timeslots.add(new Timeslot(Long.toString(nextTimeslotId++), DayOfWeek.MONDAY, LocalTime.of(8, 30), LocalTime.of(9, 30)));
        timeslots.add(new Timeslot(Long.toString(nextTimeslotId++), DayOfWeek.MONDAY, LocalTime.of(9, 30), LocalTime.of(10, 30)));
        timeslots.add(new Timeslot(Long.toString(nextTimeslotId++), DayOfWeek.MONDAY, LocalTime.of(10, 30), LocalTime.of(11, 30)));
        timeslots.add(new Timeslot(Long.toString(nextTimeslotId++), DayOfWeek.MONDAY, LocalTime.of(13, 30), LocalTime.of(14, 30)));
        timeslots.add(new Timeslot(Long.toString(nextTimeslotId++), DayOfWeek.MONDAY, LocalTime.of(14, 30), LocalTime.of(15, 30)));
        ...

        List<Room> rooms = new ArrayList<>(3);
        long nextRoomId = 0L;
        rooms.add(new Room(Long.toString(nextRoomId++), "Room A"));
        rooms.add(new Room(Long.toString(nextRoomId++), "Room B"));
        rooms.add(new Room(Long.toString(nextRoomId++), "Room C"));

        List<Lesson> lessons = new ArrayList<>();
        long nextLessonId = 0L;
        lessons.add(new Lesson(Long.toString(nextLessonId++), "Math", "A. Turing", "9th grade"));
        lessons.add(new Lesson(Long.toString(nextLessonId++), "Math", "A. Turing", "9th grade"));
        lessons.add(new Lesson(Long.toString(nextLessonId++), "Physics", "M. Curie", "9th grade"));
        lessons.add(new Lesson(Long.toString(nextLessonId++), "Chemistry", "M. Curie", "9th grade"));
        lessons.add(new Lesson(Long.toString(nextLessonId++), "Biology", "C. Darwin", "9th grade"));
        ...

        return new Timetable(demoData.name(), timeslots, rooms, lessons);
    }

def id_generator():
    current = 0
    while True:
        yield str(current)
        current += 1

def generate_demo_data(demo_data: DemoData) -> Timetable:
    timeslot_ids = id_generator()
    room_ids = id_generator()
    lesson_ids = id_generator()

    timeslots = [
        Timeslot(next(timeslot_ids), day, start, start.replace(hour=start.hour + 1))
        for day in ('MONDAY', 'TUESDAY', 'WEDNESDAY', 'THURSDAY', 'FRIDAY')
        for start in (time(8, 30), time(9, 30), time(10, 30), time(13, 30), time(14, 30))
    ]
    rooms = [Room(next(room_ids), f'Room {name}') for name in ('A', 'B', 'C')]

    lessons = []
    lessons.append(Lesson(next(lesson_ids), "Math", "A. Turing", "9th grade"))
    lessons.append(Lesson(next(lesson_ids), "Math", "A. Turing", "9th grade"))
    lessons.append(Lesson(next(lesson_ids), "Physics", "M. Curie", "9th grade"))
    lessons.append(Lesson(next(lesson_ids), "Chemistry", "M. Curie", "9th grade"))
    lessons.append(Lesson(next(lesson_ids), "Biology", "C. Darwin", "9th grade"))
    ...

    return Timetable(demo_data.name, timeslots, rooms, lessons)

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 for the solver to plan.

Modeling planning problems

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

2. Problem fact

2.1. @PlanningId

3. Planning entity

3.1. Planning entity annotation

3.2. Planning entity difficulty

4. Planning variable (genuine)

4.1. Planning variable annotation

4.2. Allowing unassigned values

4.3. When is a planning variable considered initialized?

5. Planning variable (shadow)

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

5.2. Anchor shadow variable

5.3. Custom VariableListener

5.3.1. Multiple source variables

5.3.2. Piggyback shadow variable

5.3.3. Shadow variable cloning

5.4. VariableListener triggering order

6. Planning value and planning value range

6.1. Planning value

6.2. Planning value range provider

6.2.1. Overview

6.2.2. ValueRangeProvider on the solution

6.2.3. ValueRangeProvider on the Planning Entity

6.2.4. Referencing ValueRangeProviders

Anonymous ValueRangeProviders

Explicitly referenced ValueRangeProviders

6.2.5. ValueRangeFactory

6.3. Planning value strength

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

7.1. Allowing unassigned values

7.2. List variable shadow variables

7.2.1. Inverse relation shadow variable

7.2.2. Index shadow variable

7.2.3. Previous and next element shadow variable

7.3. Updating tail chains

7.3.1. Multiple sources

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

9. Planning problem and planning solution

9.1. Planning problem instance

9.2. Solution class

9.3. Planning entities of a solution (@PlanningEntityCollectionProperty)

9.4. Score of a Solution (@PlanningScore)

9.5. Problem facts of a solution (@ProblemFactCollectionProperty)

9.5.1. Cached problem fact

9.6. Auto discover solution properties

9.7. Cloning a solution

9.7.1. FieldAccessingSolutionCloner

9.7.2. Custom cloning with a SolutionCloner

9.8. Create an uninitialized solution

2.1. `@PlanningId`

5.3. Custom `VariableListener`

6.2.2. `ValueRangeProvider` on the solution

6.2.3. `ValueRangeProvider` on the Planning Entity

6.2.4. Referencing `ValueRangeProvider`s

Anonymous `ValueRangeProvider`s

Explicitly referenced `ValueRangeProvider`s

6.2.5. `ValueRangeFactory`

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

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

9.3. Planning entities of a solution (`@PlanningEntityCollectionProperty`)

9.4. `Score` of a Solution (`@PlanningScore`)

9.5. Problem facts of a solution (`@ProblemFactCollectionProperty`)

9.7.1. `FieldAccessingSolutionCloner`

9.7.2. Custom cloning with a `SolutionCloner`