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.OPTIMALonly when the backend proved optimality, or the enumeration completed. A run stopped by a limit reportsFEASIBLEwith the backend's proven lower bound inSolveResult.bound, soSolveResult.gapmeasures how far from proven the schedule is.Status.INFEASIBLEonly 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.
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
¶
Most digits after the decimal point an exactly scaled value may have.
VALUE_TOLERANCE
module-attribute
¶
Relative tolerance when comparing a backend's objective with the schedule's.
Clock
¶
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 |
required |
decimal_scale
¶
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
|
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]
|
|
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 |
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 |
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 |
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 |
backend_version
¶
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 |
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
¶
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 |
log |
bool
|
Send CP-SAT's search log to the |
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
¶
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]andF[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
texcludes every task running acrosst, 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 the milp solver can run through PuLP.
OBJECTIVES
module-attribute
¶
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
|
|
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
|
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 |
MissingDependencyError
|
If PuLP or the chosen backend is missing. |
SolverError
|
If the backend fails or returns an inconsistent solution. |
warm_up
¶
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
¶
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
|
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
¶
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
¶
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
¶
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. |