Routing, scheduling & trade-offs
Vehicle routes, schedules, convex quadratic programs, Pareto fronts and decisions under uncertainty — searched on your own machine, reporting the bound you have rather than claiming an optimum.
Five kernel families for the problems where proving the best answer is not on the table: travelling-salesman and vehicle routing, job-shop and project scheduling, convex quadratic programs, Pareto fronts, and programs whose data is uncertain. All run as compiled kernels inside the runtime that ships with the SDK — there is nothing to start and nothing to install separately.
from algenta import MojoRuntime
import math
runtime = MojoRuntime(mode="local")
# seven stops as coordinates; the kernels take the distance matrix, flat and row-major
pts = [(0.0, 0.0), (4.0, 1.0), (8.0, 0.0), (8.0, 6.0), (4.0, 5.0), (0.0, 6.0), (3.0, 3.0)]
d = [math.dist(p, q) for p in pts for q in pts]
nn = runtime.execute("optimization.routing", "tsp_greedy_flat", [d, 7])["result"]
nn["tour_length"] # 34.718... — nearest neighbour from stop 0
nn["local_optimum"] # False — nothing has been searched yet
r = runtime.execute("optimization.routing", "tsp_local_search",
[d, 7, 64, True, True, 3])["result"]
r["tour"] # [0, 1, 2, 3, 4, 6, 5, 0] — closed, and verified a permutation
r["tour_length"] # 30.848...
r["improvement"] # 3.870... — what the search bought over its own starting tour
r["local_optimum"] # True — no improving move of the declared kinds is left
r["moves_evaluated"] # 154None of that says "optimal", and neither does the status. Ask it what the code means and it tells you in as many words:
30.848... is the best tour those two families of moves can reach from that starting tour. It is a real tour of real length — verified to visit every stop exactly once — and it is not certified to be the shortest one. Every driver on this page is a search of that kind, so every one of them reports what it has instead of what it would be nicer to claim.
The modules
optimization.routing
travelling-salesman tours by 2-opt, Or-opt and iterated local search; vehicle routing with hard capacity and hard time windows; a distance-matrix census; and audits of a tour or a routing you were handed
optimization.scheduling
job-shop scheduling by tabu search over critical machine swaps, resource-constrained project scheduling by multi-start schedule generation, makespan lower bounds with the critical path, resource peak profiles, and verification of a schedule from anywhere
optimization.quadratic
convex quadratic programs by an active-set method — a KKT certificate, a measured optimality gap from the linearisation, a convexity report, and refusal of an objective that is not convex
optimization.multiobjective
Pareto front decomposition, front certification, crowding distance and NSGA-II selection, hypervolume against an explicit reference, a genetic search over a linear model, and exact lexicographic optimisation
optimization.robust
scenario generation, per-scenario optima with worst case and CVaR, the decision that is feasible in every scenario, and measured chance-constraint satisfaction rates
Matrices cross as flat row-major lists plus their dimensions, and constraint senses are 0 for <=, 1 for ==, 2 for >= — the same conventions as the exact solvers, which these drivers call for every inner linear program.
A heuristic reports its bound, not a verdict
A local search cannot prove that nothing better exists. What it can do is measure the distance to a bound that holds for every schedule, tour or point — and that number is worth more than a status word, because it tells you whether to keep searching.
For a job shop there are two such bounds and both are cheap: the operations of one job run in sequence, so the longest job is a bound; a machine runs one operation at a time, so its total load is a bound.
The search then reports the incumbent, that bound, and the gap between them:
There is no proven_optimal field on a tour, a routing, a schedule or a heuristic front, and that absence is the design — where a proof genuinely is available, as it is for the convex quadratic programs below, the field exists and has to be earned. optimal_by_bound is a statement about the bound — the incumbent met it — not about the search, which proves nothing either way. A solver that prints "optimal" when its own search stopped has told you about its budget and labelled it a property of your problem; here the two facts stay separate, and iteration_limit_hit is the one that answers "would more time help".
Why a gap beats a verdict: 11.0 against a bound of 10.0 says the answer is within one time unit of anything achievable, which is usually where you stop. A verdict of "optimal" from a truncated search says nothing you can act on, and a wrong one is undetectable from the outside.
The critical path, and when it is the wrong explanation
For a project with renewable resources the same shape holds, with one addition that matters more than the numbers: a project can be late because of a resource, not a dependency, and a precedence-only critical path reports that as a dependency.
resource_delayed_at is the honest half of the explanation. Activity 5 starts at 12.0 with every predecessor long finished; presenting a precedence path as the reason would answer "what do I change" wrongly. rcpsp_peak_usage_flat gives the other half — where each resource peaks, and when:
An answer that does not exist is reported absent
Same rule as the exact solvers, and it bites harder here, because a search always has something plausible lying around in a partly-built structure. None of it is returned.
A tour that is not a tour has no length — not a partial sum:
A project whose dependencies form a cycle has no schedule, and therefore no bound either:
A dynamic program over a cyclic dependency graph terminates and returns a finite makespan for a schedule that cannot exist. That is the specific wrong number this status replaces.
An activity demanding more than a resource has is infeasible at every instant, and both culprits are named because "infeasible" alone is not actionable:
The same applies to a vehicle count (vrp_vehicle_bound on a load bigger than one vehicle returns has_bound False and the offending index, because the fleet size of an impossible instance does not exist), and to a hypervolume reference point (mo_reference_point returns an empty list rather than a zero vector, which would be a perfectly plausible reference somebody would then use).
Same seed, same answer
These searches are randomised: tie-breaks, restarts, kicks, crossover, mutation and scenario draws all consume random numbers. Every one of those draws is addressed by an explicit seed plus its own coordinates, so the answer is a pure function of the arguments — including on a different machine, and whatever else was computed first.
This is not a nicety. A heuristic whose output changes between runs cannot be used in a decision that has to be explained: the schedule you defend in a meeting has to be the schedule the same call produces tomorrow, and a difference between two runs has to mean somebody changed the data. So there is no hidden clock and no address-dependent hashing — nothing about a run depends on when or where it happened.
Where a convenience entry point does supply a seed for you, it is a fixed constant compiled into the kernel rather than anything drawn at run time, and the sample count comes back with the result — so the call is still reproducible and still says what it did. A seed taken from the clock would not be, which is the thing to avoid.
A different seed is a different walk, and the result says so without pretending the answer changed:
The path may depend on the seed; the answer may not. Where a search genuinely cannot prove its answer — a tour, a schedule, a front — a different seed can land on a different local optimum, which is exactly why the seed travels with the result instead of living in a log.
Scenario draws carry their whole provenance for the same reason:
Seed, stream, generator and distribution come back with the block, so a stored answer can be re-derived from the record rather than merely believed.
A structure that is not valid is not returned
Every driver here re-checks its own answer against the caller's own arrays before returning it, and discards it if the check fails. A search that builds a structure incrementally is exactly where a subtle bookkeeping bug produces a plausible-looking result, so the answer is audited by the same routine that audits a stranger's.
a tour must visit every stop exactly once — verified after every accepted move, not once at the end;
a routing must respect every capacity and every time window, and serve every customer exactly once;
a schedule must satisfy every precedence and keep every resource inside its limit at every instant where the profile can peak;
a Pareto front must contain no dominated point, and must not have left a Pareto-optimal one out;
a chance constraint met in 52% of scenarios is not met at 95%, and the measured rate is reported next to the level it was judged against.
Vehicle routing: capacity and windows are hard
Vehicle v's sequence is stops[route_start[v] : route_start[v + 1]]. Empty routes are removed, not retained as zero-length slots, so the offsets partition stops exactly and a vehicle that never leaves the depot has no load, no distance and no entry.
vrp_check runs that same audit on a routing from anywhere — and a structural break is a rejection while a semantic break is a report, with the counts and the location:
A routing that serves a customer twice is not a routing however cheap it is, so total_distance is reported and feasible is what says whether the routes are an answer.
With time windows, distance doubles as the travel-time matrix — one matrix, stated, rather than two that can silently disagree. A vehicle may wait at a stop it reaches early, must begin service by due, and must be back at the depot by due[0]. When the data alone makes that impossible, it is proven rather than searched for:
Fronts: no dominated point, and nothing left out
pareto_certify checks a front somebody else produced, condition by condition, so you can audit a recommendation rather than adopt it:
Any subset of the true front is an antichain that nothing outside beats, so a claim of one point out of forty passes the first two conditions. maximal is the condition that makes the certificate about the whole Pareto set instead of a fragment of it — and it is the one a certificate omits when no test exercises the shape that needs it.
Chance constraints: the rate, next to the level
[2.0, 6.0] is the optimum of the deterministic program, and it sits exactly on two of its rows — so it survives about half the scenarios, and the plan is feasible in 28% of them. A boolean would have hidden all of that; the joint rate is usually the number that matters, and it is not determined by the per-row rates.
Convexity is checked, not assumed
For an indefinite objective, "optimal" has no meaning: the same point is a minimum along one direction and a maximum along another. So a non-convex quadratic program is refused, with the pivot that refuted it named in your own index space:
And the check survives an objective whose units differ by orders of magnitude, which is the ordinary case for a portfolio or an engineering trade-off, not an exotic one:
A tolerance scaled by the largest entry of the whole matrix accepts a curvature of -0.68 beside a 1e12 as convex, and then everything downstream inherits a false premise: a KKT certificate and an independent bound will both agree the answer is optimal, because both were handed the same wrong verdict. Each direction's curvature is therefore judged against its own magnitude.
A certified minimiser, and a measured gap when there is none
upper is padding here: a bound value whose flag is not set is never read, so a variable with no upper limit is a flag rather than an infinity — an infinity that enters arithmetic produces inf - inf, which is not a number.
certified and proven_optimal are separate fields because they are separate claims, proved by different computations that have to agree. The bound comes from minimising the objective's linearisation over the same feasible set, which for a convex objective is a genuine lower bound — so it is available for any feasible point, including one you produced elsewhere:
at_optimum is decided inside the call rather than left to the caller, because the gap is a difference of three numbers and only that call holds all three. A tolerance sized by the objective's magnitude instead of the gap's own terms is how a measured gap of four hundred million passes for zero on a program whose optimum is near 1e17 — so the verdict is computed where all three magnitudes are in scope.
qp_kkt_check audits a point and its duals from the outside, and the four conditions are reported separately so a rejection says which one failed:
What the certificate covers, in full: stationarity per component; primal feasibility per row and per bound, each against that row's own scale; dual sign feasibility, including a zero multiplier on a bound you never declared; and complementary slackness in both directions — a slack row has a zero dual, and a priced row is tight. Convexity is part of the conjunction, because a KKT point of a non-convex objective is not a minimum. Non-finite inputs are rejected before any tolerance is computed from them: a tolerance derived from a nan is a nan, every comparison against it is false, and the audit would pass having counted zero violations.
Trade-offs: fronts, volumes and priorities
Hypervolume is exact for one and two objectives, and the reference point is echoed back because the number is meaningless without it:
For three or more objectives the sweep is not exact, and the driver says so rather than returning an estimate in the field a caller reads as a value:
The same seed reproduces 18.578125 exactly; a different seed gives a different estimate inside the same proven bounds. std_error is never 0.0 from a degenerate sample — zero hits out of 4096 draws is no measurement, not a measurement of zero.
A genetic search over a linear model gets the same treatment, plus one bound that is proven: the exact per-objective optimum, from one linear program per objective.
That status is deliberately not the success code the exact solvers use, and there is no proven_optimal field to set. ideal_gap is the evidence that exists; the front's own spread is not evidence about anything.
Where priorities are strict rather than traded off, lexicographic_linear is exact — every stage is a simplex solve, so its success status is the ordinary one:
Uncertainty: what a scenario answer does and does not prove
Two different questions live here, and conflating them is the classic error.
Wait-and-see solves each scenario on its own. The worst of those optima is a bound on the robust value, not the robust value itself — nobody gets to pick their decision after seeing which scenario happened:
The status is the whole point: the number is real, and it is a bound. bound_direction is a field rather than a sentence in the documentation because it flips with the objective sense, and "my worst case is at least 3" and "at most 3" lead to opposite decisions. cvar_tail_fraction travels with cvar_level for the same reason — a caller who meant "the 5% tail" and passed 0.05 sees a tail fraction of 0.95 and finds out immediately.
If even one scenario fails to solve, there is no risk summary at all, because a worst case over a subset is a statement about a different scenario set than the one you asked about:
Here-and-now is the decision you actually have to make: one point, feasible in every scenario. Because only the right-hand sides vary, that intersection is a single linear program and its optimum is exact over the given scenarios — so this driver is not a heuristic, and it says which scenario binds each row:
What this does not prove. It is a sampled guarantee, over 64 drawn scenarios, and nothing here is a statement about a scenario nobody drew. A wider draw can only tighten a row, so the objective errs in the direction bound_direction names — that is the honest reading, and it is not a distributional guarantee. Likewise a satisfaction rate is an estimate: rate_stderr is the binomial standard error of the estimate, which measures sampling noise and is not a confidence bound on the true probability. n_distinct_scenarios tells you whether a per-scenario block was supplied at all: without one, every scenario shares the same row and the count is 1, because verifying one unchanging row a thousand times is the same measurement a thousand times rather than evidence about a thousand scenarios. It does not de-duplicate scenarios you did supply — a thousand supplied rows count as a thousand even if they happen to be identical, since deciding that two rows are "the same scenario" is a modelling judgement and not one this kernel makes for you.
Shapes, sizes and search budgets are checked before anything is read
Every function validates its declared dimensions against the actual list lengths before indexing, and returns a status rather than reading past the end of an array. Declared sizes are capped against what the request actually contains, and the work is bounded too, not only the memory: a dimension can sit inside an allocation limit and still drive an unbounded number of comparisons, so every loop bound that multiplies into the cost is charged against the budget. Exceeding it is a status, never a truncated answer presented as a complete one.
A tolerance is always derived from the one quantity being judged — this row's own magnitude, this pivot's own curvature, this gap's own terms — and never from a sum, a maximum or a norm over everything else in the model. An aggregate lets one row's units pay for another row's contradiction, and the result is a confident answer to a problem that has none.
Each family has its own status vocabulary and a matching name function — route_status_name, sched_status_name (with sched_violation_name for which constraint an audit failed), qp_status_name, mo_status_name, robust_status_name — and each falls through to the shared vocabulary, so an input rejection keeps the name of the module that rejected it and tells you which of your arrays to look at.
See also
Optimization & decision programs — linear, integer, assignment and flow, solved exactly
Sparse systems & graph analytics — sparse solvers, shortest paths, centrality
Batched and chained execution — many kernel calls in one frame
Runtime library catalog — every module and function
Last updated
Was this helpful?