Skip to content

Christopher-Chianelli/timefold-solver-python

 
 

Repository files navigation

Timefold Logo

Timefold Solver for Python

PyPI License JVM support Python support Commit Activity

Stackoverflow GitHub Discussions GitHub Issues

Reliability Rating Security Rating Maintainability Rating Coverage

Timefold Solver is an AI constraint solver for Python to optimize the Vehicle Routing Problem, Employee Rostering, Maintenance Scheduling, Task Assignment, School Timetabling, Cloud Optimization, Conference Scheduling, Job Shop Scheduling, Bin Packing and many more planning problems.

Using Timefold Solver in Python is significantly slower than using Timefold Solver in Java or Kotlin.

Get started with Timefold Solver for Python

Requirements

Build from source

  1. Build the main branch of Timefold Solver for Java from source
  2. Install the repo
    $ pip install git+https://github.com/TimefoldAI/timefold-solver-python.git

Source code overview

Domain

In Timefold Solver, the domain has three parts:

  • Problem Facts, which do not change.
  • Planning Entities, which have one or more planning variables.
  • Planning Solution, which define the facts and entities of the problem.

Problem Facts

Problem facts can be any Python class, which are used to describe unchanging facts in your problem:

from dataclasses import dataclass
from datetime import time

@dataclass
class Timeslot:
    id: int
    day_of_week: str
    start_time: time
    end_time: time

Planning Entities

To declare Planning Entities, use the @planning_entity decorator along with annotations:

from dataclasses import dataclass, field
from typing import Annotated
from timefold.solver.domain import planning_entity, PlanningId, PlanningVariable

@planning_entity
@dataclass
class Lesson:
    id: Annotated[int, PlanningId]
    subject: str
    teacher: str
    student_group: str
    timeslot: Annotated[Timeslot, PlanningVariable] = field(default=None)
    room: Annotated[Room, PlanningVariable] = field(default=None)
  • The PlanningVariable annotation is used to mark what fields the solver is allowed to change.

  • The PlanningId annotation is used to uniquely identify an entity object of a particular class. The same Planning Id can be used on entities of different classes, but the ids of all entities in the same class must be different.

Planning Solution

To declare the Planning Solution, use the @planning_solution decorator:

from dataclasses import dataclass, field
from typing import Annotated
from timefold.solver.domain import (planning_solution, ProblemFactCollectionProperty, ValueRangeProvider,
                                    PlanningEntityCollectionProperty, PlanningScore)
from timefold.solver.score import HardSoftScore

@planning_solution
@dataclass
class TimeTable:
    timeslots: Annotated[list[Timeslot], ProblemFactCollectionProperty, ValueRangeProvider]
    rooms: Annotated[list[Room], ProblemFactCollectionProperty, ValueRangeProvider]
    lessons: Annotated[list[Lesson], PlanningEntityCollectionProperty]
    score: Annotated[HardSoftScore, PlanningScore] = field(default=None)
  • The ValueRangeProvider annotation is used to denote a field that contains possible planning values for a PlanningVariable.

  • TheProblemFactCollection annotation is used to denote a field that contains problem facts. This allows these facts to be queried in your constraints.

  • The PlanningEntityCollection annotation is used to denote a field that contains planning entities. The planning variables of these entities will be modified during solving.

  • The PlanningScore annotation is used to denote the field that holds the score of the current solution. The solver will set this field during solving.

Constraints

You define your constraints by using the ConstraintFactory:

from domain import Lesson
from timefold.solver.score import (Joiners, HardSoftScore, ConstraintFactory,
                                   Constraint, constraint_provider)

@constraint_provider
def define_constraints(constraint_factory: ConstraintFactory) -> list[Constraint]:
    return [
        # Hard constraints
        room_conflict(constraint_factory),
        # Other constraints here...
    ]

def room_conflict(constraint_factory: ConstraintFactory) -> Constraint:
    # A room can accommodate at most one lesson at the same time.
    return (
        constraint_factory.for_each_unique_pair(Lesson,
                # ... in the same timeslot ...
                Joiners.equal(lambda lesson: lesson.timeslot),
                # ... in the same room ...
                Joiners.equal(lambda lesson: lesson.room))
            .penalize(HardSoftScore.ONE_HARD)
            .as_constraint("Room conflict")
    )

for more details on Constraint Streams, see https://timefold.ai/docs/timefold-solver/latest/constraints-and-score/score-calculation.

Solve

from timefold.solver import SolverFactory
from timefold.solver.config import SolverConfig, TerminationConfig, ScoreDirectorFactoryConfig, Duration
from constraints import define_constraints
from domain import TimeTable, Lesson, generate_problem

solver_config = SolverConfig(
    solution_class=TimeTable,
    entity_class_list=[Lesson],
    score_director_factory_config=ScoreDirectorFactoryConfig(
        constraint_provider_function=define_constraints
    ),
    termination_config=TerminationConfig(
        spent_limit=Duration(seconds=30)
    )
)

solver = SolverFactory.create(solver_config).build_solver()
solution = solver.solve(generate_problem())

solution will be a TimeTable instance with planning variables set to the final best solution found.

More information

For a full API spec, visit the Timefold Documentation.

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Java 63.9%
  • Python 36.1%