Quadratic knapsack problem¶
A capacity-constrained item-selection optimization with pairwise and optional individual profits.
Core Idea¶
The quadratic knapsack problem chooses items under a capacity limit while maximizing pairwise interaction value, with optional individual-item profits. In its common 0–1 form, each item is included or omitted; the broader name can also cover declared quantity variants. The pair terms are constitutive. If all are zero, the model reduces to ordinary linear knapsack. If capacity disappears, it is not a knapsack problem.
In a worked binary example, items A and C have weights 2 each, individual profits 3 and 2, and joint profit 5; together they fit capacity 4 and yield 10. B has weight 3 and profit 4. This illustrates how an interaction can change the preferred feasible set. QKPLIB publishes larger instances with capacities, weights and quadratic coefficients for solver comparisons, an attested research use rather than a claim of field deployment. The problem is an Optimization subtype: it specifies decisions, objective, constraints and optimality sense. A heuristic's feasible score is not automatically a certified global optimum, and invented pair synergies should not be treated as measured business benefits.
Scope of Application¶
These uses declare variables, pair coefficients, capacity and solution status.
- Combinatorial optimization. Compare exact or heuristic methods under a common quadratic objective.
- Benchmark research. Use documented instance sets with disclosed coefficient and capacity data.
- Project selection models. Represent pair synergies only when their coefficients are defensible.
- Complexity analysis. Study tractability under declared binary, bounded-copy or coefficient restrictions.
Clarity¶
Identify item decisions, weights, capacity, optional singleton coefficients and a nonzero pair term. Linear knapsack is the nearest miss because all interaction terms vanish. State whether decisions are 0–1 or another permitted quantity form, and whether the reported score is feasible, heuristic or proved optimal.
Manages Complexity¶
Pairwise effects couple item decisions: an item's marginal value depends on what else is selected. The quadratic objective compresses these dependencies into coefficients while the capacity still filters feasible sets. That compact formalism can hide estimation uncertainty in real applications and algorithmic difficulty in large instances. Keeping the objective, feasible set and solution guarantee separate prevents a benchmark table from masquerading as a universal decision recipe.
Abstract Reasoning¶
- Specify item decisions and whether each is binary or permits copies.
- Write weights and a single capacity condition for feasibility.
- Separate singleton profit terms from pairwise interaction coefficients.
- Evaluate a candidate set using both parts of the objective.
- Distinguish a feasible or heuristic score from a proved optimum.
Knowledge Transfer¶
The variable–objective–constraint structure transfers directly to prime Optimization. Pair-profit models can be used for projects or items only when joint value can be justified, and a synthetic benchmark cannot certify a field benefit. Dropping pair terms yields ordinary knapsack; dropping capacity yields another quadratic selection problem. These stopping points keep the QKP label mathematically exact.
Relationships to Other Abstractions¶
Current abstraction Quadratic knapsack problem Domain-specific
Parents (1) — more general patterns this builds on
-
Quadratic knapsack problem is a kind of Optimization Prime
QKP maximizes singleton-plus-pair profit over item decisions constrained by capacity.
Hierarchy path (1) — routes to 1 parentless root
- Quadratic knapsack problem → Optimization
Neighborhood in Abstraction Space¶
Quadratic knapsack problem sits in a moderately populated region (40th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Combinatorial Optimization & Game Problems (12 abstractions)
Nearest neighbors
- Partition problem — 0.88
- Matroid-Constrained Number Partitioning — 0.88
- General equilibrium theory — 0.87
- Two-Moment Decision Model — 0.87
- ÉLECTRE — 0.87
Computed from structural-signature embeddings · 2026-10-08