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¶

You write	Meaning
`@problem_fact` class	Data the solver reads and never changes
`@planning_entity` class	Something the solver changes
`@planning_solution` class	The problem: lists of facts and entities, and a `score` field
`x: Annotated[T \\| None, PlanningVariable]`	The solver picks `x` from the solution's list of `T`
`PlanningVariable(allows_unassigned=True)`	`None` is an acceptable answer (over-constrained problems)
`xs: Annotated[list[E], PlanningListVariable]`	The solver orders entities `E` into lists (routes)
`InverseRelationShadow`, `PreviousElementShadow`, `NextElementShadow`, `IndexShadow`	On a list element: its list's owner, neighbours, position
`CascadingShadow(fn)`	On a list element: `fn(element, previous)`, recomputed along the list (arrival times)

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

Stream step	Meaning
`f.for_each(E)`	Every `E` whose variables are assigned
`f.for_each_including_unassigned(E)`	Every `E`
`f.for_each_unique_pair(E, *joiners)`	Every pair of `E`, once
`.filter(fn)`	Keep what `fn` holds for
`.join(E, *joiners)`	Pairs with an assigned `E` matching the joiners
`.if_exists(E, joiners)`, `.if_not_exists(E, joiners)`	Keep if a matching `E` exists / does not
`.group_by(key, ConstraintCollectors.count() / sum(f) / min(f) / max(f) / count_distinct(f))`	One `(key, value)` per key
`.group_by(key, key2, …, collector)`	Up to four keys: one `(key, key2, …, value)` per combination
`.complement(F)`	Add `(fact, 0)` for every `F` with no group
`.group_by(ConstraintCollectors.load_balance(scale=…))`	One result: the groups' unfairness × `scale`
`.flatten_last(fn)`	One `(entity, item)` per item of a list attribute

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.

Code	Meaning
`domain.invalid`	A domain class cannot be represented (an unsupported field type, a missing score field)
`lambda.untranslatable`	A constraint lambda uses something the compiler does not translate
`stream.unsupported`	A stream chain the engine does not run
`problem.invalid`	The problem is not valid data
`options.invalid`	The solve options are not valid data
`model.duplicate_name`	Two items of one kind share a name
`model.unknown_value_range`	A variable names a value range that does not exist
`model.unknown_element_type`	A list variable names an entity type that does not exist
`model.invalid_element_type`	A list variable holds a type it cannot hold
`model.list_and_basic_variables`	An entity type has a list variable and basic variables
`model.too_many_entity_types`	More entity types than supported
`model.too_many_entities`	More entities than supported
`model.value_range_too_long`	A value range longer than supported
`model.data_shape`	Instance data does not match the model's shape
`model.value_out_of_range`	An initial value outside its value range
`model.invalid_list_entry`	An initial list holds something it cannot
`model.shadows_on_unlisted_type`	Cascading shadows on a type no list holds
`constraint.duplicate_name`	Two constraints share a name
`constraint.unknown_source`	A constraint starts from an unknown type
`constraint.level_not_in_score`	A score level the score type does not have
`constraint.unsupported`	A stream shape the engine does not build
`constraint.negative_weight`	A `penalize` or `reward` weight was negative for a match (a penalty would have added to the score)
`expr.element_out_of_range`	An expression reads a tuple element that does not exist
`expr.arity`	An expression over too many or too few elements
`expr.unknown_entity_type`	An expression names an unknown entity type
`expr.unknown_field`	An expression names an unknown field
`expr.unknown_list`	An expression names an unknown list
`expr.unknown_fact`	An expression names an unknown fact table
`expr.unknown_list_fact`	An expression names an unknown list-fact table
`expr.empty_operands`	An `and` / `or` with nothing in it
`expr.too_many_slots`	A model too wide to address
`expr.too_long`	An expression too long to compile
`expr.compiler_defect`	A defect in Heusor's compiler — please report it
`expr.variable_in_shadow`	A cascading shadow reads a planning variable
`expr.shadow_not_yet_computed`	A cascading shadow reads itself or a later one
`config.invalid`	Contradictory options, or a refused configuration
`solve.failed`	The engine stopped with an error

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.