Quadratic knapsack problem¶

A capacity-constrained item-selection optimization with pairwise and optional individual profits.

Version: v1 · 2026-09-28 · History
Domain-specific #: 11592
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomain: Combinatorial Optimization → Operations Research
Aliases: QKP

Core Idea¶

The quadratic knapsack problem extends capacity-constrained selection by making some selected pairs contribute joint profit. Each item has a weight; its individual-profit coefficient may be positive or zero, while a nonzero pair coefficient changes the objective when both members are chosen. The 0–1 formulation uses binary inclusion, but the title also covers declared quantity variants. If every pair coefficient is zero, the objective is additive and the ordinary knapsack problem remains. If capacity is absent, the knapsack constraint has disappeared.

A three-item worked case shows the distinction: A and C together fit capacity 4 and earn 3+2+5=10 because their interaction adds 5. QKPLIB supplies real published benchmark instances in which researchers test solvers on item, weight, capacity and quadratic-profit data. Benchmarking is an attested use of the formal model, not proof that the generated cases describe a particular industrial choice or that every proposed solution is globally optimal. The abstraction is a typed optimization problem, not an algorithm for solving it.

Structural Signature¶

Sig role-phrases:

Item decisions — Specifies admissible quantities or binary inclusion choices for a finite item set. It is constitutive. Counterfactual: A task with no selectable items is not a knapsack problem.
Weight and capacity — Bounds feasible selections by the sum of item weights relative to one capacity. It is constitutive. Counterfactual: Unconstrained pair-profit maximization loses the knapsack structure.
Singleton profits — Specify each item's independent coefficient, which may be zero in a restricted quadratic variant. It is diagnostic. Counterfactual: Pair terms alone can define a restricted variant when its zero-singleton convention is explicit.
Pair interaction profits — Adds a quadratic contribution when two corresponding items are selected. It is constitutive. Counterfactual: If all interaction coefficients vanish, the problem collapses to linear knapsack.
Optimality and variant convention — States maximize-under-capacity and whether decisions are binary or permit bounded copies. It is boundary. Counterfactual: A heuristic solution is not automatically a proved global optimum.

What It Is Not¶

Not ordinary knapsack. Nonzero pair profit changes the objective from additive to quadratic.
Not unconstrained pair selection. Capacity remains a defining feasibility condition.
Not only the 0–1 subtype. Decision-domain variants must be stated rather than silently excluded.
Not a solver. An algorithm or heuristic addresses the problem but is not its identity.
Closest near-miss. Ordinary 0–1 knapsack is the closest near miss: it has binary choices and capacity but additive profits only.

Scope of Application¶

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¶

Write decision variables, item weights, capacity, the possibly zero singleton coefficients and at least one nonzero pair term before naming QKP. Linear knapsack is the nearest miss because joint inclusion adds no special value. An instance score is a feasible solution value unless an optimality guarantee is supplied. The 0–1 form is common but does not exhaust the broader problem family.

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.

Examples¶

Canonical¶

Take binary items A, B and C with weights 2, 3 and 2, capacity 4, and individual profits 3, 4 and 2. Selecting A and C earns an additional pair profit of 5, so A+C is feasible and has value 10; B alone has value 4. The example displays the capacity and interaction terms without claiming that a particular algorithm discovered or certified the optimum for larger instances.

Mapped back: Item decisions → binary inclusion of A, B and C; Weight and capacity → weights 2, 3, 2 against capacity 4; Singleton profits → 3, 4, 2 respectively; Pair interaction profits → extra 5 only when A and C are selected; Optimality and variant convention → finite 0–1 worked instance; A+C is best among its feasible subsets.

Applied / In Practice¶

QKPLIB publishes test instances of the quadratic knapsack problem from 100 to 2000 items, recording capacities, weights and item/pair profits so optimization methods can be compared on common inputs. This is a documented computational-research application of QKP, not evidence that the generated instances represent a particular real investment portfolio or that any solver is always exact.

Mapped back: Item decisions → QKPLIB item inclusion variables; Weight and capacity → recorded instance weights and capacity; Singleton profits → instance item-profit coefficients; Pair interaction profits → published quadratic coefficient matrix; Optimality and variant convention → benchmark formulation and solver comparisons, not unearned optimality claim.

Structural Tensions¶

T1 — Pair Synergy versus Independent Value. Joint inclusion can change value beyond the sum of item profits; replacing coefficients with additive approximations can change the optimum.

Diagnostic: Would removing pair terms change the selected set?

T2 — Problem Specification versus Solver Guarantee. A mathematically specified maximum and a heuristic candidate are different objects.

Diagnostic: Is the result proven optimal or only a feasible benchmark score?

Structural–Framed Character¶

QKP lies toward the structural end: choice variables, quadratic value and capacity can be stated without a particular material carrier. Evaluative weight: profit is a declared objective, not intrinsic worth. Human-practice-bound: a modeler chooses coefficients; the mathematical feasible set follows from them. Institutional origin: benchmarks standardize tests but do not create the problem form. Vocabulary travels: interaction and budget occur widely; this exact quadratic knapsack structure has specific constraints. Import versus recognize: any correctly typed instance is literal; calling a vague synergistic decision QKP without coefficients is analogy.

Prime Optimization is a verified strict parent: QKP has decisions, objective, capacity constraints and a stated optimality sense. Its character: a structural discrete-optimization subtype specified by pairwise profits and a knapsack bound.

Structural Core vs. Domain Accent¶

The optimization skeleton is general; quadratic knapsack is a specific formal contract.

What is skeletal. Choices are evaluated by an objective within a feasible set, and an optimum is sought. This exactly instantiates the current Optimization prime.

What is domain-bound. The candidates are items with weights, one capacity, and objective coefficients for both singletons and selected pairs. A QKPLIB matrix is meaningful only under that decision and constraint convention.

Why this does not clear the prime bar. Optimization already captures the cross-domain reasoning. Quadratic pair terms plus knapsack capacity are a narrower mathematical problem class; abstracting them away would turn the entry into generic optimization and erase its closest linear-knapsack boundary.

This entry is a kind of Optimization.

Parent — optimization. QKP maximizes a specified objective over a capacity-constrained choice set.
Related — ordinary knapsack. It is the zero-pair-profit limit, not the full quadratic case.
Related — algorithm. Solvers search for answers but do not define the problem.

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 (40^th 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

Not to Be Confused With¶

Linear knapsack. Tell: Is any pair coefficient nonzero?
Unconstrained quadratic selection. Tell: Where is the capacity bound?
0–1 subtype. Tell: Are quantities restricted to binary choices?
Heuristic result. Tell: Has global optimality actually been established?

References¶

Gallo, Hammer, and Simeone, Quadratic Knapsack Problems, Mathematical Programming Studies 12 (1980): https://doi.org/10.1007/BFb0120892
QKPLIB, Quadratic Knapsack Problem Library, Mendeley Data (2023): https://data.mendeley.com/datasets/82pxy6yv49/1
Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Quadratic_knapsack_problem (revision 1314216629).