[Model] IntegerKnapsack

[isPANN]

Important

Build as optimization, not decision. Value = Max<i64>.
Objective: Maximize total value Σ v(u)·c(u) subject to Σ s(u)·c(u) ≤ B.
Do not add a bound/threshold field — let the solver find the optimum directly. See #765.

Motivation

INTEGER KNAPSACK (P216) from Garey & Johnson, A6 MP10. A classical NP-complete problem that generalizes the standard 0-1 Knapsack by allowing each item to be used with any non-negative integer multiplicity c(u), rather than just 0 or 1. This is also known as the "unbounded knapsack problem" in much of the literature. It remains NP-complete even in the special case where s(u) = v(u) for all items, which connects it directly to SUBSET SUM. Solvable in pseudo-polynomial time by dynamic programming, and polynomial time when |U| = 2 (Hirschberg and Wong, 1976).

Associated rules:

• R160: SUBSET SUM -> INTEGER KNAPSACK (establishes NP-completeness via Lueker 1975)

Reduction Rule Crossref:

• [Rule] SUBSET SUM to INTEGER KNAPSACK #521: [Rule] SUBSET SUM to INTEGER KNAPSACK
• [Rule] IntegerKnapsack to ILP #781: [Rule] IntegerKnapsack to ILP (direct ILP formulation)

Definition

Name: IntegerKnapsack

Reference: Garey & Johnson, Computers and Intractability, A6 MP10

Mathematical definition (GJ decision form):

INSTANCE: Finite set U, for each u ∈ U a size s(u) ∈ Z⁺ and a value v(u) ∈ Z⁺, and positive integers B and K.
QUESTION: Is there an assignment of a non-negative integer c(u) to each u ∈ U such that Σᵤ∈U c(u)·s(u) ≤ B and such that Σᵤ∈U c(u)·v(u) ≥ K?

Optimization formulation (used in implementation):

Given a finite set U with sizes s(u) ∈ Z⁺ and values v(u) ∈ Z⁺ for each u ∈ U, and a capacity B ∈ Z⁺, find an assignment of non-negative integers c(u) to each u ∈ U that maximizes Σᵤ∈U c(u)·v(u) subject to Σᵤ∈U c(u)·s(u) ≤ B.

Variables

• Count: n = |U| (one variable per item in the set U)
• Per-variable domain: {0, 1, 2, ..., floor(B / s(u))} — non-negative integers, bounded above by floor(B / min_size) in the worst case. For the codebase representation, we use a discretized domain where each variable c(u) ranges from 0 to floor(B / s(u)).
• Meaning: c(u) is the non-negative integer multiplicity assigned to item u. The assignment is feasible if the total size Σ c(u)·s(u) ≤ B, and the objective is to maximize total value Σ c(u)·v(u).

Schema (data type)

Type name: IntegerKnapsack
Variants: none (operates on a generic item set with sizes and values)

Field	Type	Description
sizes	Vec<i64>	Size s(u) for each item u ∈ U
values	Vec<i64>	Value v(u) for each item u ∈ U
capacity	i64	Knapsack capacity B (total size budget)

Notes:

• Implemented as an optimization problem with Value = Max<i64>, maximizing total value subject to capacity. Follows the same pattern as the existing Knapsack model.
• Key difference from the existing Knapsack (0-1 Knapsack): each item can be used with integer multiplicity c(u) ≥ 0, not just 0 or 1. The configuration space per variable is larger: dims() returns [floor(B/s(0))+1, floor(B/s(1))+1, ...] instead of [2, 2, ..., 2].
• Key getter methods needed: num_items() (= |U|), capacity() (= B).

Complexity

• Decision complexity: Weakly NP-complete (Lueker, 1975; transformation from SUBSET SUM). Remains NP-complete even when s(u) = v(u) for all u. Not strongly NP-complete — solvable in pseudo-polynomial time.
• Best known exact algorithm: Dynamic programming in O(n · B) time and O(B) space, where n = |U| and B is the capacity. This is pseudo-polynomial time. The DP recurrence is: dp[w] = max over all u of (dp[w - s(u)] + v(u)) for w = 1, ..., B, with dp[0] = 0. Each item can be used multiple times naturally in this formulation.
• declare_variants! complexity string: "(capacity + 1)^num_items" — worst-case brute-force bound where each item can be used 0 to capacity times.
• Special case |U| = 2: Solvable in polynomial time (Hirschberg and Wong, 1976) via a number-theoretic algorithm exploiting the structure of linear Diophantine equations.
• Approximation: Admits an FPTAS. For any ε > 0, a (1-ε)-approximation can be computed in O(n / ε) time using LP relaxation and rounding techniques.
• References:
  • G. S. Lueker (1975). "Two NP-complete problems in nonnegative integer programming." Computer Science Laboratory, Princeton University. Original NP-completeness proof.
  • D. S. Hirschberg and C. K. Wong (1976). "A polynomial-time algorithm for the knapsack problem with two variables." JACM 23, pp. 147–154.

Extra Remark

Full book text:

INSTANCE: Finite set U, for each u ∈ U a size s(u) ∈ Z⁺ and a value v(u) ∈ Z⁺, and positive integers B and K.
QUESTION: Is there an assignment of a non-negative integer c(u) to each u ∈ U such that Σᵤ∈U c(u)·s(u) ≤ B and such that Σᵤ∈U c(u)·v(u) ≥ K?

Reference: [Lueker, 1975]. Transformation from SUBSET SUM.
Comment: Remains NP-complete if s(u) = v(u) for all u ∈ U. Solvable in pseudo-polynomial time by dynamic programming. Solvable in polynomial time if |U| = 2 [Hirschberg and Wong, 1976].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all multiplicity vectors (c(u_1), ..., c(u_n)) with 0 ≤ c(u_i) ≤ floor(B/s(u_i)); check feasibility and compute total value.)
• It can be solved by reducing to integer programming. (ILP with integer variables c_i ≥ 0 for each item; constraint Σ c_i · s_i ≤ B; objective maximize Σ c_i · v_i. See companion issue.)
• Other: Dynamic programming in O(n·B) pseudo-polynomial time.

Example Instance

Input:
U = {u₁, u₂, u₃, u₄, u₅} (n = 5 items)
Sizes: s(u₁) = 3, s(u₂) = 4, s(u₃) = 5, s(u₄) = 2, s(u₅) = 7
Values: v(u₁) = 4, v(u₂) = 5, v(u₃) = 7, v(u₄) = 3, v(u₅) = 9
Capacity B = 15

Optimal solution: c(u₁) = 0, c(u₂) = 0, c(u₃) = 1, c(u₄) = 5, c(u₅) = 0

• Total size: 0·3 + 0·4 + 1·5 + 5·2 + 0·7 = 15 ≤ 15 ✓
• Total value: 0·4 + 0·5 + 1·7 + 5·3 + 0·9 = 22 (optimal)

Alternative optimal: c(u₁) = 1, c(u₂) = 0, c(u₃) = 0, c(u₄) = 6, c(u₅) = 0

• Total size: 1·3 + 0·4 + 0·5 + 6·2 + 0·7 = 15 ≤ 15 ✓
• Total value: 1·4 + 0·5 + 0·7 + 6·3 + 0·9 = 22 (optimal)

Suboptimal feasible solutions (examples):

• c = (0, 0, 3, 0, 0): size = 15, value = 21
• c = (0, 0, 0, 4, 1): size = 15, value = 21
• c = (5, 0, 0, 0, 0): size = 15, value = 20
• c = (0, 0, 0, 7, 0): size = 14, value = 21

Note how the same item u₃ can be used 3 times — this is impossible in 0-1 Knapsack. The instance has 103 feasible solutions across 21 distinct objective values (verified by brute-force enumeration), making it suitable for round-trip testing.

Negative instance:
Same items but B = 5. Best achievable: c(u₃) = 1 gives value 7. No combination with total size ≤ 5 can achieve value ≥ 20.

References

• [Lueker, 1975]: G. S. Lueker (1975). "Two NP-complete problems in nonnegative integer programming." Computer Science Laboratory, Princeton University. Original NP-completeness proof.
• [Hirschberg and Wong, 1976]: D. S. Hirschberg and C. K. Wong (1976). "A polynomial-time algorithm for the knapsack problem with two variables." JACM 23, pp. 147–154.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; distinct from existing 0-1 Knapsack
Non-trivial	✅ Pass	Different variable domains and feasibility structure from existing Knapsack
Correctness	❌ Fail	Claims "NP-complete in the strong sense" — this is incorrect
Well-written	⚠️ Warn	Schema missing target K field for decision version; optimization/satisfaction modeling ambiguous

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

The problem IntegerKnapsack does not exist in the current codebase. The existing Knapsack model is a 0-1 knapsack with binary variables (dims() returns [2; n]). IntegerKnapsack allows non-negative integer multiplicities, giving a genuinely different configuration space (dims() returns [floor(B/s(i))+1, ...]). The issue identifies an associated rule (R160: Subset Sum -> Integer Knapsack) that would connect it to the reduction graph. Motivation is well-articulated. Pass.

Non-trivial

This is genuinely distinct from the existing Knapsack model. The key difference is structural: Knapsack uses binary selection variables (include/exclude each item), while IntegerKnapsack uses integer multiplicity variables (how many copies of each item). The feasibility constraint and objective are mathematically different because items can be reused. Not a variant or renaming. Pass.

Correctness

• Lueker (1975): Verified as a real reference. "Two NP-complete problems in nonnegative integer programming," Technical Report TR-178, Computer Science Laboratory, Princeton University. The reference is widely cited in the literature for establishing NP-completeness of integer knapsack problems.

• Hirschberg and Wong (1976): Verified. "A polynomial-time algorithm for the knapsack problem with two variables," JACM 23(1), pp. 147–154. Paper confirmed to exist and the claim matches.

• CRITICAL ERROR: "NP-complete in the strong sense." The issue states the Integer Knapsack is "NP-complete in the strong sense." This is incorrect. The Integer Knapsack (unbounded knapsack) is only weakly NP-complete. The issue itself correctly states that it is "solvable in pseudo-polynomial time by dynamic programming" with O(n·B) time. By definition, a problem with a pseudo-polynomial time algorithm is weakly NP-complete, not strongly NP-complete. A strongly NP-complete problem (like Bin Packing or 3-Partition) remains NP-complete even when all numerical values are bounded by a polynomial in the input size. The Integer Knapsack does not have this property — its O(n·B) DP algorithm is polynomial when B is polynomially bounded.

Fail — the strong NP-completeness claim is factually wrong and must be corrected.

Well-written

Strengths:

• Examples are well-worked with both positive and negative instances
• Mathematical definition matches Garey & Johnson verbatim
• Variables section clearly explains the domain structure
• Both brute-force and ILP solver paths identified

Warnings:

1. Schema missing target field. The GJ definition is a decision problem asking whether total value ≥ K is achievable. The Schema only has sizes, values, and capacity — no field for the target value K. If modeled as a satisfaction problem (Metric = bool), K must be stored. If modeled as an optimization problem (Metric = SolutionSize), K is not needed but the issue should be explicit about which modeling choice is intended.

2. Optimization vs. satisfaction ambiguity. The issue notes it "can be modeled as" either, but should commit to one for implementation. The existing Knapsack in the codebase uses the optimization formulation (Metric = SolutionSize, direction = Maximize). The new IntegerKnapsack should likely follow the same pattern for consistency.

3. Complexity string for declare_variants!. The issue gives O(n·B) pseudo-polynomial time but does not provide the worst-case exact exponential complexity needed for the declare_variants! macro. The existing Knapsack uses "2^(num_items / 2)" (meet-in-the-middle). A similar bound or the brute-force bound should be stated.

Recommendations

• Remove the "NP-complete in the strong sense" claim and replace with "weakly NP-complete" (since a pseudo-polynomial time algorithm exists).
• Commit to the optimization formulation (maximizing total value subject to capacity) to be consistent with the existing Knapsack model.
• If keeping the decision version, add a target field (K) to the Schema.
• Provide a concrete complexity string for declare_variants!.

[isPANN]

Implementation note: build as optimization

This model should be implemented as an optimization problem (Value = Max<i64> or similar), not a decision problem with a bound field.

• Objective: Maximize total value Σ v(u)·c(u) subject to Σ s(u)·c(u) ≤ B
• Do not add a value_target or bound threshold — let the solver find the optimum directly
• Follows the same pattern as the existing Knapsack model (which uses Max<i64>)

See #765 for context on the decision-vs-optimization policy.

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12 — 2 passed, 1 failed (Correctness), 1 warning (Well-written). Re-checking with --force.

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem; ILP solving claimed but no companion [Rule] IntegerKnapsack to ILP issue linked
Non-trivial	✅ Pass	Different variable domains and configuration space from existing 0-1 Knapsack
Correctness	❌ Fail	Still claims "NP-complete in the strong sense" — contradicted by the O(n·B) pseudo-polynomial DP
Well-written	⚠️ Warn	Example framed as decision (K=20) but model is optimization (Max); missing optimal value; no declare_variants! complexity string

Overall: 1 passed, 1 failed, 2 warnings

Changes from previous check: Usefulness downgraded Pass → Warn (ILP companion issue missing). Correctness Fail unchanged. Well-written Warn details expanded with Python-verified example analysis.

---

Usefulness

IntegerKnapsack does not exist in the codebase. The existing Knapsack is a 0-1 knapsack with binary selection variables (dims() = [2; n]). The issue identifies an associated rule R160: SubsetSum → IntegerKnapsack, and SubsetSum exists in the codebase (reachable from KSatisfiability).

Warning: The issue checks [x] It can be solved by reducing to integer programming, but no companion [Rule] IntegerKnapsack to ILP issue exists or is linked. Per project convention, if direct ILP solvability is claimed, a companion ILP rule issue should be filed and cross-referenced.

Non-trivial

Genuinely distinct from existing Knapsack. Key structural difference: Knapsack uses binary variables (include/exclude), while IntegerKnapsack uses integer multiplicity variables with dims() = [floor(B/s(i))+1, ...]. The feasibility constraint and objective differ because items can be reused. Pass.

Correctness

References verified:

• Lueker (1975): "Two NP-complete problems in nonnegative integer programming," TR-178, Princeton University. Verified — widely cited for NP-completeness of integer knapsack.
• Hirschberg & Wong (1976): "A polynomial-time algorithm for the knapsack problem with two variables," JACM 23, pp. 147–154. Verified — polynomial-time algorithm for |U|=2 confirmed.
• Garey & Johnson, A6 MP10: GJ number could not be independently verified from web sources. The codebase uses MP9 for 0-1 Knapsack and MP12 for Partially Ordered Knapsack, making MP10 for Integer Knapsack plausible but unconfirmed.

CRITICAL ERROR (unchanged from previous check): The issue states "NP-complete in the strong sense." This is factually incorrect. The issue itself correctly notes an O(n·B) pseudo-polynomial time DP algorithm. By definition, a problem with a pseudo-polynomial time algorithm is only weakly NP-complete. A strongly NP-complete problem (e.g., 3-Partition, Bin Packing) has no pseudo-polynomial algorithm unless P=NP. This must be corrected to "weakly NP-complete."

Fail — the strong NP-completeness claim contradicts the pseudo-polynomial DP.

Well-written

Strengths:

• Mathematical definition matches Garey & Johnson verbatim
• Variables section clearly explains the per-item domain structure
• Schema is clean with 3 fields matching the optimization formulation
• Both brute-force and ILP solver paths identified
• Example has 5 items, 103 feasible solutions, 21 distinct objective values — excellent for round-trip testing

Warnings:

1. Example framed as decision, not optimization. The banner says "Build as optimization (Value = Max<i64>)" but the example only checks the decision threshold K=20. Python brute-force verification confirms:

   • True optimal value = 22 (assignments: [0,0,1,5,0] or [1,0,0,6,0])
   • Claimed "Solution" c=(0,0,3,0,0) gives value 21 — feasible but not optimal
   • Claimed "Alternative solution" c=(0,0,1,5,0) gives value 22 — this is the optimum but isn't labeled as such
   • The example should state: "Optimal value: 22, achieved by c(u₄)=5, c(u₃)=1"

2. Missing declare_variants! complexity string. The issue gives the pseudo-polynomial O(n·B) bound but not the worst-case exact exponential complexity needed for the macro. The existing Knapsack uses "2^(num_items / 2)" (meet-in-the-middle). A comparable bound should be provided.

3. No Reduction Rule Crossref section. ILP solvability is claimed but no [Rule] IntegerKnapsack to ILP companion issue is linked.

Recommendations

• Fix "NP-complete in the strong sense" → "weakly NP-complete" (the pseudo-poly DP proves this)
• Reframe the example as optimization: label the optimal solution and state optimal value = 22
• Add a declare_variants! complexity string (e.g., "2^(num_items / 2)" for meet-in-the-middle, or document a better bound)
• File a [Rule] IntegerKnapsack to ILP companion issue and cross-reference it

[isPANN]

Fix-issue changelog

• Fixed "NP-complete in the strong sense" → "Weakly NP-complete" (pseudo-polynomial DP proves it's not strongly NP-complete)
• Added declare_variants! complexity string: "(capacity + 1)^num_items"
• Reframed example as optimization: labeled optimal value = 22 (verified by brute-force Python script), added alternative optimal and suboptimal solutions
• Committed schema to optimization formulation (Value = Max<i64>), removed ambiguous decision-vs-optimization language
• Added explicit optimization formulation in Definition section alongside GJ decision form
• Added Reduction Rule Crossref section linking [Rule] SUBSET SUM to INTEGER KNAPSACK #521 and [Rule] IntegerKnapsack to ILP #781
• Filed companion issue [Rule] IntegerKnapsack to ILP #781 [Rule] IntegerKnapsack to ILP

Applied by /fix-issue.