●  How to use · Allocation & Packing

Quadratic assignment

Place facilities in locations so that heavy flows travel short distances — layouts, wiring and slotting.

What it decides

For every location, the solver picks one facility, so that each facility ends up in exactly one location.

Minimal example

from optimaru.quadratic_assignment import solve
from optimaru.quadratic_assignment.models import QuadraticAssignmentProblemModel

problem = QuadraticAssignmentProblemModel(
    facilities=["F1", "F2", "F3"],
    locations=["L1", "L2", "L3"],
    flows=[[0, 5, 2], [5, 0, 3], [2, 3, 0]],
    distances=[[0, 8, 15], [8, 0, 13], [15, 13, 0]],
)

solve(problem, time_limit_seconds=1.0, random_seed=42)  # solves in place
print(problem.assignment, problem.total_cost)

The same use case as a Jupyter notebook, with charts and saved outputs: examples/quadratic-assignment.ipynb ↗

Input parameters

ForbiddenAssignmentModel

Field Meaning
facility required Facility id. location required Location it may not use.

QuadraticAssignmentProblemModel

Field Meaning
facilities required Facility ids. locations required Location ids, as many as facilities. flows required Facility-to-facility flow matrix. distances required Location-to-location distance matrix. assignment_costs Optional direct cost matrix, facility by location. fixed_assignments Location id to the facility it must hold. forbidden_assignments Facility and location pairs to avoid. facility_demands Demand of each facility. location_capacities Capacity of each location.

Solve parameters

What you pass to the solve call. Time limit, seed and parallel count are here.

Parameter Default Meaning
time_limit_seconds None Search budget in seconds, from 0 to 1e9. Left unset, it is the config's spent_limit_seconds, 30 by default.
random_seed None Seed for the search. Left unset, it is the config's value, 0 by default.
parallel_solver_count None Independent parallel starts. Each gets its own seed and the full budget, and the best result wins. Left unset, it is the config's value, 1 by default.
stop_at_first_feasible False Stop as soon as hard 0 is reached.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
config None A SolverConfig as the base configuration. Keyword arguments here override it for this solve only; the object you pass is not changed.
constraints None Which constraints to score, and how. Left unset, the defaults apply.

The search only swaps two facilities: ruin-and-recreate, which other use cases use to escape a stall, would break the one-to-one assignment. So late acceptance, the default, stops improving at a local optimum for swaps. Much of a long budget can then go unused, and solving a returned solution again rarely improves it. Stop early with unimproved_spent_limit_seconds or unimproved_step_count_limit, run independent starts with parallel_solver_count, or set acceptor_type to RECORD_TO_RECORD_TRAVEL or SIMULATED_ANNEALING. Simulated annealing keeps accepting some worse swaps while it cools, so it can leave that optimum. Its starting temperature is simulated_annealing_temperature_fraction times the start's soft score in absolute value, or simulated_annealing_starting_temperature if you set one, and it cools to 0 over the time limit, or over step_count_limit when that is further along. ENTITY_TABU accepts only swaps that do not worsen the score.

All search options (14)

Set these on a SolverConfig and pass it as config=.

Parameter Default Meaning
acceptor_type LATE_ACCEPTANCE Which rule accepts or rejects a move.
best_score_limit — Stop early once the best score reaches this value. By default it never fires.
entity_tabu_size 7 Tabu tenure with the ENTITY_TABU acceptor.
full_assert False Check every incremental score against a full recompute. Slow; for debugging.
late_acceptance_size 0 Late-acceptance history length. 0 picks it from the instance size.
on_new_best None Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
parallel_solver_count 1 Independent parallel starts, each with its own seed and the full budget. The best one wins.
random_seed 0 Seed for the search.
simulated_annealing_starting_temperature (0, 0.0) Starting temperature of the SIMULATED_ANNEALING acceptor, as (hard, soft). (0, 0.0) derives it from the start: hard 0, and soft simulated_annealing_temperature_fraction times the start's soft score in absolute value, and at least 1. It cools to 0 over the time limit, or over step_count_limit when that is further along.
simulated_annealing_temperature_fraction 0.01 Fraction of the start's soft score, in absolute value, that becomes the automatic starting temperature. It must be above 0.
spent_limit_seconds 30.0 Time budget in seconds, from 0 to 1e9.
step_count_limit 0 Stop after this many steps. 0 means no limit.
unimproved_spent_limit_seconds 0.0 Stop after this many seconds without a new best. 0 means no limit.
unimproved_step_count_limit 0 Stop after this many steps without a new best. 0 means no limit.

What comes back

solve fills problem in place and returns the engine Score, with .hard and .soft. It also takes the engine object from problem.to_core().

QuadraticAssignmentProblemModel

Field Meaning
assignment Location id to facility id. total_cost Flow multiplied by assigned distance, summed. score_hard Hard score. 0 means feasible. score_soft Soft score.

Constraints

Pick them by calling their classes from optimaru.quadratic_assignment.constraints, such as PinnedAssignmentsCost(). Only what you pass is scored; pass nothing to keep the defaults. A list may name a constraint more than once, and each pick is scored on its own. Each one takes these parameters:

Parameter Default Meaning
weight None Multiplier on the constraint's cost, in units of the level in effect. Left unset, the default weight below applies. A constraint whose default weight is 0 is off until you give it a weight.
level None "hard" makes the constraint a must and "soft" a preference, as do Level.HARD and Level.SOFT. Left unset, it keeps the level below. This use case has no medium level, so "medium" raises ValueError. A reward refuses "hard", and a fixed level refuses any change; both raise ValueError.
exponent 1.0 Sign-preserving power on the cost, above 0, taken after offset. 2.0 squares it, so concentrated violations cost much more. It applies per unit, such as a vehicle or a day, or to the total of a constraint scored as one sum.
offset 0.0 Subtracted from the cost x before the exponent, per unit or total like the exponent. It is in the cost's own measure: seconds, minutes, a count and so on. Any finite number of either sign, keyword only. clip decides what happens below it.
clip True True makes offset a threshold: only the part beyond it counts, max(0, x - offset) ** exponent, so a cost at or below it adds nothing. False takes the literal (x - offset) ** exponent, sign kept: a unit below the offset counts negative, as a reward, even one whose cost is 0. On a level that counts toward hard, clip=False with a non-zero offset raises ValueError, since hard 0 must mean no violation. Keyword only.

This continues the minimal example above.

from optimaru.quadratic_assignment.constraints import FlowDistanceCost, PinnedAssignmentsCost

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=1.0, random_seed=42,
            constraints=[PinnedAssignmentsCost(), FlowDistanceCost(weight=2)]))
Name Level Default weight What it does
pinned_assignments_cost Hard 1 Fixed location assignments that are not respected.
forbidden_assignments_cost Hard 1 Assignments using a forbidden facility and location pair.
location_capacity_cost Hard 1 Assigned facility demand exceeding its location's capacity.
assignment_cost Soft 1 Direct facility-to-location cost.
flow_distance_cost Soft 1 Sum of flow multiplied by assigned-location distance.

How constraints work →

Starting from an existing solution

This needs the latest release: pip install -U optimaru.

with_initial_solution(problem, solution) returns a copy of problem whose search starts from solution, a solved model or the same thing as a JSON dict.

This continues the minimal example above.

from optimaru.quadratic_assignment import with_initial_solution

warm = with_initial_solution(problem, problem.model_dump(mode="json"))
solve(warm, time_limit_seconds=1.0, random_seed=42)
print(warm.assignment, warm.total_cost)
  • Unlike the other use cases, partial starts do not work here: assignment must be a full bijection from locations to facilities. Partial assignments, unknown ids and repeated facilities raise ValueError. The search only swaps two facilities, so every solution it visits stays a bijection.
  • With time_limit_seconds=0 the solve stops at once, so a complete solution comes back as it went in. Use the time limit for this: step_count_limit = 0 means no limit.

Exceptions and limits

  • facilities, locations, flows and distances must have the same square size.