Skip to content

0/1 knapsack

The problem

The 0/1 knapsack problem has items, each with a weight and a value (a profit), and a knapsack with a capacity. It chooses the items with the highest total value whose total weight is at most the capacity; each item is taken whole or not at all. Martello and Toth (1990, Knapsack Problems: Algorithms and Computer Implementations, Wiley) treat it and its variants in a book.

The instance is drawn from the first of Pisinger's (2005) classes of generated instances, the uncorrelated one: 50 items whose weights and values are drawn independently and uniformly from 1 to R = 1000. The capacity is half the total weight, rounded down, as instance 50 of Pisinger's series of 100 has it: c = ⌊50/101 Σ w⌋ (his eq. 5), 12,572 of 25,397. The instance is genoxide's problems::binary::Knapsack::generator(KnapsackClass::Uncorrelated, 50).seed(1): its items are drawn from seed 1 with genoxide's portable random numbers, the same on every platform and in Python. The first item weighs 613 and is worth 705; the second weighs 858 and is worth 45.

What makes it hard

The problem is NP-hard, though only weakly: dynamic programming over the capacities solves it in time proportional to the number of items times the capacity (Bellman's recursion), and genoxide's optimum does, exactly. With 50 items there are 2⁵⁰ ≈ 10¹⁵ selections, far too many to try.

The capacity binds: the best selection weighs 12,551 of 12,572, and taking any further item breaks the limit: the lightest item left out weighs 209. Pisinger's classes are hard in different ways. Uncorrelated instances are "generally easy to solve" for exact algorithms; in the strongly correlated class, whose values are the weights plus R/10, sorting by value per unit of weight is sorting by weight, and the continuous optimum is far from the integer one.

Representation

A Binary genome of 50 bits, a bit per item: 1 takes the item. Every bit string is a selection, but not every selection fits.

The fitness has two numbers: the total value, and how far the weight exceeds the capacity (0 when it fits), constraint::at_most(weight, capacity). genoxide compares them with Deb's feasibility rules (Deb, 2000, Computer Methods in Applied Mechanics and Engineering 186: 311-338). A selection that fits beats one that doesn't. Two that fit compare by value. Two that don't compare by their excess weight. So overweight selections still guide the search: the less overweight, the better. There is no penalty weight to tune.

Algorithm

A genetic algorithm:

  • a population of 200;
  • tournament selection of size 3; genoxide's guide recommends tournaments with constraints, since roulette selection gives infeasible selections no weight;
  • uniform crossover, which takes each item's bit from either parent;
  • bit-flip mutation at a rate of 1/50 per bit, one flip per child on average.

It stops as soon as it reaches the optimum, which dynamic programming finds beforehand; or, if it never does, after 200 generations without improvement, or after 2,000 generations. A run from seed 1, then runs from seeds 1 to 20. As a contrast, the same runs on an instance of Pisinger's strongly correlated class, 50 items from seed 1.

Output

The first line gives the instance: its total weight and capacity. The next three give the run from seed 1: the chosen items, numbered from 0, their total value and weight, and the evaluations, with the optimum that dynamic programming finds. The last two lines give the runs from seeds 1 to 20: how many reach the optimum, and after how many evaluations (the median); and how many reach the optimum of the strongly correlated instance. Copies of a parent inherit its score, so a generation of 200 needs fewer than 200 evaluations. The problem is evaluated in Rust in both languages, so both print the same.

The project page plays this run back.

Good results

The optimum is 20,849: 32 items that weigh 12,551. The run from seed 1 finds it after 6,864 evaluations, and so do all 20 runs from seeds 1 to 20, after a median of 6,936. Over seeds 1 to 200, every run found it, within 16,536 evaluations; on the instances of seeds 1 to 5, 997 of 1,000 runs (200 each) did.

The strongly correlated instance, optimum 16,020, is another matter: the same GA reaches it from 2 of the 20 seeds, and the other runs stall from 1 to 115 below it, within 0.7%. Pisinger's hard classes are hard for genetic algorithms too.

Reference: Pisinger, D. (2005). Where are the hard knapsack problems? Computers & Operations Research 32(9): 2271-2284.

Known optimum: 20849 (total value, by dynamic programming)

Source: examples/knapsack

Interactive run: tachsin.gr/projects/genoxide/examples/knapsack

cargo run --release --example knapsack

//! 0/1 knapsack: choose items with the highest total value that fit in the knapsack, on an
//! instance of 50 items drawn from Pisinger's uncorrelated class.
//!
//! Shows a constraint with Deb's feasibility rules: the fitness is the value and how far the
//! weight exceeds the capacity, so overweight selections still guide the search towards the
//! feasible ones. The instance is genoxide's `problems::binary::Knapsack`, generated from seed 1,
//! whose optimum dynamic programming finds. A run from seed 1 stops at it; then runs from seeds 1
//! to 20 count how often the GA reaches it, and, as a contrast, how often it reaches the optimum
//! of an instance of Pisinger's strongly correlated class, which is harder.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example knapsack
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::binary::{Knapsack, KnapsackClass};

const ITEMS: usize = 50;
const SEEDS: u64 = 20;

// the genetic algorithm from `seed`
fn ga(knapsack: &Knapsack, seed: u64) -> Result<Ga<Binary, Tournament, UniformCrossover, BitFlip>> {
    Ga::builder(knapsack.representation())
        .population_size(200)
        .select(Tournament::new(3)?)
        .crossover(UniformCrossover::new())
        .mutate(BitFlip::per_gene(1.0 / ITEMS as f64)?)
        .seed(seed)
        .build()
}

// stops at the optimum that dynamic programming finds, or once the search stalls
fn stop(optimum: f64) -> Stop {
    Stop::target(optimum)
        .or(Stop::stagnation(200))
        .or(Stop::generations(2_000))
}

// the runs from seeds 1 to 20 that reach the optimum, and their median evaluations
fn seeds(knapsack: &Knapsack, optimum: f64) -> Result<(usize, f64)> {
    let mut evaluations = Vec::new();
    for seed in 1..=SEEDS {
        let outcome = Engine::new(ga(knapsack, seed)?, knapsack.clone())
            .stop_when(stop(optimum))
            .run()?;
        if outcome.stop_reason() == StopReason::Target {
            evaluations.push(outcome.evaluations() as f64);
        }
    }
    evaluations.sort_by(f64::total_cmp);
    let (count, middle) = (evaluations.len(), evaluations.len() / 2);
    let median = match count {
        0 => f64::NAN,
        n if n % 2 == 1 => evaluations[middle],
        _ => (evaluations[middle - 1] + evaluations[middle]) / 2.0,
    };
    Ok((count, median))
}

fn main() -> Result<()> {
    let knapsack = Knapsack::generator(KnapsackClass::Uncorrelated, ITEMS)
        .seed(1)
        .generate()?;
    let optimum = knapsack.optimum().expect("small enough").value();
    let total: u64 = knapsack.weights().iter().sum();
    println!(
        "{ITEMS} uncorrelated items (R = 1000, seed 1): total weight {total}, capacity {}",
        knapsack.capacity()
    );

    // with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
    let mut trace = trace::Trace::from_env(&knapsack, optimum);
    let outcome = Engine::new(ga(&knapsack, 1)?, knapsack.clone())
        .stop_when(stop(optimum))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;
    let best = outcome.best_genome();
    let items: Vec<usize> = (0..ITEMS)
        .filter(|&item| best.get(item) == Some(true))
        .collect();
    let (weight, value) = knapsack.totals(best);
    println!("items {items:?}");
    println!("value {value}, weight {weight} of {}", knapsack.capacity());
    println!(
        "after {} evaluations; the optimum, by dynamic programming, is {optimum}",
        outcome.evaluations()
    );

    let (reached, median) = seeds(&knapsack, optimum)?;
    println!(
        "\nseeds 1 to {SEEDS}: {reached} reach {optimum}, after a median of {median:.1} evaluations"
    );
    let strong = Knapsack::generator(KnapsackClass::StronglyCorrelated, ITEMS)
        .seed(1)
        .generate()?;
    let strong_optimum = strong.optimum().expect("small enough").value();
    let (reached, _) = seeds(&strong, strong_optimum)?;
    println!(
        "contrast, {ITEMS} strongly correlated items (seed 1): {reached} of {SEEDS} reach its \
         optimum, {strong_optimum}"
    );
    trace.write();
    Ok(())
}

python examples/knapsack/main.py

"""0/1 knapsack: choose items with the highest total value that fit in the knapsack, on an
instance of 50 items drawn from Pisinger's uncorrelated class.

Shows a constraint with Deb's feasibility rules: the fitness is the value and how far the weight
exceeds the capacity, so overweight selections still guide the search towards the feasible ones.
The instance is genoxide's problems.binary.Knapsack, generated from seed 1, which run evaluates in
Rust, and whose optimum dynamic programming finds. A run from seed 1 stops at it; then runs from
seeds 1 to 20 count how often the GA reaches it, and, as a contrast, how often it reaches the
optimum of an instance of Pisinger's strongly correlated class, which is harder.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.

    python examples/knapsack/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

ITEMS = 50
SEEDS = 20


def ga(knapsack, seed):
    """The genetic algorithm from ``seed``."""
    return gx.Ga(
        knapsack.genome,
        population_size=200,
        select=gx.Tournament(3),
        crossover=gx.UniformCrossover(),
        mutation=gx.BitFlip(rate=1 / ITEMS),
        seed=seed,
    )


def run(knapsack, seed, optimum, on_generation=None):
    """A run from ``seed``: it stops at the optimum that dynamic programming finds, or once the
    search stalls."""
    return ga(knapsack, seed).run(
        knapsack,
        target=optimum,
        stagnation=200,
        generations=2_000,
        on_generation=on_generation,
    )


def seeds(knapsack, optimum):
    """The runs from seeds 1 to 20 that reach the optimum, and their median evaluations."""
    evaluations = sorted(
        result.evaluations
        for result in (run(knapsack, seed, optimum) for seed in range(1, SEEDS + 1))
        if result.stop_reason == "target"
    )
    middle = len(evaluations) // 2
    if not evaluations:
        return 0, float("nan")
    if len(evaluations) % 2:
        return len(evaluations), float(evaluations[middle])
    return len(evaluations), (evaluations[middle - 1] + evaluations[middle]) / 2


knapsack = gx.problems.binary.Knapsack(ITEMS, "uncorrelated", seed=1)
optimum = knapsack.optimum.value
weights, values = knapsack.weights, knapsack.profits
print(
    f"{ITEMS} uncorrelated items (R = 1000, seed 1): total weight {weights.sum()}, "
    f"capacity {knapsack.capacity}"
)

# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(knapsack, optimum)
result = run(knapsack, 1, optimum, trace.on_generation)
best = result.best_genome
print(f"items {np.flatnonzero(best).tolist()}")
print(f"value {values[best].sum()}, weight {weights[best].sum()} of {knapsack.capacity}")
print(
    f"after {result.evaluations} evaluations; the optimum, by dynamic programming, is "
    f"{optimum:.0f}"
)

reached, median = seeds(knapsack, optimum)
print(
    f"\nseeds 1 to {SEEDS}: {reached} reach {optimum:.0f}, after a median of {median:.1f} "
    "evaluations"
)
strong = gx.problems.binary.Knapsack(ITEMS, "strongly_correlated", seed=1)
strong_optimum = strong.optimum.value
reached, _ = seeds(strong, strong_optimum)
print(
    f"contrast, {ITEMS} strongly correlated items (seed 1): {reached} of {SEEDS} reach its "
    f"optimum, {strong_optimum:.0f}"
)
trace.write()

What it prints, from a seeded run:

50 uncorrelated items (R = 1000, seed 1): total weight 25397, capacity 12572
items [0, 2, 5, 6, 7, 10, 14, 15, 16, 17, 18, 19, 21, 22, 26, 28, 29, 30, 31, 32, 33, 34, 36, 37, 39, 40, 43, 45, 46, 47, 48, 49]
value 20849, weight 12551 of 12572
after 6864 evaluations; the optimum, by dynamic programming, is 20849

seeds 1 to 20: 20 reach 20849, after a median of 6936.0 evaluations
contrast, 50 strongly correlated items (seed 1): 2 of 20 reach its optimum, 16020