OptaPy configuration

1. Overview

Solving a planning problem with OptaPy consists of the following steps:

  1. Model your planning problem as a class annotated with the @planning_solution decorator, for example the NQueens class.

  2. Configure a Solver, for example a First Fit and Tabu Search solver for any NQueens instance.

  3. Load a problem data set from your data layer, for example a Four Queens instance. That is the planning problem.

  4. Solve it with Solver.solve(problem) which returns the best solution found.

inputOutputOverview

2. Solver configuration

2.1. Solver configuration by XML

Build a Solver instance with the SolverFactory. Create a SolverFactory by passing a SolverConfig to solver_factory_create. A SolverConfig can be created from a XML file, like so:

from optapy import solver_config_create_from_xml_file
import pathlib

solver_config = solver_config_create_from_xml_file(pathlib.Path('solverConfig.xml'))

solver_factory = solver_factory_create(solver_config)

solver_factory.buildSolver().solve(generate_problem())

A solver configuration XML file looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <!-- Define the model -->
  <solutionClass>optapy.examples.domain.NQueens</solutionClass>
  <entityClass>optapy.examples.domain.Queen</entityClass>

  <!-- Define the score function -->
  <scoreDirectorFactory>
    <constraintProviderClass>optapy.examples.constraints.n_queens_constraints</constraintProviderClass>
  </scoreDirectorFactory>

  <!-- Configure the optimization algorithms (optional) -->
  <termination>
    ...
  </termination>
  <constructionHeuristic>
    ...
  </constructionHeuristic>
  <localSearch>
    ...
  </localSearch>
</solver>

For XML elements that end in "Class" (solutionClass, entityClass, constraintProviderClass, etc.), put "{module}.{name}", where {module} is the module the class/function was defined in, and name is the name of the class/function. If the module is "__main__", put "{name}" instead. For instance, if the below code was in the main module:

from optapy import constraint_provider, planning_solution
from my.domain import MyEntity

@planning_solution
class MySolution:
    ...

@constraint_provider
def my_constraints(constraint_factory):
    ...

Use "my.domain.MyEntity" to refer to "MyEntity", "MySolution" to refer to "MySolution", and "my_constraints" to refer to "my_constraints".

Notice the three parts in it:

  • Define the model.

  • Define the score function.

  • Optionally configure the optimization algorithm(s).

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

OptaPy makes it relatively easy to switch optimization algorithm(s) just by changing the configuration.

2.2. Solver configuration by Python API

A solver configuration can also be configured with the SolverConfig API. This is especially useful to change some values dynamically at runtime. For example, to change the running time based on an environment variable, before building the Solver:

import os
import optapy
import optapy.config
import pathlib

SOLVE_TIME_IN_MINUTES = os.environ['SOLVE_TIME_IN_MINUTES']
termination_config = optapy.config.solver.TerminationConfig() \
    .withMinutesSpentLimit(SOLVE_TIME_IN_MINUTES)

solver_config = solver_config_create_from_xml_file(pathlib.Path('solverConfig.xml')) \
    .withTerminationConfig(termination_config)

solver_factory = solver_factory_create(solver_config)

solver_factory.buildSolver().solve(generate_problem())

Every element in the solver configuration XML is available as a *Config class or a property on a *Config class in the package optapy.config. These *Config classes are the Python representation of the XML format. They build the runtime components and assemble them into an efficient Solver.

To configure a SolverFactory dynamically for each user request, build a template SolverConfig during initialization and copy it with the copy constructor for each user request:

termination_config = optapy.config.solver.TerminationConfig()
template = solver_config_create_from_xml_file(pathlib.Path('solverConfig.xml')) \
    .withTerminationConfig(termination_config)

# Called concurrently from different threads
def user_request(..., user_input):
    solver_config = optapy.config.solver.SolverConfig(template) # Copy it
    solver_config.getTerminationConfig().setMinutesSpentLimit(user_input)
    solver_factory = solver_factory_create(solver_config)
    solver = solver_factory.buildSolver()
    ...

3. Model a planning problem

3.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 xref:repeated-planning/repeated-planning.adoc#realTimePlanning[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 OptaPy, all problem facts and planning entities are plain old Python Objects. Load them from a database, an XML file, a data repository, a REST service, a noSQL cloud; it doesn’t matter.

3.2. Problem fact

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

from optapy import problem_fact

@problem_fact
class Column:
    def __init__(self, index):
        self.index = index
    ...
from optapy import problem_fact

@problem_fact
class Row:
    def __init__(self, index):
        self.index = index
    ...

A problem fact can reference other problem facts of course:

from optapy import problem_fact

@problem_fact
class Teacher:
    ...

@problem_fact
class Curriculum:
    ...

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

Unlike OptaPlanner, a problem fact class must be decorated with @problem_fact to be used in constraints.

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 OptaPy 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.3. Planning entity

3.3.1. Planning entity decorator

A planning entity is a Python Object 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 decorated with the @planning_entity decorator.

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.

from optapy import planning_entity

@planning_entity
class Queen:
    column: Column

    # Planning variables: changes during planning, between score calculations.
    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.

from optapy import planning_entity

@planning_entity
class Lecture:
    course: Course
    lectureIndexInCourse: int

    # Planning variables: changes during planning, between score calculations.
    period: Period
    room: Room
    ...

The solver configuration needs to declare each planning entity class:

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  ...
  <entityClass>optapy.examples.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 __hash__(self) implementations must remain constant. Therefore entity __hash__(self) must not depend on any planning variables. Pay special attention when using data structures with auto-generated __hash__(self) as entities, such as Python @dataclass.

3.3.2. Planning entity difficulty

Planning entity difficulty is not yet supported, but will be in a future version.

3.4. Planning variable (genuine)

3.4.1. Planning variable decorator

A planning variable is a Python 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 @planning_variable annotation, which needs a non-empty variable_type and value_range_provider_refs property.

from optapy import planning_entity, planning_variable

@planning_entity
class Queen:
    # ...
    row: Row

    # Alternatively, @planning_variable(Row, ["row_range"])
    @planning_variable(variable_type = Row, value_range_provider_refs = ["row_range"])
    def get_row(self):
        return self.row

    def set_row(self, row):
        self.row = row

The variable_type property define the type of planning values this planning variable takes. The variable_type does not need to be decorated with @problem_fact; it can be any Python type. The value_range_provider_refs property defines what are the possible planning values for this planning variable. It references one or more @ValueRangeProvider id's.

3.4.2. Nullable planning variable

By default, an initialized planning variable cannot be None, so an initialized solution will never use None 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 None, set nullable to True:

    @planning_variable(..., nullable = True)
    def get_worker(self):
        return self.worker

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

OptaPy will automatically add the value None to the value range. There is no need to add None in a collection provided by a @value_range_provider.

Using a nullable planning variable implies that your score calculation is responsible for punishing (or even rewarding) variables with a None 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 None 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://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  ...
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="entitySelector1">
        <filterClass>...</filterClass>
      </entitySelector>
    </queuedEntityPlacer>
    ...
    <changeMoveSelector>
      <entitySelector mimicSelectorRef="entitySelector1" />
    </changeMoveSelector>
    ...
  </constructionHeuristic>
 ...
</solver>

3.4.3. When is a planning variable considered initialized?

A planning variable is considered initialized if its value is not None 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.

3.4.4. 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 int. It can even be another planning entity or even an interface implemented by both a planning entity and a problem fact.

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 float between 0.0 and 1.0).

3.4.5. Planning value range provider

Overview

The value range of a planning variable is defined with the @value_range_provider decorator. A @value_range_provider decorator always has a property range_id, which is referenced by the @planning_variable's property value_range_provider_refs.

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 @value_range_provider annotation needs to be on a member in a class with a @planning_solution or a @planning_entity annotation. It is ignored on parent classes or subclasses without those annotations.

The return type of that method can be two types:

  • List: The value range is defined by a list of its possible values.

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

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 @planning_solution implementation has method that returns a list (or a ValueRange). Any value from that list is a possible planning value for this planning variable.

    @planning_variable(Row, value_range_provider_refs = {"row_range"})
    def get_row(self):
        return self.row
from optapy import planning_solution, value_range_provider, problem_fact_collection_property

@planning_solution
class NQueens:
    # ...
    @value_range_provider(range_id = "row_range")
    def get_row_list(self):
        return self.row_list

That list (or ValueRange) must not contain the value null, not even for a nullable planning variable.
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.

    @planning_variable(Room, value_range_provider_refs = ["department_room_range"])
    def get_room(self):
        return self.room

    @value_range_provider(range_id = "department_room_range", value_range_type = Room)
    def get_possible_room_list(self):
        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 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 instances contain the same Room instance.

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

A @value_range_provider on the planning entity is not currently compatible with a chained variable.
ValueRangeFactory

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

from optapy import planning_solution, value_range_provider
from optapy.types import CountableValueRange, ValueRangeFactory

    @value_range_provider(range_id = "delay_range", value_range_type = CountableValueRange)
    def get_delay_range(self):
        return ValueRangeFactory.createIntValueRange(0, 5000)

A ValueRange uses far less memory, because it only holds the bounds. In the example above, a list 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:

from optapy import planning_solution, value_range_provider
from optapy.types import CountableValueRange, ValueRangeFactory

    @value_range_provider(range_id = "stock_amount_range", value_range_type = CountableValueRange)
    def get_stock_amount_range(self) {
        # Range: 0, 200, 400, 600, ..., 9999600, 9999800, 10000000
        return ValueRangeFactory.createIntValueRange(0, 10000000, 200)
    }

Return CountableValueRange instead of ValueRange whenever possible (so OptaPy 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.

Combine ValueRangeProviders

Value range providers can be combined, for example:

    @planning_variable(value_range_provider_refs = ["company_car_range", "personal_car_range"])
    def get_car(self):
        return self.car
    }
    @value_range_provider(id = "company_car_range")
    def get_company_car_list(self):
        return self.company_car_list

    @value_range_provider(id = "personal_car_range")
    def get_personal_car_list(self):
        return self.personal_car_list

3.4.6. Planning value strength

Planning value difficulty is not yet supported, but will be in a future version.

3.4.7. Planning List Variable

In some use cases, such as Vehicle Routing and Task Assignment, it is more convenient to model the planning variables as a list. For example, the list of customers a vehicle visits, or the list of tasks a person does. In OptaPy, this is accomplished by using planning list variables.

For a planning list variable with value range "value_range":

  • The order of elements inside the list is significant

  • All values in "value_range" appear in exactly one planning entity’s planning list variable

To declare a planning list variable, use the @planning_list_variable decorator:

from optapy import planning_entity, planning_list_variable

@planning_entity
class Vehicle:
    def __init__(self, _id, capacity, depot, customer_list=None):
        self.id = _id
        self.capacity = capacity
        self.depot = depot
        if customer_list is None:
            self.customer_list = []
        else:
            self.customer_list = customer_list

    @planning_list_variable(Customer, ['customer_range'])
    def get_customer_list(self):
        return self.customer_list

    ...

The getter for @planning_list_variable can never return None.

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

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

Planning list variables can also be used for these use cases

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

from optapy import problem_fact, planning_entity, planning_variable
from optapy.types import PlanningVariableGraphType

@problem_fact
class Standstill:
    def get_city(self):
        raise NotImplementedError()


@problem_fact
class Domicile(Standstill):
    # ...
    def get_city(self):
        return self.city


@planning_entity
class Visit(Standstill):
    # ...
    @planning_variable(Standstill, value_range_provider_refs=['domicile_range', 'visit_range'],
                              graph_type=PlanningVariableGraphType.CHAINED)
    def get_previous_standstill(self):
        return self.previous_standstill

    def set_previous_standstill(self, previous_standstill):
        self.previous_standstill = previous_standstill

Notice how two value range providers are usually combined:

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

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

3.5. Planning problem and planning solution

3.5.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 decorated with a @planning_solution decorator. 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 @planning_solution 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.

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

from optapy import planning_solution
from optapy.score import SimpleScore

@planning_solution
class NQueens:
    # Problem facts
    n: int
    column_list: list[Column]
    row_list: list[Row]

    # Planning entities
    queen_list: list[Queen]

    score: SimpleScore
    ...

The solver configuration needs to declare the planning solution class:

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

3.5.3. Planning entities of a solution (@planning_entity_collection_property)

OptaPy needs to extract the entity instances from the solution instance. It gets those collection(s) by calling every getter that is annotated with @planning_entity_collection_property:

from optapy import planning_solution, planning_entity_collection_property

@planning_solution
class NQueens :
    # ...
    queen_list: list[Queen]

    @planning_entity_collection_property(Queen)
    def get_queen_list(self):
        return self.queen_list

There can be multiple @planning_entity_collection_property decorated getters. Those can even return a list with the same entity class type.

A @planning_entity_collection_property annotation needs to be on a getter in a class with a @planning_solution decorator. It is ignored on parent classes or subclasses without that decorator.

In rare cases, a planning entity might be a singleton: use planning_entity_property on its getter instead.

3.5.4. Score of a Solution (@PlanningScore)

A @planning_solution class requires a score property (or field), which is annotated with a @planning_score annotation. The score property is None 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:

from optapy import planning_solution, planning_score
from optapy.score import SimpleScore

@planning_solution
class NQueens:
    # ...
    score: SimpleScore

    @planning_score(SimpleScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score

Most use cases use a HardSoftScore instead:

@planning_solution
class CloudBalance:
    # ...
    score: HardSoftScore

    @planning_score(HardSoftScore)
    def get_score(self):
        return self.score

    def set_score(self, score):
        self.score = score

Some use cases use other score types.

3.5.5. Problem facts of a solution (@problem_fact_collection_property)

For Constraint Streams score calculation, OptaPlanner 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 @problem_fact_collection_property. 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.

from optapy import planning_solution, problem_fact_collection_property

@planning_solution
class NQueens:
    # ...

    column_list: list[Column]
    row_list: list[Row]

    @problem_fact_collection_property(Column)
    def get_column_list(self):
        return self.column_list

    @problem_fact_collection_property(Row)
    def get_row_list(self):
        return self.row_list

All planning entities are automatically inserted into the working memory. Do not add @problem_fact_collection_property 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 @problem_fact_collection_property annotated members. Those can even return a list with the same class type, but they shouldn’t return the same instance twice.

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

In rare cases, a problem fact might be a singleton: use @problem_fact_property on its method instead.

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.

    @problem_fact_collection_property(TopicConflict)
    def calculate_topic_conflict_list(self): list[TopicConflict]:
        topic_conflict_list = []
        for left_topic in self.topic_list:
            for right_topic in self.topic_list:
                if left_topic.topic_id < right_topic.topic_id:
                    student_size = 0
                    for student in left_topic.student_list:
                        if student in right_topic.student_list:
                            student_size += 1
                    if student_size > 0:
                        topic_conflict_list.append(TopicConflict(left_topic, right_topic, student_size))
        return topic_conflict_list

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.

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

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 list, set or map (whichever is more applicable).

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 @deep_planning_clone decorator:

from optapy import problem_fact, deep_planning_clone

@problem_fact
@deep_planning_clone
class SeatDesignationDependency:
    left_seat_designation: SeatDesignation # planning entity
    right_seat_designation: SeatDesignation # 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 @deep_planning_clone decorator also works on a getter method to planning clone it. If that property is a list 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 @deep_planning_clone decorator.

3.5.7. Create an uninitialized solution

Create a @planning_solution class 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.

    def create_n_queens(n: int) -> NQueens:
        n_queens = NQueens()
        n_queens.n = n
        n_queens.column_list = create_column_list(n_queens)
        n_queens.row_list = create_row_list(n_queens)
        n_queens.queen_list = create_queen_list(n_queens)
        return n_queens

    def create_queen_list(n_queens: NQueens) -> list[Queen]:
        n = n_queens.n
        queen_list = []
        queen_id = 0
        for column in n_queens.column_list:
            queen = Queen()
            queen.queen_id = id
            queen_id += 1
            queen.column = column
            # Notice that we leave the PlanningVariable properties as None
            queen_list.append(queen)
        return queen_list
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:

def create_lecture_list(schedule: CourseSchedule):
    course_list = schedule.course_list
    lecture_list = []
    lecture_id = 0
    for course in course_list:
        for i in range(course.lecture_size):
            lecture = Lecture()
            lecture.lecture_id = lecture_id
            lecture_id += 1
            lecture.course = course
            lecture.lecture_index_in_course = i
            # Notice that we leave the PlanningVariable properties (period and room) as None
            lecture_list.append(lecture)
    schedule.lecture_list = lecture_list

4. Use the Solver

4.1. The Solver interface

A Solver solves your planning problem.

A Solver can only solve one planning problem instance at a time. It is built with a SolverFactory, there is no need to implement it yourself.

A Solver should only be accessed from a single thread, except for the methods that are specifically documented in javadoc as being thread-safe. The solve() method hogs the current thread. This can cause HTTP timeouts for REST services and it requires extra code to solve multiple datasets in parallel. To avoid such issues, use a SolverManager instead.

4.2. Solving a problem

Solving a problem is quite easy once you have:

  • A Solver built from a solver configuration

  • A @planning_solution that represents the planning problem instance

Just provide the planning problem as argument to the solve() method and it will return the best solution found:

problem = ...
best_solution = solver.solve(problem)

For example in n queens, the solve() method will return an NQueens instance with every Queen assigned to a Row.

solvedNQueens04
Figure 2. Best Solution for the Four Queens Puzzle in 8ms (Also an Optimal Solution)

The solve(Solution) method can take a long time (depending on the problem size and the solver configuration). The Solver intelligently wades through the search space of possible solutions and remembers the best solution it encounters during solving. Depending on a number of factors (including problem size, how much time the Solver has, the solver configuration, …​), that best solution might or might not be an optimal solution.

The solution instance given to the method solve(solution) is changed by the Solver, but do not mistake it for the best solution.

The solution instance returned by the methods solve(solution) or getBestSolution() is most likely a planning clone of the instance given to the method solve(solution), which implies it is a different instance.

The solution instance given to the solve(Solution) method does not need to be uninitialized. It can be partially or fully initialized, which is often the case in repeated planning.

4.3. Environment mode: are there bugs in my code?

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

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

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
</solver>

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

These are the environment modes:

4.3.1. FULL_ASSERT

The FULL_ASSERT mode turns on all assertions (such as assert that the incremental score calculation is uncorrupted for each move) to fail-fast on a bug in a Move implementation, a constraint, the engine itself, …​

This mode is reproducible (see the reproducible mode). It is also intrusive because it calls the method calculateScore() more frequently than a non-assert mode.

The FULL_ASSERT mode is horribly slow (because it does not rely on incremental score calculation).

4.3.2. NON_INTRUSIVE_FULL_ASSERT

The NON_INTRUSIVE_FULL_ASSERT turns on several assertions to fail-fast on a bug in a Move implementation, a constraint, the engine itself, …​

This mode is reproducible (see the reproducible mode). It is non-intrusive because it does not call the method calculateScore() more frequently than a non assert mode.

The NON_INTRUSIVE_FULL_ASSERT mode is horribly slow (because it does not rely on incremental score calculation).

4.3.3. FAST_ASSERT

The FAST_ASSERT mode turns on most assertions (such as assert that an undoMove’s score is the same as before the Move) to fail-fast on a bug in a Move implementation, a constraint, the engine itself, …​

This mode is reproducible (see the reproducible mode). It is also intrusive because it calls the method calculateScore() more frequently than a non assert mode.

The FAST_ASSERT mode is slow.

It is recommended to write a test case that does a short run of your planning problem with the FAST_ASSERT mode on.

4.3.4. REPRODUCIBLE (default)

The reproducible mode is the default mode because it is recommended during development. In this mode, two runs in the same OptaPlanner version will execute the same code in the same order. Those two runs will have the same result at every step, except if the note below applies. This enables you to reproduce bugs consistently. It also allows you to benchmark certain refactorings (such as a score constraint performance optimization) fairly across runs.

Despite the reproducible mode, your application might still not be fully reproducible because of:

  • Use of set (or another Collection which has an inconsistent order between Python runs) for collections of planning entities or planning values (but not normal problem facts), especially in the solution implementation.

  • Combining a time gradient dependent algorithms (most notably Simulated Annealing) together with time spent termination. A sufficiently large difference in allocated CPU time will influence the time gradient values. Replace Simulated Annealing with Late Acceptance. Or instead, replace time spent termination with step count termination.

The reproducible mode can be slightly slower than the non-reproducible mode. If your production environment can benefit from reproducibility, use this mode in production.

In practice, this mode uses the default, fixed random seed if no seed is specified, and it also disables certain concurrency optimizations (such as work stealing).

4.3.5. NON_REPRODUCIBLE

The non-reproducible mode can be slightly faster than the reproducible mode. Avoid using it during development as it makes debugging and bug fixing painful. If your production environment doesn’t care about reproducibility, use this mode in production.

In practice, this mode uses no fixed random seed if no seed is specified.

4.4. Logging level: what is the Solver doing?

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

  • error: Log errors, except those that are thrown to the calling code as a RuntimeException.

    If an error happens, OptaPy normally fails fast. It does not log it as an error itself to avoid duplicate log messages. Meanwhile, the code is disrupted from doing further harm or obfuscating the error.

  • warn: Log suspicious circumstances.

  • info: Log every phase and the solver itself. See scope overview.

  • debug: Log every step of every phase. See scope overview.

  • trace: Log every move of every step of every phase. See scope overview.

Turning on trace logging, will slow down performance considerably: it is often four times slower. However, it is invaluable during development to discover a bottleneck.

Even debug logging can slow down performance considerably for fast stepping algorithms (such as Late Acceptance and Simulated Annealing), but not for slow stepping algorithms (such as Tabu Search).

Both cause congestion in multithreaded solving with most appenders, see below..

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

INFO  Solving started: time spent (3), best score (-4init/0), random (JDK with seed 0).
DEBUG     CH step (0), time spent (5), score (-3init/0), selected move count (1), picked move (Queen-2 {null -> Row-0}).
DEBUG     CH step (1), time spent (7), score (-2init/0), selected move count (3), picked move (Queen-1 {null -> Row-2}).
DEBUG     CH step (2), time spent (10), score (-1init/0), selected move count (4), picked move (Queen-3 {null -> Row-3}).
DEBUG     CH step (3), time spent (12), score (-1), selected move count (4), picked move (Queen-0 {null -> Row-1}).
INFO  Construction Heuristic phase (0) ended: time spent (12), best score (-1), score calculation speed (9000/sec), step total (4).
DEBUG     LS step (0), time spent (19), score (-1),     best score (-1), accepted/selected move count (12/12), picked move (Queen-1 {Row-2 -> Row-3}).
DEBUG     LS step (1), time spent (24), score (0), new best score (0), accepted/selected move count (9/12), picked move (Queen-3 {Row-3 -> Row-2}).
INFO  Local Search phase (1) ended: time spent (24), best score (0), score calculation speed (4000/sec), step total (2).
INFO  Solving ended: time spent (24), best score (0), score calculation speed (7000/sec), phase total (2), environment mode (REPRODUCIBLE).

All time spent values are in milliseconds.

Configure the logging level by explicitly calling logging.getLogger('optapy').setLevel(logging.LEVEL):

import logging

logging.getLogger('optapy').setLevel(logging.DEBUG)

By default, INFO logging is used.

4.5. Monitoring the solver

OptaPy currently does not support metric export.

4.6. Random number generator

Many heuristics and metaheuristics depend on a pseudorandom number generator for move selection, to resolve score ties, probability based move acceptance, …​ During solving, the same Random instance is reused to improve reproducibility, performance and uniform distribution of random values.

To change the random seed of that Random instance, specify a randomSeed:

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <randomSeed>0</randomSeed>
  ...
</solver>

To change the pseudorandom number generator implementation, specify a randomType:

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <randomType>MERSENNE_TWISTER</randomType>
  ...
</solver>

The following types are supported:

  • JDK (default): Standard implementation (java.util.Random).

  • MERSENNE_TWISTER: Implementation by Commons Math.

  • WELL512A, WELL1024A, WELL19937A, WELL19937C, WELL44497A and WELL44497B: Implementation by Commons Math.

For most use cases, the randomType has no significant impact on the average quality of the best solution on multiple datasets.

5. SolverManager

A SolverManager is a facade for one or more Solver instances to simplify solving planning problems in REST and other enterprise services. Unlike the Solver.solve(…​) method:

  • SolverManager.solve(…​) returns immediately: it schedules a problem for asynchronous solving without blocking the calling thread. This avoids timeout issues of HTTP and other technologies.

  • SolverManager.solve(…​) solves multiple planning problems of the same domain, in parallel.

Internally a SolverManager manages a thread pool of solver threads, which call Solver.solve(…​), and a thread pool of consumer threads, which handle best solution changed events.

Build a SolverManager instance with the solver_manager_create(…​) method:

from optapy import solver_manager_create, solver_config_create_from_xml_file
from optapy.types import Duration

solver_config = solver_config_create_from_xml_file("solverConfig.xml")
solver_manager = solver_manager_create(solver_config)

Each problem submitted to the SolverManager.solve(…​) methods needs a unique problem ID. Later calls to getSolverStatus(problemId) or terminateEarly(problemId) use that problem ID to distinguish between the planning problems. The problem ID must be an immutable class, such as int, str or uuid.

To retrieve the best solution, after solving terminates normally, use SolverJob.getFinalBestSolution():

import uuid

problem1 = ...
problem_id = uuid.uuid4()
# Returns immediately
solver_job = solver_manager.solve(problem_id, problem1)
...
solution1 = solver_job.getFinalBestSolution()

However, there are better approaches, both for solving batch problems before an end-user needs the solution as well as for live solving while an end-user is actively waiting for the solution, as explained below.

The current SolverManager implementation runs on a single computer node, but future work aims to distribute solver loads across a cloud.

5.1. Solve batch problems

At night, batch solving is a great approach to deliver solid plans by breakfast, because:

  • There are typically few or no problem changes in the middle of the night. Some organizations even enforce a deadline, for example, submit all day off requests before midnight.

  • The solvers can run for much longer, often hours, because nobody’s waiting for it and CPU resources are often cheaper.

To solve a multiple datasets in parallel (limited by parallelSolverCount), call solve(…​) for each dataset:

from optapy.types import SolverManager

class TimeTableService:
    solver_manager: SolverManager

    # Returns immediately, call it for every dataset
    def solve_batch(self, time_table_id: int):
        solver_manager.solve(time_table_id,
                # Called once, when solving starts
                lambda the_id: self.find_by_id(the_id),
                # Called once, when solving ends
                lambda solution: self.save(solution))

    def find_by_id(self, time_table_id: int) -> TimeTable:
        ...

    def save(self, time_table: TimeTable) -> None:
        ...

A solid plan delivered by breakfast is great, even if you need to react on problem changes during the day.

5.2. Solve and listen to show progress to the end-user

When a solver is running while an end-user is waiting for that solution, the user might need to wait for several minutes or hours before receiving a result. To assure the user that everything is going well, show progress by displaying the best solution and best score attained so far.

To handle intermediate best solutions, use solveAndListen(…​):

from optapy.types import SolverManager

class TimeTableService:
    solver_manager: SolverManager

    # Returns immediately
    def solve_live(self, time_table_id: int) -> None:
        solver_manager.solveAndListen(time_table_id,
                # Called once, when solving starts
                lambda the_id: self.find_by_id(time_table_id),
                # Called multiple times, for every best solution change
                lambda solution: self.save(solution))

    def find_by_id(self, time_table_id: int):
        ...

    def save(self, time_table: TimeTable) -> None:
        ...

    def stop_solving(self, time_table_id: int):
        solver_manager.terminateEarly(time_table_id)

This implementation is using the database to communicate with the UI, which polls the database. More advanced implementations push the best solutions directly to the UI or a messaging queue.

If the user is satisfied with the intermediate best solution and does not want to wait any longer for a better one, call SolverManager.terminateEarly(problemId).