●  How to use · Allocation & Packing

Knapsack & selection

Choose the most valuable subset under one or more budgets, with mandatory items, dependencies and group limits.

What it decides

For every item, the solver decides whether it is selected.

Minimal example

from optimaru.knapsack import solve
from optimaru.knapsack.models import ItemModel, KnapsackProblemModel

problem = KnapsackProblemModel(
    capacity=10,
    items=[
        ItemModel(id="A", weight=6, value=9),
        ItemModel(id="B", weight=4, value=7),
        ItemModel(id="C", weight=5, value=8),
    ],
)

print(solve(problem, time_limit_seconds=1.0, random_seed=42))  # a Score; solves in place
print([item.id for item in problem.items if item.selected], problem.total_value)

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

Input parameters

ItemModel

Field Meaning
id required Item id. weight required Weight counted against capacity. value required Value of selecting it. resource_usage Use of each extra resource. requires Items that must also be selected with this one.

SelectionGroupModel

Field Meaning
id required Group id. item_ids required Items in the group. min_selected Fewest items to select. Inclusive. max_selected Most items to select. Inclusive.

KnapsackProblemModel

Field Meaning
capacity required Maximum total selected weight. items required Candidate items. resource_capacities Capacity by extra resource, for multidimensional budgets. mandatory_items Ids that must be selected. forbidden_items Ids that must not be selected. selection_groups Groups with lower and upper selection bounds.

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 (25)

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.5 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.
nearby_probability 0.0 Probability of drawing move partners from nearby entities. 0 disables it.
nearby_size 20 How many neighbours each entity keeps. 0 picks it automatically or disables it, depending on the use case.
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.05 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.5 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().

ItemModel

Field Meaning
selected True if the item is in the chosen set.

KnapsackProblemModel

Field Meaning
total_weight Selected weight. total_value Selected value. score_hard Hard score. 0 means feasible. score_soft Soft score. With the default weight, it is the selected value.

Constraints

Pick them by calling their classes from optimaru.knapsack.constraints, such as KnapsackCapacityCost(). 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.knapsack.constraints import (
    KnapsackCapacityCost, MandatoryItemsCost, SelectedValueCost,
)

custom = problem.model_copy(deep=True)
print(solve(custom, time_limit_seconds=1.0, random_seed=42, constraints=[
    KnapsackCapacityCost(), MandatoryItemsCost(), SelectedValueCost(weight=2),
]))
Name Level Default weight What it does
knapsack_capacity_cost Hard 1 Amount by which selected weight exceeds capacity.
resource_capacity_cost Hard 1 Overflow across extra resources.
mandatory_items_cost Hard 1 Mandatory items that are not selected.
forbidden_items_cost Hard 1 Forbidden items that are selected.
selection_group_bounds_cost Hard 1 Selection count outside a group's inclusive bounds.
item_dependency_cost Hard 1 Selected items whose required companion is not selected.
selected_value_cost Soft Reward 1 Total selected value, as a negative cost so that the score rises with value.

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.knapsack import with_initial_solution

warm = with_initial_solution(problem, problem.model_dump(mode="json"))
print(solve(warm, time_limit_seconds=1.0, random_seed=42))
print([item.id for item in warm.items if item.selected], warm.total_value)
  • Items are matched by id.
  • selected: false means not selected and is kept as it is. Items the solution leaves out go through the greedy selection around the seeded load.
  • 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 ids, duplicates and non-boolean values raise ValueError.

Exceptions and limits

  • Items are selected or not: this is a 0/1 model, with no fractional or repeated picks.