[Model] CapacityAssignment

[isPANN]

Motivation

CAPACITY ASSIGNMENT (P155) from Garey & Johnson, A4 SR7. An NP-complete bicriteria optimization problem arising in communication network design. Each communication link must be assigned a capacity from a discrete set, balancing total cost against total delay penalty, subject to the monotonicity constraint that higher capacity costs more but incurs less delay. Proved NP-complete by Van Sickle and Chandy (1977) via reduction from SUBSET SUM.

Associated rules:

• R101: SubsetSum → CapacityAssignment (as target)

Definition

Name: CapacityAssignment
Canonical name: CAPACITY ASSIGNMENT
Reference: Garey & Johnson, Computers and Intractability, A4 SR7

Mathematical definition:

INSTANCE: Set C of communication links, set M ⊆ Z+ of capacities, cost function g: C x M → Z+, delay penalty function d: C x M → Z+ such that for all c ∈ C and i < j ∈ M, g(c,i) ≤ g(c,j) and d(c,i) ≥ d(c,j), and positive integers K and J.
QUESTION: Is there an assignment σ: C → M such that the total cost ∑_{c ∈ C} g(c,σ(c)) does not exceed K and such that the total delay penalty ∑_{c ∈ C} d(c,σ(c)) does not exceed J?

Variables

• Count: |C| variables, one per communication link. Each variable selects a capacity from M.
• Per-variable domain: {1, 2, ..., |M|} — index into the ordered set of capacities M.
• Meaning: Variable i encodes the capacity assigned to link c_i. A satisfying assignment σ maps each link to a capacity such that both the total cost budget K and total delay budget J are met simultaneously. The monotonicity constraints (higher capacity = higher cost, lower delay) make this a bicriteria trade-off.

Schema (data type)

Type name: CapacityAssignment
Variants: none (no graph or weight type parameter)

Field	Type	Description
num_links	usize	Number of communication links
capacities	Vec<u64>	Ordered set M of available capacities
cost	Vec<Vec<u64>>	Cost matrix g: cost[i][j] = g(c_i, M[j])
delay	Vec<Vec<u64>>	Delay matrix d: delay[i][j] = d(c_i, M[j])
cost_budget	u64	Cost budget K
delay_budget	u64	Delay budget J

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The monotonicity constraints are: for all i and j1 < j2 in M, cost[i][j1] ≤ cost[i][j2] and delay[i][j1] ≥ delay[i][j2].
• No weight or graph type parameters needed.

Complexity

• Best known exact algorithm: O*(|M|^|C|) brute force over all assignments. Since the problem is solvable in pseudo-polynomial time (as noted in GJ), a dynamic programming approach runs in O(|C| · K · J) time, which is pseudo-polynomial when K and J are bounded by a polynomial in the input size. The DP iterates over links and maintains a 2D table of (cost-so-far, delay-so-far) states.
• Complexity string: "num_capacities ^ num_links"
• NP-completeness: NP-complete (Van Sickle and Chandy, 1977). Transformation from SUBSET SUM.
• Special cases: With |M| = 2, the problem reduces to a form of SUBSET SUM / bicriteria knapsack. Pseudo-polynomial when the budgets are polynomially bounded.
• References:
  • Lawrence Van Sickle and K. Mani Chandy (1977). "Computational Complexity of Network Design Algorithms." Proc. IFIP Congress 77, Toronto, 1977, pp. 235–239.

Extra Remark

Full book text:

INSTANCE: Set C of communication links, set M ⊆ Z+ of capacities, cost function g: C×M → Z+, delay penalty function d: C×M → Z+ such that, for all c ∈ C and i < j ∈ M, g(c,i) ≤ g(c,j) and d(c,i) ≥ d(c,j), and positive integers K and J.
QUESTION: Is there an assignment σ: C → M such that the total cost ∑c ∈ C g(c,σ(c)) does not exceed K and such that the total delay penalty ∑c ∈ C d(c,σ(c)) does not exceed J?
Reference: [Van Sickle and Chandy, 1977]. Transformation from SUBSET SUM.
Comment: Solvable in pseudo-polynomial time.

How to solve

• It can be solved by (existing) bruteforce — enumerate all |M|^|C| assignments and check cost/delay budgets.
• It can be solved by reducing to integer programming — minimize/check cost and delay as linear constraints with integer capacity variables.
• Other: Pseudo-polynomial DP in O(|C| · K · J) time. Also reducible to 0-1 knapsack variants or bicriteria shortest path.

Example Instance

Instance 1 (YES, satisfiable):

• Links: C = {c_1, c_2, c_3}
• Capacities: M = {1, 2, 3}
• Cost function g:

Link	g(·,1)	g(·,2)	g(·,3)
c_1	1	3	6
c_2	2	4	7
c_3	1	2	5

• Delay penalty function d:

Link	d(·,1)	d(·,2)	d(·,3)
c_1	8	4	1
c_2	7	3	1
c_3	6	3	1

• Monotonicity check: for each link, cost is non-decreasing and delay is non-increasing with capacity ✓

• Cost budget: K = 10

• Delay budget: J = 12

• Assignment σ = (2, 2, 2): cost = 3+4+2 = 9 ≤ 10 ✓, delay = 4+3+3 = 10 ≤ 12 ✓ (best balanced)

• Assignment σ = (1, 2, 3): cost = 1+4+5 = 10 ≤ 10 ✓, delay = 8+3+1 = 12 ≤ 12 ✓ (tightest on both budgets)

• Assignment σ = (3, 1, 2): cost = 6+2+2 = 10 ≤ 10 ✓, delay = 1+7+3 = 11 ≤ 12 ✓

• Failing assignment σ = (1, 1, 1): cost = 1+2+1 = 4 ≤ 10 ✓, delay = 8+7+6 = 21 > 12 ✗ (cheap but too slow)

• Failing assignment σ = (3, 3, 3): cost = 6+7+5 = 18 > 10 ✗ (fast but too expensive)

• 5 satisfying assignments out of 27 total (BruteForce-friendly)

• Answer: YES

Instance 2 (YES, from Subset Sum reduction):
Constructed from SubsetSum A = {3, 7, 1, 8, 4, 12}, B = 15:

• Links: C = {c_1, ..., c_6}
• Capacities: M = {1, 2}
• Cost: g(c_i, 1) = 0, g(c_i, 2) = a_i for each i
• Delay: d(c_i, 1) = a_i, d(c_i, 2) = 0 for each i
• K = 15, J = 20
• Assignment σ(c_1)=2, σ(c_2)=1, σ(c_3)=1, σ(c_4)=2, σ(c_5)=2, σ(c_6)=1
  • Cost = 3+0+0+8+4+0 = 15 ≤ 15 ✓
  • Delay = 0+7+1+0+0+12 = 20 ≤ 20 ✓
• Answer: YES

References

• [Van Sickle and Chandy, 1977]: Lawrence Van Sickle and K. Mani Chandy (1977). "Computational Complexity of Network Design Algorithms." Proc. IFIP Congress 77, Toronto, 1977, pp. 235–239.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct bicriteria satisfaction problem unlike any existing model
Correctness	⚠️ Warn	Reference verified but cited as "technical report" — actual venue is IFIP Congress 1977; Instance 1 example is broken
Well-written	❌ Fail	Instance 1 labeled "YES, satisfiable" but no satisfying assignment is demonstrated (5 attempts all fail); complexity section lacks a concrete declare_variants! string

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. CapacityAssignment does not exist in the codebase. It is a genuine satisfaction problem (Metric = bool) from Garey & Johnson (A4 SR7) with a distinct bicriteria structure. The issue mentions an associated rule R101 (SubsetSum → CapacityAssignment), which would connect it to the reduction graph. Motivation is concrete: communication network design with cost-delay tradeoff.

Non-trivial

Pass. This is a bicriteria feasibility problem with monotonicity constraints on cost/delay functions. No existing problem in the codebase has this structure — it is not a variant of Knapsack, BinPacking, or any other implemented model. The feasibility constraint involves two simultaneous budget bounds with a coupling monotonicity condition, which is genuinely distinct.

Correctness

Warn. Two issues found:

1. Reference format: The issue cites "Larry van Sickle and K. Mani Chandy (1977). 'The complexity of computer network design problems.' Technical report." The actual publication is: Lawrence Van Sickle and K. Mani Chandy, "Computational Complexity of Network Design Algorithms," IFIP Congress 77, Toronto, Canada, pp. 235-239, 1977. The title is slightly different and it is a conference paper (IFIP Congress), not a technical report. The NP-completeness claim via reduction from Subset Sum is consistent with Garey & Johnson's listing (A4 SR7).

2. Instance 1 example is incorrect: Instance 1 is labeled "YES, satisfiable" but the issue shows 5 attempted assignments and none satisfy both budget constraints simultaneously. The issue never demonstrates a valid satisfying assignment for Instance 1. A manual search also fails to find one — with K=25 and J=30, achieving low enough delay requires high capacities which blow the cost budget. This instance appears to be a NO instance mislabeled as YES, or the budgets need adjustment.

The formal problem definition itself matches the Garey & Johnson formulation correctly.

Well-written

Fail. Specific issues:

1. Instance 1 is broken (critical): The example is labeled "YES, satisfiable" but no satisfying assignment is ever shown. Five attempted assignments are listed and all fail. An example instance MUST include a verified satisfying assignment to be useful for implementation and testing. Instance 2 (from SubsetSum reduction) is correct and well-worked.

2. Complexity section lacks a concrete complexity string: The issue discusses brute-force O*(|M|^|C|) and pseudo-polynomial DP, but does not provide a concrete declare_variants! complexity expression using getter method names (e.g., "num_capacities ^ num_links"). This is required for implementation.

3. Minor: The "Variables" section correctly identifies the per-variable domain as {1, ..., |M|}, but the Schema uses u64 for all numeric fields — the issue should clarify whether u64 is appropriate or if i64/usize would be more consistent with existing models.

Recommendations

• Fix Instance 1: either find budgets K, J that make the instance satisfiable and demonstrate the assignment, or replace it with a smaller, hand-verifiable YES instance (e.g., 3 links, 2 capacities).
• Correct the reference to: Lawrence Van Sickle and K. Mani Chandy, "Computational Complexity of Network Design Algorithms," IFIP Congress 1977, pp. 235-239.
• Add a concrete complexity string for declare_variants!, e.g., "num_capacities ^ num_links".

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12. Re-checking with --force. Issue body unchanged since last check.

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct bicriteria satisfaction problem unlike any existing model
Correctness	⚠️ Warn	Reference verified but cited with wrong title/venue; complexity claims correct
Well-written	❌ Fail	Instance 1 is a NO instance mislabeled as YES (exhaustively verified); complexity section lacks concrete declare_variants! string

Overall: 2 passed, 1 warning, 1 failed

Previously: 2 passed, 1 warning, 1 failed → No change

---

Usefulness

Pass. CapacityAssignment does not exist in the codebase (pred show CapacityAssignment fails). It is a genuine satisfaction problem (Metric = bool) from Garey & Johnson (A4 SR7) with a distinct bicriteria structure — simultaneous cost and delay budgets with monotonicity constraints. The issue mentions associated rule R101 (SubsetSum → CapacityAssignment), connecting it to the reduction graph via the existing SubsetSum problem.

Non-trivial

Pass. This is a bicriteria feasibility problem with monotonicity constraints on cost/delay functions. No existing problem in the codebase (86 types checked) has this structure. The feasibility constraint involves two simultaneous budget bounds with a coupling monotonicity condition, which is genuinely distinct from Knapsack, BinPacking, or any other implemented model.

Correctness

Warn. Two issues found:

1. Reference format (minor): The issue cites "Larry van Sickle and K. Mani Chandy (1977). 'The complexity of computer network design problems.' Technical report." The correct citation is: Lawrence Van Sickle and K. Mani Chandy, "Computational Complexity of Network Design Algorithms," Proc. IFIP Congress 77, Toronto, 1977, pp. 235-239. (Confirmed via DBLP record conf/ifip/SickleC77.) The title and venue are both wrong in the issue. However, the underlying NP-completeness claim (reduction from Subset Sum) is confirmed by Garey & Johnson's catalog entry SR7.

2. Definition correctness: The formal definition matches the Garey & Johnson formulation correctly. Complexity claims (brute-force O*(|M|^|C|), pseudo-polynomial DP in O(|C|·K·J)) are accurate.

3. Representation feasibility: u64 for cost/delay fields is appropriate for non-negative integer functions. No issues.

Well-written

Fail. Two issues:

1. Instance 1 is broken (critical): The example is labeled "YES, satisfiable" but exhaustive enumeration of all 729 (3^6) assignments confirms NO satisfying assignment exists. The tightest assignment found is σ = (2,2,2,2,2,3) with cost=31, delay=26 — meets the delay budget but exceeds cost by 6. The issue itself shows 5 attempted assignments that all fail, yet never demonstrates a valid one. This has not been fixed since the previous review.

2. Complexity section lacks concrete declare_variants! string: The issue discusses brute-force and pseudo-polynomial DP but does not provide a concrete complexity expression using getter method names (e.g., "num_capacities ^ num_links"). This is needed for implementation.

Instance 2 is correct and well-constructed: The SubsetSum reduction instance (A={3,7,1,8,4,12}, B=15) has exactly 4 satisfying assignments out of 64 total ({3,12}, {7,8}, {3,4,8}, {1,3,4,7} all sum to 15), providing good round-trip testability.

Recommendations

• Fix Instance 1: Either adjust the budgets K and J to make it satisfiable (e.g., increase K to ~31 or J to ~44), or replace it with a smaller hand-verifiable YES instance (e.g., 3 links, 2 capacities).
• Fix the reference: Cite as: Lawrence Van Sickle and K. Mani Chandy, "Computational Complexity of Network Design Algorithms," Proc. IFIP Congress 77, Toronto, 1977, pp. 235-239.
• Add a concrete complexity string for declare_variants!, e.g., "num_capacities ^ num_links".

[GiggleLiu]

Fix-issue changelog

• Replaced Instance 1: original 6-link instance was a NO instance mislabeled YES (exhaustively verified, all 729 assignments fail). New instance: 3 links, 3 capacities, K=10, J=12 with 5 verified satisfying assignments and 2 failing examples demonstrating cost-delay trade-off
• Corrected reference: "Larry van Sickle ... Technical report" → "Lawrence Van Sickle and K. Mani Chandy, 'Computational Complexity of Network Design Algorithms,' Proc. IFIP Congress 77, Toronto, 1977, pp. 235–239" (confirmed via DBLP conf/ifip/SickleC77)
• Added concrete complexity string "num_capacities ^ num_links" for declare_variants!

Applied by /fix-issue.