[Rule] PARTITION to BIN PACKING

[isPANN]

Source: PARTITION
Target: BIN PACKING
Motivation: Establishes NP-completeness of BIN PACKING via polynomial-time reduction from PARTITION. This is one of the most natural and well-known reductions in combinatorial optimization: a set of integers can be split into two equal-sum halves if and only if the same integers (as item sizes) can be packed into exactly 2 bins of capacity S/2. BIN PACKING is NP-complete in the strong sense (also via reduction from 3-PARTITION), but this simpler reduction from PARTITION suffices for weak NP-completeness.

Reference: Garey & Johnson, Computers and Intractability, SR1, p.226

GJ Source Entry

[SR1] BIN PACKING
INSTANCE: Finite set U of items, a size s(u)∈Z^+ for each u∈U, a positive integer bin capacity B, and a positive integer K.
QUESTION: Is there a partition of U into disjoint sets U_1,U_2,…,U_K such that the sum of the sizes of the items in each U_i is B or less?
Reference: Transformation from PARTITION, 3-PARTITION.
Comment: NP-complete in the strong sense. NP-complete and solvable in pseudo-polynomial time for each fixed K≥2. Solvable in polynomial time for any fixed B by exhaustive search.

Reduction Algorithm

Summary:
Given a PARTITION instance A = {a_1, ..., a_n} with sizes s(a_i) ∈ Z^+ and total sum S = Σ s(a_i), construct a BIN PACKING instance as follows:

1. Items: For each element a_i ∈ A, create an item u_i with size s(u_i) = s(a_i), cast from u64 to i32 (matching the partition_knapsack.rs type conversion pattern via i32::try_from).
2. Bin capacity: Set B = ⌊S/2⌋ (cast to i32). If S is odd, there is no balanced partition, and 2 bins of capacity ⌊S/2⌋ cannot hold all items since ⌊S/2⌋ + ⌊S/2⌋ = S - 1 < S.

Implementation trait: ReduceTo<BinPacking<i32>> (witness-capable). The codebase BinPacking<W> is an optimization model (Value = Min<i32>, minimizes number of bins used) with no explicit K parameter. However, the binary partition assignment (0 or 1, indicating which subset) directly serves as a valid 2-bin packing configuration (bin 0 or bin 1). Solution extraction is identity: target_solution.to_vec().

Correctness:

• (PARTITION feasible → BIN PACKING optimal ≤ 2): If there exists A' ⊆ A with Σ_{a ∈ A'} s(a) = S/2, then placing A' items in bin 0 and the rest in bin 1 gives each bin total size exactly S/2 = B. The optimal BinPacking value is ≤ 2. ✓
• (BIN PACKING optimal ≤ 2 → PARTITION feasible): If the optimal packing uses ≤ 2 bins of capacity B = S/2, then items in each bin sum to ≤ S/2. Since total = S, each bin sums to exactly S/2, yielding a valid partition. ✓
• (Odd S case): If S is odd, total capacity 2⌊S/2⌋ = S - 1 < S, so ≥ 3 bins are needed. Both answers are NO. ✓
• (Witness round-trip): Every optimal BinPacking witness using bins {0, 1} extracts (identity) to a satisfying Partition assignment. Use assert_satisfaction_round_trip_from_optimization_target (Source=Or, Target=Min). ✓

Size Overhead

Target metric (code name)	Expression (source getters)
num_items	num_elements

Derivation: Each PARTITION element maps to exactly one BIN PACKING item (n items total). The bin capacity B = ⌊S/2⌋ is a scalar data parameter, not a structural size field. Construction is O(n).

Validation Method

• Closed-loop test: construct a PARTITION instance, reduce to BinPacking<i32>, solve with BruteForce::find_witness, verify via assert_satisfaction_round_trip_from_optimization_target.
• Solution extraction: identity mapping — bin assignment [0, 1, 0, 1, ...] directly is the partition assignment.
• Edge cases: test with odd total sum (optimal bins > 2, no balanced partition), even sum with no valid partition (e.g., {1, 2, 6, 7}, sum = 16, no subset sums to 8).

Example

Source instance (PARTITION):
A = {5, 3, 8, 2, 4, 6} (n = 6 elements)
Total sum S = 5 + 3 + 8 + 2 + 4 + 6 = 28; target half-sum = 14.
A balanced partition exists: A' = {8, 6} (sum = 14), A \ A' = {5, 3, 2, 4} (sum = 14).

Constructed BIN PACKING instance:

Item i	Size s(u_i)
0	5
1	3
2	8
3	2
4	4
5	6

Bin capacity B = 14.

Optimal solution:

• Bin 0: items {2, 5} (sizes 8, 6). Total = 14 ≤ 14 ✓
• Bin 1: items {0, 1, 3, 4} (sizes 5, 3, 2, 4). Total = 14 ≤ 14 ✓
• Bins used: 2 → BIN PACKING feasible → PARTITION feasible.

Solution extraction:

• Config = [1, 1, 0, 1, 1, 0] (items 0,1,3,4 in bin 1; items 2,5 in bin 0)
• Partition assignment is identical: elements {0,1,3,4} in subset 1, elements {2,5} in subset 0.

Negative example:
A = {1, 2, 6, 7} (n = 4, sum S = 16, even).
B = 8. No subset of {1, 2, 6, 7} sums to 8. Optimal BinPacking needs ≥ 3 bins → PARTITION infeasible. ✓

References

• [Garey & Johnson, 1979]: [garey1979] Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.
• [Karp, 1972]: [Karp1972] Richard M. Karp (1972). "Reducibility among combinatorial problems". In: Complexity of Computer Computations. Plenum Press.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from Partition to BinPacking in the reduction graph
Non-trivial	✅ Pass	Classic GJ reduction with feasibility-to-optimization encoding
Correctness	❌ Fail	Reduction algorithm incompatible with codebase BinPacking model; type mismatch not addressed
Well-written	❌ Fail	Overhead table uses source metric name inconsistently; missing discussion of type conversion and model mismatch

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. There is no existing path from Partition to BinPacking in the reduction graph (pred path Partition BinPacking returns no path). This is a novel and well-known reduction from Garey & Johnson (SR1, p.226) that would connect two existing problems. The motivation is clear and well-articulated.

Non-trivial

Pass. While the item mapping is 1-to-1 (each partition element becomes a bin packing item with the same size), the reduction involves a genuine change in problem formulation: it encodes a feasibility question (can we split integers into two equal-sum halves?) as an optimization question (what is the minimum number of bins needed?). The bin capacity B = S/2 and the threshold K = 2 are non-trivial constructions that make the reduction meaningful.

Correctness

Fail. Two significant issues:

1. Model mismatch — no K parameter: The reduction algorithm sets K = 2 (number of bins), but the codebase BinPacking<W> model (src/models/misc/bin_packing.rs) only has two fields: sizes: Vec<W> and capacity: W. There is no K parameter. The BinPacking model is a pure optimization problem (Value = Min<i32>) that minimizes the number of bins used. The issue acknowledges this in a "Note on the codebase BinPacking model" section, stating "PARTITION is feasible if and only if the optimal BIN PACKING value is <= 2." However, this means the reduction is not a standard witness-capable reduction (ReduceTo<BinPacking>) — it would need to be an aggregate-only reduction (ReduceToAggregate) that maps the Or value (feasibility) of Partition to the Min<i32> value of BinPacking via a threshold check. The issue does not discuss this trait distinction or how extract_solution / extract_value would work given the feasibility-vs-optimization gap. The algorithm as written (with K = 2 as a parameter) cannot be directly implemented against the current model.

2. Type mismatch — u64 vs i32: Partition stores sizes as Vec<u64>, while the default BinPacking<i32> stores sizes as Vec<i32>. The reduction must handle this type conversion (similar to how partition_knapsack.rs uses partition_size_to_i64 for the Partition -> Knapsack reduction). The issue does not mention this conversion or potential overflow when u64 values exceed i32::MAX. If targeting BinPacking<i32>, large partition instances would silently overflow. The issue should either target BinPacking<f64> (which has its own precision issues) or explicitly discuss the type conversion strategy.

References are valid:

• Garey & Johnson, 1979 — confirmed in docs/paper/references.bib as garey1979. The Partition -> Bin Packing reduction is listed under SR1/SP13 and is a well-known classic reduction.
• Karp, 1972 — confirmed via web search. Published in Complexity of Computer Computations, Plenum Press, pp. 85-103. Not currently in references.bib but the paper is real and correctly cited.

Well-written

Fail. Several issues:

1. Overhead table variable naming: The table lists num_items = num_items (= n) as the formula. Per the #[reduction(overhead = {...})] convention, the left-hand side is the target field name and the right-hand side expression must use source getter method names. The correct expression should be num_items = "num_elements" (matching the existing Partition -> Knapsack pattern in src/rules/partition_knapsack.rs). The issue writes num_items on both sides, which is confusing — num_items is not a source getter on Partition.

2. Missing implementation guidance for feasibility-optimization gap: The "Note on the codebase BinPacking model" section identifies the problem but does not provide a concrete implementation plan. It should specify:

   • Which reduction trait to implement (ReduceTo with witness extraction, or ReduceToAggregate with value mapping)
   • How extract_solution maps a BinPacking assignment (bin indices) back to a Partition assignment (binary subset membership)
   • How to handle the case where the optimal BinPacking solution uses 1 bin (all items fit in one bin of capacity S/2, which means all items sum to <= S/2 and the "other half" is empty — this is only a valid partition if the total sum equals S/2 + S/2 = S, which it always does)

3. Missing type conversion discussion: No mention of the u64 -> i32 conversion needed for the default BinPacking<i32> variant.

4. Example quality — adequate but could be improved: The positive example (6 elements summing to 28) is good and exercises the reduction meaningfully. It has multiple feasible partitions ({8,6} vs {8,4,2} vs others), which is good for round-trip testing. The negative example (odd sum) is a trivial edge case — a more interesting negative example would have an even sum but no valid partition (e.g., {1, 2, 6, 7}, sum = 16, target = 8, no subset sums to 8).

5. Validation method references nonexistent API: The validation section mentions find_best which is not a method on BruteForce — the correct method is find_witness (returns one optimal witness) or solve (returns aggregate value).

Recommendations

• Clarify whether this should be a ReduceTo (witness-capable) or ReduceToAggregate (value-only) reduction. Given that the BinPacking assignment naturally maps back to a partition (bin 0 items = subset A', bin 1 items = A \ A'), a witness-capable ReduceTo implementation seems feasible.
• Fix the overhead expression to num_items = "num_elements".
• Add explicit type conversion handling (see partition_knapsack.rs for the pattern).
• Replace find_best with find_witness in the validation section.
• Consider adding a non-trivial negative example with even sum.

[zazabap]

Fix-issue changelog

• Removed K=2 parameter from algorithm — BinPacking model is optimization (no K), capacity B=S/2 naturally constrains to ≤2 bins
• Added explicit ReduceTo<BinPacking<i32>> implementation guidance with identity solution extraction
• Added witness round-trip explanation using assert_satisfaction_round_trip_from_optimization_target
• Fixed overhead expression: num_items = "num_elements" (was incorrectly num_items = num_items)
• Added u64→i32 type conversion note referencing partition_knapsack.rs pattern
• Fixed validation API: find_best → find_witness
• Replaced trivial odd-sum negative example with even-sum example {1,2,6,7} (sum=16, no subset sums to 8)

Applied by /fix-issue.