Skip to content

Exact and hybrid methods

Solvers that prove optimality or infeasibility, and a large neighbourhood search whose neighbourhoods are solved exactly.

dispatchatlas.solvers.exact

Exact solvers: they prove optimality or infeasibility, or say that they did not.

Three solvers share one contract:

  • cp-sat (CpSat) states the problem as an interval model and solves it with OR-Tools CP-SAT. It models every problem feature.
  • milp (TimeIndexedMilp) states the problem as a time-indexed 0-1 program and solves it with CBC, HiGHS, Gurobi, or SCIP through PuLP.
  • enumeration (Enumeration) decodes every task order and mode vector with the shared schedule builder. It needs no third-party package and is the reference the other two are tested against on small problems.

What the contract guarantees:

  • Status.OPTIMAL only when the backend proved optimality, or the enumeration completed. A run stopped by a limit reports FEASIBLE with the backend's proven lower bound in SolveResult.bound, so SolveResult.gap measures how far from proven the schedule is.
  • Status.INFEASIBLE only when infeasibility was proven.
  • The published schedule is the solver's own, checked with check_schedule(); the model-based solvers also check that its objective value equals the value the backend proved.
  • A feature or objective a solver does not model exactly raises UnsupportedProblemError; nothing is approximated or replaced by a neighbouring problem. Time values are scaled to integers exactly or refused.
  • The time limit covers model building. Threads default to one and are recorded, with the backend's version and raw status, in SolveResult.extras.

register

register(registry: SolverRegistry) -> None

Add the exact solvers to registry.

dispatchatlas.solvers.exact.common

Machinery the exact solvers share: exact integer time, horizons, and checked results.

The model-based solvers state a problem in integer time. decimal_scale() picks the smallest power of ten that turns every time value into an integer and refuses a problem it cannot represent exactly, so an optimum the backend proves for the model is an optimum of the problem, never of a rounded neighbour. serial_horizon() bounds the finish time of some optimal schedule, which lets a model restrict time without losing every optimum. exact_result() checks a backend's schedule with check_schedule() before publishing it.

MAX_DECIMALS module-attribute

MAX_DECIMALS = 6

Most digits after the decimal point an exactly scaled value may have.

VALUE_TOLERANCE module-attribute

VALUE_TOLERANCE = 1e-06

Relative tolerance when comparing a backend's objective with the schedule's.

Clock

Clock(limit: float | None)

Wall-clock time of one run against an optional limit.

The clock starts at clock_start(): the instant it is created, or the origin set by clock_origin().

Parameters:

Name Type Description Default
limit float | None

Seconds the run may take, or None.

required

elapsed property

elapsed: float

Seconds since the clock started.

remaining

remaining() -> float | None

Seconds left before the limit, never negative, or None without one.

expired

expired() -> bool

Whether the limit has passed.

scaled

scaled(value: float, scale: int) -> int

Return value * scale as the nearest integer.

decimal_scale

decimal_scale(values: Iterable[float], what: str) -> int

Return the smallest power of ten, at most 10**6, that makes every value integral.

Parameters:

Name Type Description Default
values Iterable[float]

The numbers to represent exactly.

required
what str

Plural description of the numbers, used in the error message.

required

Returns:

Type Description
int

The scale factor.

Raises:

Type Description
UnsupportedProblemError

If some value has more than MAX_DECIMALS decimals, or a scaled value is too large for exact integer arithmetic.

transfer_times

transfer_times(problem: Problem, dependency: Dependency) -> dict[tuple[int, int], float]

Return the transfer time of a dependency for every pair of modes.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
dependency Dependency

One of its dependencies.

required

Returns:

Type Description
dict[tuple[int, int], float]

times[(before mode, after mode)], empty when the dependency moves no

dict[tuple[int, int], float]

data across a network. Pairs located on one resource transfer in zero

dict[tuple[int, int], float]

time.

time_values

time_values(problem: Problem, *, dues: bool) -> list[float]

Return every time value a model of problem states.

That is every duration, release, deadline, lag, transfer time, and setup time, plus the due dates when dues is true.

serial_horizon

serial_horizon(problem: Problem, scale: int) -> int

Return a scaled time by which some optimal schedule finishes every task.

The bound is the latest release plus, for every task, its longest mode and its largest incoming setup, plus every dependency's lag and largest transfer time.

It holds for every regular objective, one that never improves when a task finishes later: decoding the start order of an optimal schedule with the serial schedule-generation scheme starts no task later than that schedule (Kolisch 1996), and starts each task no later than the finish of the tasks before it plus its own release, lags, transfers, and setup, which sums to at most this bound.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
scale int

Time scale from decimal_scale().

required

Returns:

Type Description
int

The horizon in scaled time units.

jobs

jobs(problem: Problem) -> list[tuple[float, float, tuple[int, ...]]]

Return (weight, release, task indices) of every job.

A job is a named group of tasks or a task without a group, the unit that completion-time objectives sum over. The order matches dispatchatlas.core.objectives: groups first, then ungrouped tasks.

require_features

require_features(info: SolverInfo, problem: Problem) -> None

Refuse a problem with features the solver does not declare.

Raises:

Type Description
UnsupportedProblemError

If problem has an unsupported feature.

require_bounded

require_bounded(info: SolverInfo, stop: StopCriteria) -> None

Refuse unbounded stop criteria for an iterative solver.

Raises:

Type Description
SolverError

If the solver is iterative and stop sets no time, evaluation, or iteration limit.

primary_objective

primary_objective(problem: Problem, supported: Collection[str], solver_id: str) -> str

Return the problem's primary objective if the solver models it exactly.

Raises:

Type Description
UnsupportedProblemError

If the objective is not in supported, or its name is registered with a definition other than the library's.

backend_version

backend_version(distribution: str) -> str

Return the installed version of a distribution, or "unknown".

confirm_value

confirm_value(solver_id: str, reported: float, schedule_value: float, *, absolute: float = 1e-09) -> None

Check that a backend's objective value matches its schedule's.

Parameters:

Name Type Description Default
solver_id str

Id of the solver, for the message.

required
reported float

The backend's objective value, in problem units.

required
schedule_value float

The objective of the schedule read back from it.

required
absolute float

Absolute tolerance, for backends with floating-point feasibility tolerances.

1e-09

Raises:

Type Description
SolverError

If the two differ, which means the model and the problem disagree and no optimality claim may be published.

exact_result

exact_result(info: SolverInfo, problem: Problem, objective: str, *, status: Status, schedule: Schedule | None, stop_reason: StopReason, elapsed: float, bound: float | None = None, evaluations: int = 0, iterations: int = 0, trace: Sequence[TracePoint] = (), extras: Mapping[str, Scalar] | None = None) -> SolveResult

Build the result of an exact solver after checking its schedule.

Parameters:

Name Type Description Default
info SolverInfo

Metadata of the solver.

required
problem Problem

The problem solved.

required
objective str

Name of the primary objective.

required
status Status

What is known about the schedule.

required
schedule Schedule | None

The backend's schedule, or None without one.

required
stop_reason StopReason

Why the run ended.

required
elapsed float

Wall-clock seconds of the run.

required
bound float | None

Proven lower bound on the primary objective.

None
evaluations int

Schedules the solver scored.

0
iterations int

Main-loop iterations, as the solver defines them.

0
trace Sequence[TracePoint]

Improvements of the incumbent over time.

()
extras Mapping[str, Scalar] | None

Backend facts such as its raw status.

None

Returns:

Type Description
SolveResult

The result.

Raises:

Type Description
SolverError

If the schedule breaks a constraint of the problem, or a status that needs a schedule comes without one.

dispatchatlas.solvers.exact.cpsat

The cp-sat solver: an exact interval model solved with OR-Tools CP-SAT.

The model itself lives in dispatchatlas.solvers.exact._cpsat, which is imported only when a solve starts, so registering this solver needs no third-party package.

OBJECTIVES module-attribute

OBJECTIVES = frozenset({'makespan', 'total_completion_time', 'total_flow_time', 'mean_response_time', 'total_tardiness', 'max_lateness', 'tardy_tasks', 'energy', 'cost'})

Objectives the cp-sat solver optimises exactly. Others are refused.

CpSat dataclass

CpSat(threads: int = 1, relative_gap: float = 0.0, log: bool = False)

Prove optimal schedules with the OR-Tools CP-SAT solver.

Each task gets one optional interval per mode, exactly one present, and the resources, dependencies, setups, and permutation constraint become CP-SAT constraints (see IntervalModel). The solver models every problem feature and optimises the problem's primary objective when it is one of OBJECTIVES; any other objective is refused.

Time is stated exactly: every duration, release, lag, deadline, due date, transfer time, and setup time is multiplied by the smallest power of ten, up to 10**6, that makes all of them integers. Weights, demands, and energy or cost coefficients are scaled the same way. A problem that needs more decimals is refused rather than rounded.

Statuses are CP-SAT's own proofs. OPTIMAL means CP-SAT proved the schedule optimal, FEASIBLE that it stopped earlier, with bound holding its proven lower bound, INFEASIBLE that it proved no schedule exists, and UNKNOWN that it stopped before finding a schedule. The published schedule is CP-SAT's own solution, checked with check_schedule(), and its objective value must equal the model's.

Stop criteria: the time limit covers model building and search. Each improving solution CP-SAT reports counts as one evaluation and one iteration, so evaluation and iteration limits stop the search after that many solutions; the search between two solutions is not bounded, so pair them with a time limit on hard problems. A target stops the search at the first solution that reaches it. Patience has no effect, because every reported solution improves on the previous one. Without a time limit the search ends only on a proof or another criterion.

With one worker (the default) and no time limit, runs are deterministic. With several workers, a few more solutions may arrive, and be counted, while the search stops. The run seed is not used.

Attributes:

Name Type Description
threads int

CP-SAT workers. More than one runs CP-SAT's parallel portfolio, which is faster but not deterministic.

relative_gap float

Relative gap between solution and bound at which CP-SAT may stop. The default 0 asks for a proof. A run that stops at a positive gap reports FEASIBLE unless its bound meets the value.

log bool

Send CP-SAT's search log to the dispatchatlas logger at level INFO.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Build and solve the CP-SAT model of problem.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
stop StopCriteria

Stop criteria; at least one of a time, evaluation, or iteration limit.

required
seed int

Ignored; the search is deterministic with one worker.

0

Returns:

Type Description
SolveResult

The result with CP-SAT's schedule, status, and bound.

Raises:

Type Description
UnsupportedProblemError

If the objective is not modelled, or a value cannot be scaled to an integer exactly.

SolverError

If the stop criteria are unbounded.

MissingDependencyError

If OR-Tools is not installed.

warm_up

warm_up() -> None

Import OR-Tools and the model, which the first call in a process pays for.

Raises:

Type Description
MissingDependencyError

If OR-Tools is not installed.

dispatchatlas.solvers.exact.milp

The milp solver: a time-indexed 0-1 program solved through PuLP.

The formulation follows Pritsker, Watters and Wolfe (1969), with modes as in Talbot (1982). Time is divided into periods of equal length, and a binary x[i, m, t] states that task i starts in mode m at period t:

  • every task starts exactly once: sum over m, t of x[i, m, t] = 1;
  • start and finish are linear in x: S[i] = sum t * x[i, m, t] and F[i] = sum (t + p[i, m]) * x[i, m, t];
  • every dependency: S[after] >= F[before] + lag;
  • every resource and period: the demands of the tasks running in that period sum to at most the capacity;
  • on an exclusive resource, one where every demand is the full capacity, a zero-duration task started at period t excludes every task running across t, the instant the data model defines;
  • releases and hard deadlines remove the start periods that break them.

Why the periods lose no optimum. Times are first scaled to integers exactly (see decimal_scale()). For a regular objective some optimal schedule is active, and every start of an active schedule is a sum of releases, durations, and lags, so it is a multiple of their greatest common divisor, the period length used here. The horizon is serial_horizon(), tightened by a heuristic schedule when that is valid: its makespan bounds the optimal makespan, and its total completion time divided by the smallest job weight bounds every completion time of an optimal schedule.

BACKENDS module-attribute

BACKENDS = ('cbc', 'highs', 'gurobi', 'scip')

Backends the milp solver can run through PuLP.

OBJECTIVES module-attribute

OBJECTIVES = frozenset({'makespan', 'total_completion_time', 'total_tardiness'})

Objectives the milp solver optimises exactly. Others are refused.

TimeIndexedMilp dataclass

TimeIndexedMilp(backend: str = 'cbc', threads: int = 1, relative_gap: float = 0.0, max_variables: int = 200000)

Prove optimal schedules with a time-indexed MILP.

The solver models precedence with lags, modes, multi-resource and cumulative demands, zero-duration tasks as the data model defines them, releases, due dates, and hard deadlines, and optimises makespan, total_completion_time, or total_tardiness; other objectives, network transfers, setup times, and the permutation constraint are refused. Its size grows with the number of periods, so it suits problems with short horizons.

Statuses come from the backend's own solution status, never from PuLP's overall status, which reports a time-limited CBC incumbent as optimal. OPTIMAL means the backend proved optimality, FEASIBLE that it stopped earlier with a solution, INFEASIBLE that it proved no schedule exists, and UNKNOWN that it stopped without a solution. bound holds the backend's best bound when it reports one; CBC's is read from its log, where it is printed to six significant digits and so is loosened by one unit in the last digit. The published schedule is read from the backend's solution and checked with check_schedule().

The solver is not iterative: it runs until the backend proves optimality or infeasibility, or until the time limit. The limit covers building the model and handing it over: the backend gets the time left after building, minus the building time again, about what PuLP needs to pass the model on. Evaluation and iteration limits do not apply, and the result counts one evaluation, the schedule read back.

Attributes:

Name Type Description
backend str

"cbc" (bundled with PuLP), "highs" (needs highspy), "gurobi" (needs gurobipy and a licence), or "scip" (needs pyscipopt).

threads int

Threads the backend may use. SCIP runs single-threaded.

relative_gap float

Relative gap at which the backend may stop. The default 0 asks for a proof. A run that stops at a positive gap reports FEASIBLE unless the reported bound meets the value.

max_variables int

Largest number of start binaries built. Larger models are refused before any memory is spent on them.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Build the time-indexed model of problem and solve it with the backend.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
stop StopCriteria

Stop criteria. Only the time limit applies.

required
seed int

Ignored; the backends run deterministically.

0

Returns:

Type Description
SolveResult

The result with the backend's schedule, status, and bound.

Raises:

Type Description
UnsupportedProblemError

If a feature or the objective is not modelled, a value cannot be scaled exactly, or the model would exceed max_variables.

MissingDependencyError

If PuLP or the chosen backend is missing.

SolverError

If the backend fails or returns an inconsistent solution.

warm_up

warm_up() -> None

Import PuLP and the backend, which the first call in a process pays for.

Raises:

Type Description
MissingDependencyError

If PuLP or the chosen backend is missing.

dispatchatlas.solvers.exact.enumeration

The enumeration solver: exhaustive search over task orders and mode vectors.

It needs no third-party package and serves as the reference that the model based solvers are tested against.

Why it is exact. Fix an optimal schedule and list its tasks by start time, zero-duration tasks first among equal starts, other ties broken along the dependencies. Decoding that list with the schedule's own modes by the serial schedule builder, which places each task at its earliest feasible start and may fill idle gaps, starts every task no later than the optimal schedule does: when a task is placed, the tasks placed before it started no later than in the optimal schedule and therefore occupy each resource at any later moment at most as much, the instants of zero-duration tasks placed before it lie no later than its own start, and its predecessors finish no later. Every objective this solver accepts is regular, never better when a task finishes later, so the decoded schedule is optimal as well, and it meets every hard deadline the optimal schedule meets. Enumerating every precedence-feasible order and every mode vector therefore reaches an optimal schedule (Kolisch 1996; Sprecher, Kolisch and Drexl 1995). The argument covers release times, lags, transfer times, modes, and cumulative resources, but not sequence-dependent setup times, so problems with setups are refused.

Permutation problems. The schedule builder decodes one group after another, appending every task to its machines, zero-duration tasks included. The solver therefore enumerates group orders and mode vectors. When every dependency stays within a group, each machine then processes the groups in the enumerated order, and each task starts as early as that order allows, which is the best schedule of the order. Permutation problems with a dependency between two groups are refused.

Pruning. Two orders that reach the same partial schedule have the same completions, so the search expands each distinct partial schedule once. A partial schedule in which a placed task already misses its deadline is not expanded, because placed tasks never move.

OBJECTIVES module-attribute

OBJECTIVES = frozenset({'makespan', 'total_completion_time', 'total_flow_time', 'mean_response_time', 'total_tardiness', 'max_lateness', 'tardy_tasks', 'energy', 'cost'})

The built-in objectives, all regular once the modes are fixed.

Enumeration dataclass

Enumeration(max_tasks: int = 8)

Find an optimal schedule by decoding every task order and mode vector.

Statuses: OPTIMAL once the enumeration is complete, with bound equal to the value; INFEASIBLE when it is complete and no schedule meets every hard deadline. A run cut short by a stop criterion reports the best schedule so far as FEASIBLE, as VIOLATED if it misses a deadline, or UNKNOWN without one, never OPTIMAL.

The solver is not iterative: without stop criteria it runs until the enumeration is complete. It honours any criteria it is given. Each complete schedule it scores is one evaluation and one iteration. Its extras record states, the number of distinct partial schedules expanded, and complete.

Attributes:

Name Type Description
max_tasks int

Largest number of tasks accepted. The work grows with the factorial of the task count, so larger problems are refused.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Enumerate the schedules of problem and return the best.

Parameters:

Name Type Description Default
problem Problem

The problem.

required
stop StopCriteria

Optional stop criteria. Without any, the run is complete.

required
seed int

Seed recorded by the search; the enumeration uses no randomness.

0

Returns:

Type Description
SolveResult

The result.

Raises:

Type Description
UnsupportedProblemError

If the problem has setups, more than max_tasks tasks, or an objective that is not built in, or is a permutation problem with a dependency between groups.

dispatchatlas.solvers.hybrid

Hybrid solvers: heuristic search around exact subproblem solves.

restricted-neighbourhood-search improves one schedule by large neighbourhood search (Shaw 1998; Pisinger and Ropke 2010) whose neighbourhoods are solved exactly. Each iteration takes the items of the incumbent schedule, tasks or, in permutation problems, jobs, in order of their first start, and frees a window of window consecutive ones at a random place. Every other task keeps its decisions: its mode, and its order on each resource it uses relative to the other kept tasks. The restricted problem is the CP-SAT interval model of the cp-sat solver (see IntervalModel) with those decisions added as constraints and the incumbent as a hint, so CP-SAT places the freed tasks anywhere, in any mode, and retimes the others around them, which the incumbent's start times alone would not allow.

The solution CP-SAT returns is turned back into a task order, by start time, and its modes, and decoded by the shared schedule builder. For a regular objective the decoded schedule starts no task later than CP-SAT's, since the serial schedule-generation scheme never delays a task beyond a feasible start of the same order. It replaces the incumbent when it is no worse, so the run never moves to a worse schedule.

Budgets: every exact call is one iteration and one evaluation, the decoding of its solution, or, when it finds none, a probe of the incumbent that keeps evaluation limits binding. A call runs on one worker and stops after call_limit units of CP-SAT's deterministic time, or earlier at the run's time limit, so runs without a time limit replay exactly from their seed. When the window covers every task and CP-SAT proves the window optimal, the schedule is optimal and the run ends.

Window dataclass

Window(order: list[int], modes: list[int], proven: bool)

The solution of one restricted problem.

Attributes:

Name Type Description
order list[int]

Task indices by start time, then finish time, then index.

modes list[int]

Mode of every task.

proven bool

Whether CP-SAT proved the restricted problem optimal.

RestrictedNeighbourhoodSearch dataclass

RestrictedNeighbourhoodSearch(window: int = 8, call_limit: float = 1.0)

Large neighbourhood search whose neighbourhoods CP-SAT solves exactly.

The first schedule decodes the tasks in decreasing upward rank, each in its earliest-finishing mode.

Attributes:

Name Type Description
window int

Items, tasks or jobs, freed per exact call.

call_limit float

CP-SAT deterministic time per exact call, in its own units of roughly one second.

warm_up

warm_up() -> None

Import OR-Tools and the model, which the first call in a process pays for.

Raises:

Type Description
MissingDependencyError

If OR-Tools is not installed.

solve

solve(problem: Problem, stop: StopCriteria, seed: int = 0) -> SolveResult

Improve the incumbent window by window until a stop criterion fires.

Raises:

Type Description
UnsupportedProblemError

If the problem has an unsupported feature, an objective the interval model does not state, or time values it cannot scale to integers exactly.

MissingDependencyError

If OR-Tools is not installed.

register

register(registry: SolverRegistry) -> None

Add the hybrid solvers to registry.