Metadata-Version: 2.4
Name: heusor
Version: 0.1.1
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Rust
Requires-Dist: pytest>=7 ; extra == 'test'
Provides-Extra: test
License-File: LICENSE
Summary: Heusor: a constraint solver for planning and scheduling, driven from Python.
Maintainer-email: Shiftmind Limited <licensing@heusor.com>
License-Expression: LicenseRef-Proprietary
Requires-Python: >=3.11
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM

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

```python
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_entity(exclusive_cell=("timeslot", "room"))` | No two entities may hold the same combination of those variables; the solver also moves an entity into a free combination. Not a constraint: keep the hard constraint that forbids sharing |
| `@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) |
| `DerivedShadow(fn)` | On an entity with planning variables: `fn(entity)`, recomputed when a variable it depends on changes — for example a task's start from the tasks it follows: `max((t.end for t in task.after), default=0) + task.delay.days` |

Field types: `int`, `bool`, `str`, `Enum`, `datetime`, `date`, `time`,
`timedelta`, a `@problem_fact` class, and `list` / `set` of those; and
`list[E]` of `@planning_entity` objects, such as the tasks a task follows. 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 |
| `.complement(F, padding, key_padding=(…))` | After several keys: add `(fact, key2, …, padding)` for every `F` that is the first key of no group, `key2`… from `key_padding` |
| `.group_by(ConstraintCollectors.load_balance(scale=…))` | One result: the groups' unfairness × `scale` |
| `.group_by(…).group_by(key, …, collector)` | Groups of the groups: each key and the collector's value take `(key, key2, …, value)` — for example how many employees work each number of shifts |
| `.flatten_last(fn)` | One `(entity, item)` per item of a list attribute |
| `.flatten_last(fn).group_by(key, …, collector)` | Groups of those pairs: each key and the collector's value take `(entity, item)` — for example a crew's jobs at each time grain |
| `.join(E, …).group_by(key, …, collector)` | Groups of the pairs: each key and the collector's value take `(a, b)` |
| `.join(E, …).flatten_last(fn)` | One `(a, b, item)` per item of `fn(b)`, a list attribute of the joined entity |
| `.join(E, …).join(F, *joiners)` | Triples `(a, b, c)` with an assigned `F` matching the joiners; each joiner takes a function of `(a, b)`, then one of `c` |
| `.join(…).join(…).join(G, *joiners)` | Quadruples `(a, b, c, d)`, each joiner a function of `(a, b, c)`, then one of `d` |
| `.group_by(key, ConstraintCollectors.average(f, scale=1))` | The mean of `f` × `scale`, rounded half away from zero |
| `.group_by(key, ConstraintCollectors.to_list(f))` | Every `f` of the group, ascending, with repeats |
| `.group_by(key, ConstraintCollectors.to_consecutive_sequences(index))` | The runs of consecutive `index` values (an int or a date) |
| `.group_by(…, to_list(f)).flatten_last(lambda key, values: values)` | One `(key, value)` per value |
| `.group_by(…, to_consecutive_sequences(i)).flatten_last(lambda key, chain: chain.sequences)` | One `(key, sequence)` per run; `chain.breaks` gives one `(key, break)` per gap |

Existence checks go before a join. After a three- or four-way join,
`filter`, `group_by`, `penalize` and `reward` take the tuple's entities; a
match blames each of them. After a join, `flatten_last`, `group_by`,
`complement` and `load_balance` work as they do on single entities; so do
`complement` and `load_balance` after `flatten_last(…).group_by(…)`. Lambdas
after a `flatten_last` — its filters, keys, collector values and weight —
read the entity as it is, its planning variables too.

Collectors whose result is a list. A `to_list` group's values are read with
`len(values)`, `x in values` and `values[i]` (`None` past the end). In
`to_consecutive_sequences`, two members share a sequence when their indices
differ by at most one, so two shifts on one day are one sequence member each.
A chain is read with `len(chain.sequences)` and `len(chain.breaks)`. After
`flatten_last`, a sequence has `first_index`, `last_index`, `length`
(`last_index − first_index + 1`), `count` (members), `is_first` and
`is_last`; a break has `previous_index` (the earlier sequence's last),
`next_index` (the later one's first), `length` (`next_index −
previous_index`), `is_first` and `is_last`. With a date index, the indices
are dates and the lengths are days. For example, more than five days in a
row:

```python
def too_many_days_in_a_row(f):
    return f.for_each(Shift) \
        .group_by(lambda s: s.employee,
                  ConstraintCollectors.to_consecutive_sequences(lambda s: s.day)) \
        .flatten_last(lambda employee, chain: chain.sequences) \
        .filter(lambda employee, seq: seq.length > 5) \
        .penalize(HardSoftScore.ONE_SOFT, lambda employee, seq: seq.length - 5) \
        .as_constraint("Too many days in a row")
```

A `complement` after one of these adds the empty list, so it takes no
padding; `load_balance` balances the groups of a number collector only.

`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]`) — another entity's list attributes too,
  through a shadow (`stop.previous.times[stop.node]`, `len(…)`, `in`), but not
  its list variable;
- `+ - * // %`, 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)`;
- `max((x.f for x in entity.items), default=k)` and `min(…)` over a list
  variable or a `list` of entities, skipping values that are `None` — in a
  `DerivedShadow`, over the entities it depends on;
- 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

```text
heusor.solve(solution, constraints, *, time_limit=None, step_limit=None,
             seed=None, config=None, cancel=None, on_progress=None,
             weights=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=`.
- `weights={"Late": HardSoftScore.of_soft(5)}` overrides constraint weights
  by name, as data — one set of constraints for every customer's settings.
  The weight's non-zero level replaces the constraint's, and each match's
  weight is multiplied by it; a zero score (`HardSoftScore(0, 0)`) disables
  the constraint. `heusor.score(…, weights=…)` takes the same.

## Explaining a score

```text
explanation = heusor.score(solution, constraints)   # weights=… as for solve
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.invalid_exclusive_cell` | An `exclusive_cell` names something that is not a planning variable of its class, names one twice, or is declared where another class has planning variables too |
| `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` | Shadows on a type no list holds and with no basic variables |
| `model.invalid_dependency` | A derived shadow's list holds an entity of another type |
| `model.dependency_cycle` | Derived shadows' dependencies form a cycle |
| `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.weight_override` | A weight override names no constraint, or is not one non-negative level |
| `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 |
| `expr.out_of_reach` | An expression reads something its place in the stream cannot see (e.g. another entity's planning variable in a group key) |
| `config.invalid` | Contradictory options, or a refused configuration |
| `config.unknown_variable` | A configured move names a planning variable no entity type has, or one two types have at different positions |
| `config.unknown_field` | A configured group move names a field that the listed classes do not all have |
| `solve.failed` | The engine stopped with an error |
| `score.overflow` | A score, or one constraint's share, past the 64-bit integer range |

## 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`, `average`, `to_list`, `to_consecutive_sequences` and
  `load_balance`. A `group_by` after a `to_list`, `to_consecutive_sequences`
  or `load_balance` group-by. Joins of up to four streams; `flatten_last`
  after a three- or four-way join is not supported yet. An existence check
  after a join is not supported yet. A flattened sequence offers its indices,
  length and count, not its members.
- 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`. A stream starts from a
  `@planning_entity` class; `for_each`, `for_each_unique_pair`, `join` and
  existence checks on a problem-fact class are refused.
- A lambda cannot call a method of your classes (`visit.total_demand()`);
  write the expression in the lambda, or call a module-level helper whose
  body is a single `return <expression>` — no local names, no `if`
  statements, no loops. Not compiled either: dict lookups, `date.isocalendar()`
  (group by the week's Monday, `d - timedelta(days=d.weekday())`), float
  arithmetic (`/`, `1.3`), `any()` / `all()` and comprehensions other than
  `sum(x.f for x in e.list_variable)`.
- An entity is not a value: compare two entities by an attribute
  (`a.id != b.id`), and group or collect by one (`task.id`). `is`, `is not`
  and `!=` between two entities are refused — the error for `!=` suggests
  `is`, which is refused too. Facts compare with `==` / `!=`; `is` / `is not`
  only against `None`.
- No `expand`, `map`, `distinct`, `concat` or `flatten` (use `flatten_last`),
  and no `containing`, `contained_in`, `containing_any_of` or `filtering`
  joiners: flatten the list and filter with `in`, or precompute a count per
  pair when the problem is built. A join takes one ordering joiner, and not
  together with `overlapping`. A `group_by` takes at least one key.
- `PlanningListVariable` takes no `allows_unassigned`: list elements may stay
  unassigned without it.
- 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.

