Metadata-Version: 2.4
Name: heusor
Version: 0.1.0
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_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

```text
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

```text
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.

