Extending¶
DispatchAtlas finds solvers and benchmark families in registries, and objectives in a registry of their own. A new solver or family can live in your own code, registered by a call, or in a separate package that DispatchAtlas discovers through an entry point, so that the command line and campaign files can use it by id like a built-in one.
A solver¶
A solver is a class with a class-level info: SolverInfo and a method
solve(problem, stop, seed). The repository's
examples/plugin/
directory holds a complete, installable plugin with one solver, a descent by
random insertion moves that restarts when it stops improving:
"""An example solver plugin for DispatchAtlas: insertion descent with restarts.
Installing this package makes the solver ``insertion-descent`` available
wherever DispatchAtlas looks solvers up: ``dispatchatlas solvers list``,
:func:`dispatchatlas.solvers.solve`, and campaign files. The package declares
one entry point in its ``pyproject.toml``::
[project.entry-points."dispatchatlas.solvers"]
example = "dispatchatlas_example_plugin:register"
Install it next to DispatchAtlas and use it by id. From the root of a clone
of the repository::
uv run --with . --with ./examples/plugin dispatchatlas solvers show insertion-descent
uv run --with . --with ./examples/plugin dispatchatlas solve problem.json \
--solver insertion-descent --max-evaluations 5000
The solver follows the contract of the built-in ones. Its parameters are
dataclass fields checked in ``__post_init__``, its metadata is a class-level
:class:`~dispatchatlas.core.SolverInfo`, and its loop runs inside a
:class:`~dispatchatlas.solvers.Search`, which makes it honour every stop
criterion, count evaluations exactly, and draw randomness only from the seed.
"""
from __future__ import annotations
from dataclasses import dataclass
from typing import ClassVar
from dispatchatlas.core import Problem, SolveResult, SolverInfo, StopCriteria
from dispatchatlas.solvers import Search, SolverRegistry
from dispatchatlas.solvers.operators import random_insert, random_topological_order
__all__ = ["InsertionDescent", "register"]
@dataclass(frozen=True)
class InsertionDescent:
"""Improve one task order by random insertion moves, restarting when stuck.
Each iteration moves one task of the current order to another position and
keeps the new order when its schedule scores no worse. After
``restart_after`` rejected moves in a row, the walk restarts from a new
random precedence-feasible order. The best schedule over all restarts is
returned.
Attributes:
restart_after: Consecutive rejected moves after which the walk
restarts.
"""
restart_after: int = 100
info: ClassVar[SolverInfo] = SolverInfo(
id="insertion-descent",
name="Insertion descent with restarts",
family="local-search",
summary=(
"Moves one task of the current order to a random position, keeps the move when "
"the schedule scores no worse, and restarts from a random order after a run of "
"rejected moves."
),
references=("kolisch1996serial",),
)
def __post_init__(self) -> None:
value = self.restart_after
if isinstance(value, bool) or not isinstance(value, int) or value < 1:
raise ValueError(f"restart_after must be a positive integer, got {value!r}")
def solve(self, problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult:
"""Run the descent within ``stop`` using randomness derived from ``seed``."""
search = Search(problem, stop, seed, self.info)
with search:
order = random_topological_order(problem, search.rng)
score = search.evaluate(order)
rejected = 0
while True:
search.next_iteration()
if rejected >= self.restart_after:
order = random_topological_order(problem, search.rng)
score = search.evaluate(order)
rejected = 0
continue
candidate = random_insert(order, search.rng)
candidate_score = search.evaluate(candidate)
if candidate_score <= score:
order, score, rejected = candidate, candidate_score, 0
else:
rejected += 1
return search.result()
def register(registry: SolverRegistry) -> None:
"""Add the plugin's solvers to ``registry``; DispatchAtlas calls it on discovery."""
registry.register(InsertionDescent)
The pieces, in the order a reader meets them:
- Parameters are dataclass fields with defaults.
__post_init__rejects invalid values withValueError, which the registry reports as aConfigErrornaming the solver. The registry reads the parameters and their defaults from the fields. - Metadata:
idis kebab case and unique;familyis one of the standard families, or a kebab-case family of your own;summarystates the mechanism in one sentence;referencesholds bibliography keys, DOIs, or URLs.stochastic,iterative, andmulti_objectivedefault to true, true, and false.supportslists the problem features the solver models correctly, every feature by default, since the shared schedule builder handles them all; campaigns never pair the solver with a problem that has another.requiresnames the extras the solver needs. - The search.
Search(problem, stop, seed, info)checks the problem's features and the stop criteria, owns the random generatorsearch.rng, and keeps the best schedule. Insidewith search:,search.next_iteration()starts each iteration andsearch.evaluate(order)decodes and scores each candidate; either raises when a stop criterion fires, and leaving thewithblock ends the run there.search.result()builds the result, with exact counts and the trace. A solver written this way honours every stop criterion without code of its own.
A candidate is a task order, which the builder repairs to respect the
dependencies, and optionally a mode for each task; modes=None lets the
builder give each task its earliest-finishing mode. The building blocks are
documented in the solver framework:
dispatchatlas.solvers.operators holds moves and crossovers on orders and
modes, dispatchatlas.solvers.encoding maps real vectors to orders and modes
for methods that search vectors, and Search.submit scores a schedule that a
constructive heuristic built task by task with the builder of
search.evaluator.decoder.
A solver that does not search over orders, such as one that calls an
external optimiser, implements solve itself. It must then honour every
criterion it is given, return a SolveResult whose objectives come from
dispatchatlas.core.evaluate, and set status from what it knows; check its
schedules with check_schedule in its tests.
Two things decide what a time limit means for a solver in a campaign:
- What it does once in a process. A campaign times a run from the start
of its attempt, so work that only the first call in a process pays, such as
the import of a backend or the filling of a cache, would shorten the search
of the first run of every worker process and of no other. Put that work in
a method
warm_up(self) -> None: the engine calls it before the clock of a run starts, and it counts toward the start-up limit of the worker, not toward the time limit of a run.solvemust still work whenwarm_upwas not called. Import at module level what needs no optional dependency. - Where its clocks start. Inside a campaign every
Search, and every clock started atdispatchatlas.core.clock.clock_start(), counts from the start of the attempt, not from its own creation. A solver that runs several searches in turn, or gives one a share of its time limit, wraps each inwith clock_origin():so that the search counts from its own start; otherwise the limit of a later search has passed before it begins. The engine notes a run that stops for its time limit well before the limit.
Registering it in your code¶
from dispatchatlas.core import StopCriteria
from dispatchatlas.solvers import default_registry
from dispatchatlas_example_plugin import InsertionDescent
registry = default_registry()
registry.register(InsertionDescent)
solver = registry.create("insertion-descent", restart_after=50)
Pass such a registry to a campaign with run(campaign, root, registry=registry).
The process backend sends each solver instance to a worker process, which
imports the solver's class by name, so define the class at the top level of a
module or of the script, never inside its if __name__ == "__main__": block.
Publishing it as a plugin¶
A package publishes solvers through the dispatchatlas.solvers entry-point
group. Each entry point names a function that takes the registry:
[build-system]
requires = ["hatchling>=1.26"]
build-backend = "hatchling.build"
[project]
name = "dispatchatlas-example-plugin"
version = "0.1.0"
description = "An example solver plugin for DispatchAtlas: insertion descent with restarts."
requires-python = ">=3.12"
license = "MIT"
dependencies = ["dispatchatlas>=0.1"]
# DispatchAtlas calls register(registry) of every entry point in this group
# when it builds its default solver registry.
[project.entry-points."dispatchatlas.solvers"]
example = "dispatchatlas_example_plugin:register"
[tool.hatch.build.targets.wheel]
packages = ["src/dispatchatlas_example_plugin"]
Once the package is installed, default_registry() calls every such
function, so the solver appears in dispatchatlas solvers list and can be
named in campaign files. From a clone of the repository, uv run installs the
example plugin beside the library for one command:
uv run --with . --with ./examples/plugin dispatchatlas solvers show insertion-descent
uv run --with . --with ./examples/plugin dispatchatlas version # lists the installed plugins
In a project of your own, uv add ./path/to/your-plugin installs a plugin
next to DispatchAtlas.
A plugin that fails to load is skipped with a warning and registers none of
its solvers, so one broken package cannot disable the others.
default_registry(plugins=False) loads the built-in solvers alone.
Testing it¶
The tests of the built-in solvers show what to check, and
tests/test_examples.py applies the same checks to the example plugin: that
each single limit (evaluations, iterations, time) ends a run with the right
stop reason and exact counts, that the schedule passes check_schedule, that
equal seeds give equal results, and that invalid parameters are refused. Add
tests of the method itself: small cases computed by hand, known optima of tiny
instances, and a comparison with random-search at an equal number of
evaluations.
A benchmark family¶
A family is a dataclass whose fields are its parameters, with a class-level
info: FamilyInfo and a method generate(seed) that returns a problem.
Equal parameters and seed must give the same problem, so draw every random
number from a generator seeded with seed:
from __future__ import annotations
import random
from dataclasses import dataclass
from typing import ClassVar
from dispatchatlas.benchmarks import FamilyInfo, FamilyRegistry
from dispatchatlas.core import Problem, Resource, Task
@dataclass(frozen=True)
class SingleMachine:
"""Jobs with release times on one machine.
Attributes:
jobs: Number of jobs.
max_time: Largest processing time.
"""
jobs: int = 10
max_time: int = 20
info: ClassVar[FamilyInfo] = FamilyInfo(
id="single-machine",
name="Single machine with release times",
problem_class="single-machine",
summary="Jobs with integer processing times and release times on one machine.",
objectives=("total_completion_time",),
)
def __post_init__(self) -> None:
for name in ("jobs", "max_time"):
value = getattr(self, name)
if isinstance(value, bool) or not isinstance(value, int) or value < 1:
raise ValueError(f"{name} must be a positive integer, got {value!r}")
def generate(self, seed: int = 0) -> Problem:
"""Return the problem for ``seed``."""
rng = random.Random(seed)
times = [rng.randint(1, self.max_time) for _ in range(self.jobs)]
latest = sum(times) // 2
tasks = tuple(
Task.on(f"j{index}", "m", float(time), release=float(rng.randint(0, latest)))
for index, time in enumerate(times)
)
return Problem(
f"single-machine-{self.jobs}-{seed}",
tasks,
(Resource("m"),),
objectives=self.info.objectives,
family=self.info.id,
metadata={"jobs": self.jobs, "max_time": self.max_time, "seed": seed},
)
def register(registry: FamilyRegistry) -> None:
"""Add the family to ``registry``."""
registry.register(SingleMachine)
Register it in your code with default_registry().register(SingleMachine)
from dispatchatlas.benchmarks, and pass that registry to a campaign as
run(campaign, root, families=registry). A package publishes families
through the dispatchatlas.benchmarks entry-point group, exactly as solvers:
Name the problems after the family, its size, and the seed, and record the
parameters and the seed in the metadata, so that a problem says where it came
from. The builders of the built-in families, such as flow_shop_problem in
dispatchatlas.benchmarks.shop and build_problem in
dispatchatlas.benchmarks.continuum, turn plain data into problems with the
conventions of the library.
Objectives¶
An objective is a named function of a problem and a schedule, with a sense and a unit. Register it, and problems can declare it by name:
from dispatchatlas.core import Objective, Problem, Schedule, register_objective
def max_tardiness(problem: Problem, schedule: Schedule) -> float:
"""Largest amount by which a task finishes after its due date."""
ends = {item.task: item.end for item in schedule.assignments}
return max(
(
max(0.0, ends[task.id] - task.due)
for task in problem.tasks
if task.due is not None and task.id in ends
),
default=0.0,
)
register_objective(
Objective("max_tardiness", "min", "time", "Largest tardiness over the tasks.", max_tardiness)
)
Three rules make an objective work everywhere:
- Accept partial schedules. Insertion heuristics such as NEH score partial schedules while they build one, so the function must accept a schedule that leaves tasks out, and count only the tasks it holds.
- Register it where it runs. The registry belongs to the process. The
worker processes of a campaign's process backend rebuild every problem, so
the objective must be registered in them too. Every worker runs the
registration hooks of the installed plugins when it starts, so an objective
that a plugin's hook registers works in every backend and from
dispatchatlas campaign run. An objective registered by a script instead must be registered at the top level of that script, or of a module it imports at its top level, since every worker imports the main module. - Know which solvers use it. Search-based solvers optimise any
registered objective, through its function. The exact solvers model only the
objectives they list and refuse the others.
replace=Truere-registers a built-in name with a function of your own, andunregister_objectiveremoves your registration again.
The analysis reads the sense of an objective from the registry, so the tables and figures orient themselves without further settings.