[Model] PartiallyOrderedKnapsack

[isPANN]

Motivation

PARTIALLY ORDERED KNAPSACK (P218) from Garey & Johnson, A6 MP12. An NP-complete (strong sense) knapsack variant where items are subject to a partial order: including an item in the knapsack requires including all its predecessors. This models precedence-constrained selection problems arising in manufacturing scheduling, project selection, mining operations, and network design. The precedence constraints make the problem significantly harder than standard 0-1 Knapsack — it is NP-complete in the strong sense even when s(u) = v(u) for all u, whereas standard 0-1 Knapsack is only weakly NP-complete. Also known as the Precedence Constrained Knapsack Problem (PCKP) in the optimization literature.

Associated rules:

• R162: CLIQUE -> PARTIALLY ORDERED KNAPSACK (establishes NP-completeness via Garey and Johnson)

Definition

Name: PrecedenceOrderedKnapsack

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

Mathematical definition:

INSTANCE: Finite set U, partial order < on U, for each u ∈ U a size s(u) ∈ Z⁺ and a value v(u) ∈ Z⁺, positive integer B (capacity).
OBJECTIVE: Find a subset U' ⊆ U that maximizes Σᵤ∈U' v(u) subject to: (1) U' is downward-closed (if u ∈ U' and u' < u, then u' ∈ U'), and (2) Σᵤ∈U' s(u) ≤ B.

The constraint "if u ∈ U' and u' < u, then u' ∈ U'" means U' must be a downward-closed set (lower set / order ideal) in the partial order.

Variables

• Count: n = |U| binary variables (one per item)
• Per-variable domain: binary {0, 1} — whether item u is included in U'
• Meaning: x_u = 1 if item u is selected. The configuration (x₁, ..., xₙ) encodes a candidate subset U' ⊆ U. A configuration is feasible if: (a) U' is a downward-closed set (for every u ∈ U', all predecessors of u are also in U'), and (b) Σ s(u)·x_u ≤ B. The objective is to maximize Σ v(u)·x_u over all feasible configurations. Infeasible configurations (violating precedence or capacity) evaluate to SolutionSize::Invalid.

Schema (data type)

Type name: PrecedenceOrderedKnapsack
Variants: none

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
precedences	Vec<(usize, usize)>	Precedence relations: (u', u) means u' < u (u' must be included before u)
capacity	i64	Knapsack capacity B

Notes:

• This is an optimization problem: Metric = SolutionSize<i64>, direction = Maximize. The evaluate() method returns SolutionSize::Valid(total_value) when the configuration is feasible (downward-closed and within capacity), and SolutionSize::Invalid when the configuration violates precedence or capacity constraints.
• The precedences field encodes the Hasse diagram (cover relations) of the partial order. The full partial order is the transitive closure.
• An alternative representation stores the partial order as a DAG adjacency list.
• Key getter methods needed: num_items() (= |U|), num_precedences() (= number of cover relations), capacity() (= B).

Complexity

• Decision complexity: NP-complete in the strong sense (Garey and Johnson; transformation from CLIQUE). Remains NP-complete in the strong sense even when s(u) = v(u) for all u.
• Best known exact algorithm: Branch-and-bound with Lagrangian relaxation bounds. Dynamic programming approaches work when the partial order has special structure. For general partial orders, the problem is strongly NP-hard, so no pseudo-polynomial algorithm exists unless P = NP.
• Special cases:
  • Tree partial orders (Hasse diagram is a tree): solvable in pseudo-polynomial time O(n · B) by tree DP (Garey and Johnson; Johnson and Niemi, 1983).
  • 2-dimensional partial orders: FPTAS exists with running time O(n⁴/ε) for any ε > 0 (Kolliopoulos and Steiner, 2007).
  • Bipartite orders (all elements are either minimal or maximal): NP-complete in the strong sense.
• Approximation: For general partial orders, no FPTAS exists (strongly NP-hard). Johnson and Niemi (1983) gave an FPTAS for tree orders. Kolliopoulos and Steiner extended this to 2-dimensional orders.
• References:
  • M. R. Garey and D. S. Johnson. "Computers and Intractability." Original NP-completeness result.
  • D. S. Johnson and K. A. Niemi (1983). "On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees." Mathematics of Operations Research 8(1), pp. 1–14. Tree DP and FPTAS for tree orders.
  • O. H. Ibarra and C. E. Kim (1975). As cited by Garey & Johnson. (Technical report, University of Minnesota.)
  • S. G. Kolliopoulos and G. Steiner (2007). "Partially-Ordered Knapsack and Applications to Scheduling." Discrete Applied Mathematics 155(8), pp. 889–897.

Extra Remark

Full book text:

INSTANCE: Finite set U, partial order < on U, for each u ∈ U a size s(u) ∈ Z⁺ and a value v(u) ∈ Z⁺, positive integers B and K.
QUESTION: Is there a subset U' ⊆ U such that if u ∈ U' and u' < u, then u' ∈ U', and such that Σᵤ∈U' s(u) ≤ B and Σᵤ∈U' v(u) ≥ K?

Reference: [Garey and Johnson, ——]. Transformation from CLIQUE. Problem is discussed in [Ibarra and Kim, 1975b].
Comment: NP-complete in the strong sense, even if s(u) = v(u) for all u ∈ U. General problem is solvable in pseudo-polynomial time if < is a "tree" partial order [Garey and Johnson, ——].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2ⁿ subsets; filter to downward-closed sets within capacity; return the one with maximum total value.)
• It can be solved by reducing to integer programming. (ILP with binary variables x_u for each item; constraints: x_u ≤ x_{u'} for each precedence u' < u; Σ s(u)·x_u ≤ B; objective maximize Σ v(u)·x_u.)
• Other: Branch-and-bound with Lagrangian relaxation; tree DP for tree orders in O(n·B).

Example Instance

Input:
U = {a, b, c, d, e, f} (n = 6 items)
Partial order (Hasse diagram):

    a       b
   / \      |
  c   d     e
       \   /
        f

Precedences: a < c, a < d, b < e, d < f, e < f
(Meaning: to include c, must include a; to include f, must include both d and e, hence also a and b.)

Sizes: s(a) = 2, s(b) = 3, s(c) = 4, s(d) = 1, s(e) = 2, s(f) = 3
Values: v(a) = 3, v(b) = 2, v(c) = 5, v(d) = 4, v(e) = 3, v(f) = 8
Capacity B = 11

Optimal solution: U' = {a, b, d, e, f}

• Downward-closed check:
  • f ∈ U': predecessors d, e, a, b all in U' ✓
  • d ∈ U': predecessor a ∈ U' ✓
  • e ∈ U': predecessor b ∈ U' ✓
  • a, b: no predecessors ✓
• Total size: 2 + 3 + 1 + 2 + 3 = 11 ≤ 11 ✓
• Total value: 3 + 2 + 4 + 3 + 8 = 20 (maximized)

Why not include c? U' = {a, b, c, d, e, f} has total size = 2+3+4+1+2+3 = 15 > 11 = B. Exceeds capacity. evaluate() returns SolutionSize::Invalid.

Invalid subset: U' = {d, f} — includes f but not e and not b (predecessors of f via e). Not downward-closed. evaluate() returns SolutionSize::Invalid.

Suboptimal feasible subset: U' = {a, d} has size 3 ≤ 11, value 7. evaluate() returns SolutionSize::Valid(7). Feasible but not optimal.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; distinct from existing Knapsack
Non-trivial	✅ Pass	Distinct feasibility constraint (downward-closed sets under partial order) from standard Knapsack
Correctness	⚠️ Warn	Minor reference imprecision; one schema concern
Well-written	⚠️ Warn	Missing target_value field in schema; satisfaction vs optimization ambiguity

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not exist in the current codebase. The existing Knapsack model has no precedence constraints, so this is a genuinely new problem. The motivation is strong — precedence-constrained selection arises in manufacturing, project selection, and mining. The associated rule (CLIQUE → PartiallyOrderedKnapsack) provides graph connectivity.

Non-trivial

PartiallyOrderedKnapsack has a fundamentally different feasibility constraint from standard Knapsack: selected items must form a downward-closed set (order ideal) in the partial order. This is not a simple variant or restriction of the existing Knapsack model — it requires additional data (the partial order) and a qualitatively different feasibility check. The problem is strongly NP-complete (vs weakly NP-complete for standard Knapsack), confirming structural distinction.

Correctness

References verified:

• ✅ Garey & Johnson (1979) — Correctly cited as A6 MP12. The problem definition matches the book's formulation.
• ✅ Johnson & Niemi (1983) — Paper confirmed: "On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees," Mathematics of Operations Research 8(1), pp. 1–14. Claims about tree DP and FPTAS for tree orders match the paper.
• ✅ Kolliopoulos & Steiner (2007) — Paper confirmed: "Partially ordered knapsack and applications to scheduling," Discrete Applied Mathematics 155(8), pp. 889–897. FPTAS for 2-dimensional orders confirmed.
• ⚠️ Ibarra & Kim (1975) — The citation "Scheduling for maximum profit, CS Dept., University of Minnesota" appears to be a technical report. Ibarra and Kim's known 1975 publication is "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems" (JACM). The scheduling paper may be a 1978 publication in Mathematics of Operations Research. This is a minor imprecision since GJ cite it directly.

Schema concern: The issue presents the GJ decision formulation (with threshold K), but the schema omits the target_value field for K. The notes mention it "can also be modeled as optimization," but the issue should commit to one approach. If modeled as satisfaction (Metric = bool), K must be in the schema. If modeled as optimization (maximize value subject to precedence + capacity), K is not needed but the schema should be declared as optimization.

Well-written

Strengths:

• Thorough motivation with real-world applications
• Clear mathematical definition matching GJ verbatim
• Excellent example with positive instance, negative instance, and invalid subset demonstration
• Variables section is well-defined with clear semantics
• Solver methods identified (brute-force and ILP)

Warnings:

1. Schema missing target_value field: The decision formulation requires a threshold K, but the schema has no field for it. Either add target_value: i64 to the schema, or explicitly declare this as an optimization problem (maximize total value subject to precedence + capacity).
2. Satisfaction vs optimization ambiguity: The notes say "This is a satisfaction (decision) problem in the GJ formulation... Can also be modeled as optimization." The implementer needs a clear choice. Recommendation: model as optimization (like existing Knapsack) since it is more natural for the reduction graph and solver integration.
3. Complexity section lacks exact algorithm time bound: The section describes approaches (branch-and-bound, DP for special cases) but does not give a concrete worst-case time complexity string for declare_variants!. For implementation, a specific bound like "2^num_items" (naive) or a tighter bound is needed.
4. Ibarra & Kim citation could be more precise (see Correctness section).

Recommendations

• Decide on optimization vs satisfaction and update the schema accordingly. The existing Knapsack is optimization, so consistency suggests optimization here too.
• Add a concrete complexity string for the general case (e.g., "2^num_items" as a baseline, or cite a better exact algorithm if one exists).
• Consider whether precedences should store the full DAG adjacency list rather than just cover relations, to avoid requiring transitive closure computation at runtime.

[zazabap]

Changelog

Mechanical fix:

• Updated Ibarra & Kim (1975) citation to: "O. H. Ibarra and C. E. Kim (1975). As cited by Garey & Johnson. (Technical report, University of Minnesota.)" — removed the incorrect paper title.

Substantive change (Q1 answer: A — optimization):

• Reframed from satisfaction (Metric = bool) to optimization (Metric = SolutionSize<i64>, direction = Maximize).
• Definition: Changed from decision (QUESTION with target K) to optimization (OBJECTIVE: maximize total value subject to precedence + capacity).
• Variables: Updated to describe feasibility in terms of SolutionSize::Valid(total_value) vs SolutionSize::Invalid.
• Schema: Removed target_value/K threshold field (capacity B is retained). Updated Notes to specify Metric = SolutionSize<i64>, direction = Maximize, and describe evaluate() return values.
• Example: Removed target K=18 and YES/NO framing. Rewritten as optimal solution with value 20. Added suboptimal feasible example showing SolutionSize::Valid(7). Invalid/infeasible cases now show SolutionSize::Invalid.
• How to solve: Updated bruteforce description to "return the one with maximum total value".
• Extra Remark: Preserved original GJ book text unchanged (for reference).