Heusor for Python

Heusor is a constraint solver for planning and scheduling problems: school timetables, staff rosters, vehicle routes. You describe the problem with ordinary Python classes and the rules with constraint streams; Heusor searches for the assignment with the best score.

Your lambdas are read from their source and compiled once, when the problem is built. Nothing in Python runs while the solver searches, so a solve runs at engine speed.

Python 3.11 or newer.

Quickstart

A school timetable: lessons need a timeslot and a room, and a teacher cannot teach two lessons at once.

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

import heusor
from heusor import (
    ConstraintFactory, HardSoftScore, Joiners, PlanningVariable,
    constraint_provider, planning_entity, planning_solution, problem_fact,
)


@problem_fact
@dataclass
class Timeslot:
    day: str
    start: time


@problem_fact
@dataclass
class Room:
    name: str


@planning_entity
@dataclass
class Lesson:
    subject: str
    teacher: str
    timeslot: Annotated[Timeslot | None, PlanningVariable] = None
    room: Annotated[Room | None, PlanningVariable] = None


@planning_solution
@dataclass
class Timetable:
    timeslots: list[Timeslot]
    rooms: list[Room]
    lessons: list[Lesson]
    score: HardSoftScore | None = None


@constraint_provider
def constraints(f: ConstraintFactory):
    return [
        f.for_each_unique_pair(Lesson,
                               Joiners.equal(lambda l: l.timeslot),
                               Joiners.equal(lambda l: l.room))
         .penalize(HardSoftScore.ONE_HARD)
         .as_constraint("Room conflict"),
        f.for_each_unique_pair(Lesson,
                               Joiners.equal(lambda l: l.timeslot),
                               Joiners.equal(lambda l: l.teacher))
         .penalize(HardSoftScore.ONE_HARD)
         .as_constraint("Teacher conflict"),
    ]


problem = Timetable(
    timeslots=[Timeslot("MONDAY", time(8, 30)), Timeslot("MONDAY", time(9, 30))],
    rooms=[Room("A"), Room("B")],
    lessons=[Lesson("Math", "Turing"), Lesson("Physics", "Curie"),
             Lesson("Chemistry", "Curie"), Lesson("Biology", "Darwin")],
)

solved = heusor.solve(problem, constraints, time_limit=2)
print(solved.score)                       # HardSoftScore(hard=0, soft=0)
for lesson in solved.lessons:
    print(lesson.subject, lesson.timeslot.start, lesson.room.name)

solve returns a solved copy; problem is not changed.

The domain

Field types: int, bool, str, Enum, datetime, date, time, timedelta, a @problem_fact class, and list / set of those. Use integers, not float: scale a quantity (cents, minutes) and declare it int.

Score types: SimpleScore, HardSoftScore, HardMediumSoftScore. A constraint's unit is one level, scaled if you like: HardSoftScore.ONE_HARD, HardSoftScore.of_soft(1000).

Constraints

A @constraint_provider function returns streams, each ending in .penalize(unit, weight) or .reward(unit, weight) and .as_constraint(name).

Joiners: equal, less_than, less_than_or_equal, greater_than, greater_than_or_equal, overlapping(start, end) (half-open). Each takes one function for both sides, or one per side.

What a lambda may use

• attributes of its arguments — through a planning variable into a fact (lesson.timeslot.day), through a shadow into another entity (visit.previous.location), and items of a list by position (location.times[other.id]);
• + - * // %, comparisons (chained too), and, or, not, x if c else y, is None, in a list attribute or a constant tuple;
• abs, min, max, len, sum(x.f for x in entity.list_variable);
• dates and times with Python's own meaning: datetime - datetime is a timedelta, .date(), .weekday(), .hour, .total_seconds(), datetime.combine(d, t), timedelta(minutes=x);
• anything that does not mention an argument — a constant, a closure value, timedelta(minutes=30), an enum member — evaluated once, when building;
• calls to your own one-expression functions.

Anything else fails when the constraints are built, never during a solve, with the file, the line and the reason. Where Python and the engine would disagree, Heusor refuses instead of guessing: / (it gives a float — use //), time - time (Python raises — use datetime.combine), and the truth of a str, an enum or a time (compare explicitly).

Solving

heusor.solve(solution, constraints, *, time_limit=None, step_limit=None,
             seed=None, config=None, cancel=None, on_progress=None)

• time_limit (seconds, construction included) or step_limit; neither means 10 seconds. step_limit with a seed is reproducible.
• cancel=heusor.Cancel(): call cancel.cancel() from another thread to stop early with the best solution so far. The solve releases the interpreter lock.
• on_progress=fn receives progress reports (kind, step, best, elapsed_ms); if it raises, the solve stops and the exception propagates.
• heusor.config_for(solution, constraints, …) returns the exact solver configuration a solve would use; change it and pass it back as config=.

Explaining a score

explanation = heusor.score(solution, constraints)
explanation.score                 # the total
explanation.constraints           # {name: score}
explanation.indictments[name]     # [Indictment(entity, matches, score), ...]
explanation.blame(entity)         # what that object's matches cost, in total

An indictment names your own objects. A pair charges both of its members and a group every member, so indictments show who is involved; they do not add up to the score.

Errors

Every error is a heusor.HeusorError with a stable code. Messages may be reworded between versions; codes will not.

Licence

Heusor is proprietary software by Shiftmind Limited, free to use, including commercially; it may not be reverse engineered, modified or redistributed on its own. The full terms are in the package's LICENSE, and the notices for the third-party components it includes are in heusor/THIRD_PARTY_LICENSES.txt. Questions: licensing@heusor.com.

Current limits

• Up to four keys per group_by; collectors count, sum, min, max, count_distinct and load_balance; complement on a single-key group_by only. Joins of two streams (no three-way joins). A group_by after a group_by (except load_balance), or a group_by or flatten_last after a join, is not supported yet.
• A penalize or reward weight must not be negative: a match that gets one stops the solve with constraint.negative_weight.
• A join to a problem fact is written as an attribute read: shift.employee.skills, not a join with Employee.
• Lambdas must be defined in a file (their source is read).
• Wheels for Linux x86-64 (glibc 2.17 or newer), macOS on Apple silicon (arm64) and Windows x86-64, for Python 3.11 and newer. Not built yet: Linux on ARM (aarch64) and macOS on Intel.