0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@SaitoTsutomu(Tsutomu Saito)

Timefold Solver入門: Pythonで制約充足問題を解く

0
Last updated at Posted at 2026-06-16

Timefold Solverは、制約充足問題（Constraint Satisfaction Problem, CSP）のソルバーです（Apache 2.0ライセンス）。

本記事ではPythonでの使い方を紹介します。

利用例

  • シフト作成
  • 時間割作成
  • 配送ルート最適化
  • 生産計画
  • 作業員割当

動作確認環境

  • macOS 26.5.1
  • Python 3.12.13
  • timefold 1.24.0b0
  • OpenJDK 25

JDKのインストール

Java製なのでJDKが必要です。
ここではmacOSでのインストール方法を紹介します。
以下のようにしてインストールしてください（2026年6月現在、JDK 21以上推奨）。

brew install openjdk@25

sudo ln -sfn \
  /opt/homebrew/opt/openjdk@25/libexec/openjdk.jdk \
  /Library/Java/JavaVirtualMachines/openjdk-25.jdk

# Java 22以降でTimefoldがネイティブメモリに高速アクセスするための警告/エラー抑止設定
echo 'export JAVA_TOOL_OPTIONS="--enable-native-access=ALL-UNNAMED"' >> ~/.zshrc\nsource ~/.zshrc

時間割のサンプルを使った解説

Pythonのラッパーであるtimefoldを使います。下記の時間割のサンプルを動かしてみましょう。

本記事ではTimefoldの基本構造を説明するため、「同じ教室の重複利用禁止」のみ実装します。

実際の時間割問題では以下のような制約も必要です。

  • 同じ教師の重複禁止
  • 同じ学生グループの重複禁止
  • 教師ごとの希望時間
  • 教室収容人数

環境構築

2026年6月現在、timefoldはPython 3.12まで対応していますので、Python 3.12で環境構築します。

uv init timefold-sample -p 3.12
cd timefold-sample
uv add timefold

main.pyを以下の内容で置き換えてください。

from dataclasses import dataclass
from datetime import time
from typing import Annotated

from timefold.solver import SolverFactory
from timefold.solver.config import (
    Duration,
    ScoreDirectorFactoryConfig,
    SolverConfig,
    TerminationConfig,
)
from timefold.solver.domain import (
    PlanningEntityCollectionProperty,
    PlanningId,
    PlanningScore,
    PlanningVariable,
    ProblemFactCollectionProperty,
    ValueRangeProvider,
    planning_entity,
    planning_solution,
)
from timefold.solver.score import (
    Constraint,
    ConstraintFactory,
    HardSoftScore,
    Joiners,
    constraint_provider,
)

構成要素（domain）

Timefold Solverの主な構成要素は以下のようなものです。

  • 入力データ（problem facts）: Solverが変更しないデータ
  • 決定変数（planning variables）: Solverが値を決定する属性
  • 決定対象（planning entities）: 入力データと決定変数を持つ対象
  • 解（planning solution）: 問題全体を表すオブジェクト（入力データ・割当結果・スコア）
  • 制約条件（constraints）: 解を評価するルール
  • スコア（score）: 解の良さを表す値

入力データ（problem facts）

扱いやすいように入力データのクラスを作成しましょう。

  • インスタンス識別にはPlanningIdを指定します
  • 同一クラス内で一意であればよく、別クラスとの重複は問題ありません

※ main.pyに以下を追加してください（以降も同様）。

@dataclass
class Room:
    """教室"""

    name: Annotated[str, PlanningId]


@dataclass
class Timeslot:
    """時間枠"""

    id: Annotated[int, PlanningId]
    day_of_week: str
    start_time: time
    end_time: time

決定変数（planning variables）と決定対象（planning entities）

  • 決定対象は、problem factsとplanning variablesを持つクラスです
  • 決定対象には@planning_entityを指定します
  • 値を決定する属性にはPlanningVariableを指定します。Timefoldでは値候補をオブジェクトとして管理するため、属性の型に（intなどの）プリミティブは使えません
@planning_entity
@dataclass
class Lesson:
    """割当"""

    id: Annotated[int, PlanningId]
    subject: str
    teacher: str
    student_group: str
    timeslot: Annotated[Timeslot | None, PlanningVariable] = None
    room: Annotated[Room | None, PlanningVariable] = None

決定変数の初期値（None）について

LessonクラスのtimeslotとroomにNoneを指定しているのは、「初期状態ではすべての授業がどの時間枠・どの教室にも割り当てられていない」という状態をソルバーに伝えるためです。

Timefold Solverは、この「未割り当て（None）」の状態からスタートし、以下のプロセスで最適解を導き出します。

  • 探索: 未割り当てのLessonに対して、利用可能なTimeslotやRoomをアルゴリズムに基づいて割り当てます
  • 評価: define_constraintsで定義したルールに基づき、その割り当てのスコアを計算します
  • 改善: スコアが最大化（制約違反が最小化）されるような組み合わせが見つかるまで、変数の値を入れ替える試行を高速に繰り返します

解（planning solution）

  • 解のクラスには@planning_solutionを指定します
  • ValueRangeProviderは、Lesson.timeslotやLesson.roomの候補リストをSolverへ渡すために使用します
  • ProblemFactCollectionPropertyを付けたデータは、problem factsとしてSolverに渡されます
  • PlanningEntityCollectionPropertyは、決定対象の一覧を表します

※ PlanningScoreについては後述します。

@planning_solution
@dataclass
class TimeTable:
    """時間割"""

    timeslots: Annotated[  # Lesson.timeslotの候補リスト
        list[Timeslot], ProblemFactCollectionProperty, ValueRangeProvider
    ]
    rooms: Annotated[  # Lesson.roomの候補リスト
        list[Room], ProblemFactCollectionProperty, ValueRangeProvider
    ]
    lessons: Annotated[list[Lesson], PlanningEntityCollectionProperty]
    score: Annotated[HardSoftScore | None, PlanningScore] = None

制約条件（constraints）

制約条件は@constraint_providerとConstraintFactoryを使って作成します。

Timefold Solverは、下記のような制約条件の書き方に特徴があります。
このような書き方を制約ストリームといいます。宣言的な記述方法で増分評価（変更箇所だけ再計算）ができるようになっています。

詳しくは、Timefold Solver Documentation on Constraint Streamsを参考にしてください。

@constraint_provider
def define_constraints(factory: ConstraintFactory) -> list[Constraint]:
    """制約条件定義"""
    return [room_conflict(factory)]


def room_conflict(factory: ConstraintFactory) -> Constraint:
    """教室は同時に1つまで割当可"""
    return (
        # 異なる2つのLessonごとに
        factory.for_each_unique_pair(
            Lesson,
            # timeslotが同じものを絞り込み
            Joiners.equal(lambda lesson: lesson.timeslot),
            # さらにroomが同じものを絞り込み
            Joiners.equal(lambda lesson: lesson.room),
        )
        # Hardスコアをマイナス1
        .penalize(HardSoftScore.ONE_HARD)
        # ログ出力用に名前付け
        .as_constraint("Room conflict")
    )

スコア（score）

  • スコアは、制約条件の評価結果として計算されます
  • Solverはスコアがもっとも良くなる解を探索します（大きいほど良い）
  • HardSoftScore（ハード制約とソフト制約がある場合）、HardMediumSoftScoreなどがあります
  • PlanningScoreを付けた属性に保持されます

求解

solver.solve()の戻り値は、最適化結果が反映されたTimeTableです。

def generate_problem() -> TimeTable:
    """問題作成"""
    timeslots = [
        Timeslot(
            id=1,
            day_of_week="MONDAY",
            start_time=time(9, 0),
            end_time=time(10, 0),
        ),
        Timeslot(
            id=2,
            day_of_week="MONDAY",
            start_time=time(10, 0),
            end_time=time(11, 0),
        ),
    ]
    rooms = [Room("Room A"), Room("Room B")]
    lessons = [
        Lesson(id=1, subject="Math", teacher="T1", student_group="G1"),
        Lesson(id=2, subject="English", teacher="T2", student_group="G1"),
        Lesson(id=3, subject="Physics", teacher="T1", student_group="G2"),
    ]
    return TimeTable(timeslots=timeslots, rooms=rooms, lessons=lessons)


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=1)),
)

solver = SolverFactory.create(solver_config).build_solver()
solution = solver.solve(generate_problem())
print(solution.score)
for lesson in solution.lessons:
    print(
        lesson.subject,
        lesson.teacher,
        lesson.timeslot.day_of_week,
        lesson.timeslot.start_time,
        lesson.room.name,
    )
サンプルコード全体 
from dataclasses import dataclass
from datetime import time
from typing import Annotated

from timefold.solver import SolverFactory
from timefold.solver.config import (
    Duration,
    ScoreDirectorFactoryConfig,
    SolverConfig,
    TerminationConfig,
)
from timefold.solver.domain import (
    PlanningEntityCollectionProperty,
    PlanningId,
    PlanningScore,
    PlanningVariable,
    ProblemFactCollectionProperty,
    ValueRangeProvider,
    planning_entity,
    planning_solution,
)
from timefold.solver.score import (
    Constraint,
    ConstraintFactory,
    HardSoftScore,
    Joiners,
    constraint_provider,
)


@dataclass
class Room:
    """教室"""

    name: Annotated[str, PlanningId]


@dataclass
class Timeslot:
    """時間枠"""

    id: Annotated[int, PlanningId]
    day_of_week: str
    start_time: time
    end_time: time


@planning_entity
@dataclass
class Lesson:
    """割当"""

    id: Annotated[int, PlanningId]
    subject: str
    teacher: str
    student_group: str
    timeslot: Annotated[Timeslot | None, PlanningVariable] = None
    room: Annotated[Room | None, PlanningVariable] = None


@planning_solution
@dataclass
class TimeTable:
    """時間割"""

    timeslots: Annotated[  # Lesson.timeslotの候補リスト
        list[Timeslot], ProblemFactCollectionProperty, ValueRangeProvider
    ]
    rooms: Annotated[  # Lesson.roomの候補リスト
        list[Room], ProblemFactCollectionProperty, ValueRangeProvider
    ]
    lessons: Annotated[list[Lesson], PlanningEntityCollectionProperty]
    score: Annotated[HardSoftScore | None, PlanningScore] = None


@constraint_provider
def define_constraints(factory: ConstraintFactory) -> list[Constraint]:
    """制約条件定義"""
    return [room_conflict(factory)]


def room_conflict(factory: ConstraintFactory) -> Constraint:
    """教室は同時に1つまで割当可"""
    return (
        # 異なる2つのLessonごとに
        factory.for_each_unique_pair(
            Lesson,
            # timeslotが同じものを絞り込み
            Joiners.equal(lambda lesson: lesson.timeslot),
            # さらにroomが同じものを絞り込み
            Joiners.equal(lambda lesson: lesson.room),
        )
        # Hardスコアをマイナス1
        .penalize(HardSoftScore.ONE_HARD)
        # ログ出力用に名前付け
        .as_constraint("Room conflict")
    )


def generate_problem() -> TimeTable:
    """問題作成"""
    timeslots = [
        Timeslot(
            id=1,
            day_of_week="MONDAY",
            start_time=time(9, 0),
            end_time=time(10, 0),
        ),
        Timeslot(
            id=2,
            day_of_week="MONDAY",
            start_time=time(10, 0),
            end_time=time(11, 0),
        ),
    ]
    rooms = [Room("Room A"), Room("Room B")]
    lessons = [
        Lesson(id=1, subject="Math", teacher="T1", student_group="G1"),
        Lesson(id=2, subject="English", teacher="T2", student_group="G1"),
        Lesson(id=3, subject="Physics", teacher="T1", student_group="G2"),
    ]
    return TimeTable(timeslots=timeslots, rooms=rooms, lessons=lessons)


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=1)),
)

solver = SolverFactory.create(solver_config).build_solver()
solution = solver.solve(generate_problem())
print(solution.score)
for lesson in solution.lessons:
    print(
        lesson.subject,
        lesson.teacher,
        lesson.timeslot.day_of_week,
        lesson.timeslot.start_time,
        lesson.room.name,
    )

実行

以下のように実行してください。

uv run main.py

以下のように出力されます。最初の行は環境変数の通知ですが無視して構いません。

Picked up JAVA_TOOL_OPTIONS: --enable-native-access=ALL-UNNAMED
0hard/0soft
Math T1 MONDAY 09:00:00 Room A
English T2 MONDAY 10:00:00 Room A
Physics T1 MONDAY 09:00:00 Room B

以上

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?