●  How to use · Allocation & Packing

Max-cut & partitioning

Split a weighted graph into two sides to maximize the weight crossing between them, with balance and pairing rules.

What it decides

For every vertex, the solver picks side 0 or side 1.

Minimal example

from optimaru.max_cut import solve
from optimaru.max_cut.models import EdgeModel, MaxCutProblemModel

problem = MaxCutProblemModel(
    vertices=["A", "B", "C"],
    edges=[
        EdgeModel(source="A", target="B", weight=2),
        EdgeModel(source="B", target="C", weight=3),
        EdgeModel(source="A", target="C", weight=4),
    ],
)

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

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

Input parameters

EdgeModel

Field Meaning
source required One end. target required The other end. weight Edge weight. 1 by default.

VertexPairModel

Field Meaning
first required One vertex. second required The other vertex.

MaxCutProblemModel

Field Meaning
vertices required Unique vertex ids. edges required Weighted undirected edges. fixed_partition Vertices pinned to side 0 or 1. same_partition_pairs Pairs that must stay on one side. different_partition_pairs Pairs that must be split. min_partition_size Fewest vertices on either side. max_partition_size Most vertices on either side.

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.
All search options (23)

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

Parameter Default Meaning
best_score_limit — Stop early once the best score reaches this value. By default it never fires.
change_move_weight 0.8 Relative share of change moves. 0 disables them.
descent_weight 0.0 Share of best-improvement descent. 0 turns it off.
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.
ruin_recreate True Run adaptive ruin-and-recreate kicks when the search stagnates.
ruin_recreate_as_move_max_ruin 12 Most entities that small ruin removes.
ruin_recreate_as_move_weight 0.0 Probability that a step is a small ruin and repair, judged like any other move. Negative picks it automatically where the use case supports that; 0 turns it off.
ruin_recreate_max_ruin_count 60 Absolute cap on entities removed per kick.
ruin_recreate_max_ruin_fraction 0.3 Largest share of the solution one kick removes.
ruin_recreate_min_ruin_fraction 0.1 Smallest share of the solution one kick removes.
ruin_recreate_operator_decay 0.8 How fast operator weights adapt.
ruin_recreate_polish_steps 5000 Hill-climbing moves that polish each kick. Not counted against step_count_limit.
ruin_recreate_rewards [33.0, 9.0, 3.0, 0.0] Operator rewards for a new best, a better, an accepted and a rejected result.
ruin_recreate_unimproved_step_trigger 5000 Steps without a new best before a kick.
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.
swap_move_weight 0.2 Relative share of swap moves. 0 disables them.
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().

MaxCutProblemModel

Field Meaning
partition Vertex id to its side, 0 or 1. cut_weight Total weight of edges crossing the partition. score_hard Hard score. 0 means feasible. score_soft Soft score. With default weights, it is the cut weight.

Constraints

Pick them by calling their classes from optimaru.max_cut.constraints, such as FixedPartitionCost(). 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.max_cut.constraints import (
    CutWeightCost, FixedPartitionCost, PartitionImbalanceCost,
)

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=1.0, random_seed=42, constraints=[
    FixedPartitionCost(), CutWeightCost(), PartitionImbalanceCost(weight=1),
]))
Name Level Default weight What it does
fixed_partition_cost Hard 1 Vertices on a side other than their fixed one.
same_partition_pairs_cost Hard 1 Pairs that must stay together but are split.
different_partition_pairs_cost Hard 1 Pairs that must be split but are on one side.
partition_size_bounds_cost Hard 1 Vertices outside the inclusive size bounds, on either side.
partition_imbalance_cost Soft 0 Absolute difference between the two sides. Weight 0 by default, so give it a weight to use it.
cut_weight_cost Soft Reward 1 Total weight of edges crossing the partition, as a negative cost so that the score rises with it.

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.max_cut 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.partition, warm.cut_weight)
  • Vertices the partition leaves out take the default start. Any result of solve is accepted, feasible or not. Scoring a partial partition with calculate_score or constraint_costs raises ValueError; solve fills it in.
  • Under exact size bounds the search only swaps sides, so a seed of the wrong size keeps that size and its hard penalty.
  • 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.
  • Unknown vertices, sides other than 0 or 1 and sides that contradict fixed_partition raise ValueError.

Exceptions and limits

  • partition_imbalance_cost is off until you give it a weight.