[Model] NumericalMatchingWithTargetSums

[isPANN]

Motivation

NUMERICAL MATCHING WITH TARGET SUMS (P144) from Garey & Johnson, A3 SP17. A strongly NP-complete matching problem: given two disjoint sets X and Y each of size m with positive integer sizes, and a target vector <B_1,...,B_m>, can X ∪ Y be partitioned into m pairs (one from each set) such that pair i sums to B_i? This generalizes bipartite perfect matching with a numerical constraint on each matched pair. Notably, the problem becomes polynomial-time solvable when all targets are equal (B_1 = B_2 = ... = B_m), highlighting that the difficulty lies in the heterogeneity of target sums.

Associated rules:

• R82: NUMERICAL 3-DIMENSIONAL MATCHING -> NUMERICAL MATCHING WITH TARGET SUMS (establishes NP-completeness)

Definition

Name: NumericalMatchingWithTargetSums

Reference: Garey & Johnson, Computers and Intractability, A3 SP17

Mathematical definition:

INSTANCE: Disjoint sets X and Y, each containing m elements, a size s(a) in Z^+ for each element a in X union Y, and a target vector <B_1, B_2, ..., B_m> with positive integer entries.
QUESTION: Can X union Y be partitioned into m disjoint sets A_1, A_2, ..., A_m, each containing exactly one element from each of X and Y, such that, for 1 <= i <= m, sum_{a in A_i} s(a) = B_i?

Variables

• Count: m^2 (one binary variable for each possible pairing (x_i, y_j))
• Per-variable domain: binary {0, 1}
• Meaning: Variable z_{i,j} = 1 if and only if x_i and y_j are matched together. The constraints require: (1) each x_i appears in exactly one pair, (2) each y_j appears in exactly one pair, and (3) for each target index k, the pair assigned to target k satisfies s(x_i) + s(y_j) = B_k. The assignment of pairs to targets is part of the decision.

ILP alternative: Binary variables z_{i,j,k} = 1 if x_i and y_j are matched and assigned to target k. Constraints: each x_i in exactly one pair, each y_j in exactly one pair, each target used exactly once, and s(x_i) + s(y_j) = B_k for each selected assignment.

Schema (data type)

Type name: NumericalMatchingWithTargetSums
Variants: none (sizes and targets are positive integers)

Field	Type	Description
sizes_x	Vec<i64>	Sizes s(x_i) for elements of X (length m)
sizes_y	Vec<i64>	Sizes s(y_j) for elements of Y (length m)
targets	Vec<i64>	Target sums <B_1, ..., B_m> (length m)

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_pairs() (= m = |X| = |Y|).

Complexity

• Decision complexity: NP-complete in the strong sense (Garey & Johnson, 1979; by transformation from NUMERICAL 3-DIMENSIONAL MATCHING). No pseudo-polynomial algorithm exists unless P = NP.
• Best known exact algorithm: O*(2^m) via dynamic programming on subsets, tracking which Y elements have been matched. Brute-force: O(m! * m) by enumerating all m! perfect matchings.
• Concrete complexity expression: "2^num_pairs" (for declare_variants!)
• Polynomial special case: Solvable in polynomial time when all targets are equal (B_1 = ... = B_m), reducing to bipartite matching with a single sum constraint.
• References:
  • M.R. Garey and D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.

Extra Remark

Full book text:

INSTANCE: Disjoint sets X and Y, each containing m elements, a size s(a) ∈ Z^+ for each element a ∈ X ∪ Y, and a target vector <B_1,B_2,…,B_m> with positive integer entries.
QUESTION: Can X ∪ Y be partitioned into m disjoint sets A_1,A_2,…,A_m, each containing exactly one element from each of X and Y, such that, for 1 ≤ i ≤ m, Σ_{a ∈ A_i} s(a) = B_i?
Reference: Transformation from NUMERICAL 3-DIMENSIONAL MATCHING.
Comment: NP-complete in the strong sense, but solvable in polynomial time if B_1 = B_2 = ··· = B_m.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all m! matchings of X to Y; for each matching, check if the multiset of pair sums equals the multiset of targets.)
• It can be solved by reducing to integer programming. (ILP with binary variables z_{i,j,k} = 1 if x_i and y_j are matched and assigned to target k; constraints: each x_i in exactly one pair, each y_j in exactly one pair, each target used exactly once, and s(x_i) + s(y_j) = B_k for each selected assignment. Companion rule issue to be filed separately.)
• Other: DP on subsets in O*(2^m); polynomial when all targets are equal.

Example Instance

Input:
X = {x_1, x_2, x_3}, Y = {y_1, y_2, y_3}, m = 3
Sizes: s(x_1) = 1, s(x_2) = 4, s(x_3) = 7, s(y_1) = 2, s(y_2) = 5, s(y_3) = 3
Targets: <B_1, B_2, B_3> = <3, 7, 12>

Valid matching:

• (x_1, y_1) → 1 + 2 = 3 = B_1 ✓
• (x_2, y_3) → 4 + 3 = 7 = B_2 ✓
• (x_3, y_2) → 7 + 5 = 12 = B_3 ✓

All elements used exactly once. Each pair sums to its assigned target. ✓
Answer: YES — this is the unique valid matching (1 out of 6 permutations).

Note: The naive identity matching (x_i ↔ y_i) gives sums {3, 9, 10}, which does not match the targets {3, 7, 12}. The correct matching requires x_2 to pair with y_3 and x_3 to pair with y_2.

Negative example:
X = {x_1, x_2}, Y = {y_1, y_2}, m = 2
Sizes: s(x_1) = 3, s(x_2) = 5, s(y_1) = 4, s(y_2) = 6
Targets: <B_1, B_2> = <8, 8>

Possible pairings:

• (x_1, y_1) and (x_2, y_2): sums 7 and 11 → multiset {7, 11} ≠ {8, 8} ✗
• (x_1, y_2) and (x_2, y_1): sums 9 and 9 → multiset {9, 9} ≠ {8, 8} ✗

Answer: NO — no valid matching exists.

Python validation script

from itertools import permutations

def find_valid_matchings(sizes_x, sizes_y, targets):
    m = len(sizes_x)
    target_sorted = sorted(targets)
    valid = []
    for perm in permutations(range(m)):
        sums = [sizes_x[i] + sizes_y[perm[i]] for i in range(m)]
        if sorted(sums) == target_sorted:
            for tperm in permutations(range(m)):
                if all(sums[i] == targets[tperm[i]] for i in range(m)):
                    valid.append((perm, tperm))
                    break
    return valid

# Positive example
sx = [1, 4, 7]; sy = [2, 5, 3]; tgt = [3, 7, 12]
v = find_valid_matchings(sx, sy, tgt)
assert len(v) == 1
assert v[0][0] == (0, 2, 1)  # x1↔y1, x2↔y3, x3↔y2
print(f"Positive: {len(v)} valid matching (unique, non-trivial)")

# Negative example
sx_neg = [3, 5]; sy_neg = [4, 6]; tgt_neg = [8, 8]
v_neg = find_valid_matchings(sx_neg, sy_neg, tgt_neg)
assert len(v_neg) == 0
print("Negative: No valid matching (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	ILP solving claimed but no companion [Rule] NumericalMatchingWithTargetSums to ILP issue linked
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	G&J SP17 reference cannot be independently verified online; no concrete complexity expression provided
Well-written	❌ Fail	Multiple issues: missing ILP rule crossref, weak positive example, missing concrete complexity expression

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem does not yet exist in the codebase (pred show NumericalMatchingWithTargetSums fails). One planned reduction is mentioned: R82 (Numerical 3-Dimensional Matching → NumericalMatchingWithTargetSums), which would connect it to the reduction graph. Motivation is substantive and explains both the problem's significance and the polynomial-time special case.

However, the "How to solve" section checks the ILP box and describes a direct ILP formulation, but no companion [Rule] NumericalMatchingWithTargetSums to ILP issue is linked in the body. Per template requirements, if ILP solving is claimed, a direct rule issue must be linked. → Fail

Non-trivial

This problem is genuinely distinct from all existing problems in the codebase. The closest existing problems are:

• Partition — partitions a single set into two equal-sum halves; no matching or per-target constraints.
• ThreePartition — partitions into triples summing to a common target; does not involve two disjoint sets or heterogeneous targets.
• MaximumMatching — graph matching without numerical sum constraints.

NumericalMatchingWithTargetSums combines bipartite matching with heterogeneous numerical target constraints, which is a structurally different feasibility condition. → Pass

Correctness

3a — Definition: The formal definition is mathematically well-formed. Input, feasibility constraints, and the decision question are clearly stated. The definition matches the "Extra Remark" section which appears to be verbatim from G&J.

3b — Complexity: The issue claims the problem is "NP-complete in the strong sense" per G&J 1979 and cites brute-force O(m! * m) and DP O*(2^m). These bounds are plausible but no concrete complexity expression suitable for declare_variants! is provided (e.g., "2^num_pairs" or "factorial(num_pairs)"). The DP bound O*(2^m) is reasonable as a best-known exact algorithm.

The claim that the problem becomes polynomial when all targets are equal is plausible — with equal targets, one only needs to check whether there exists a perfect matching in a bipartite graph where edge (x_i, y_j) exists iff s(x_i) + s(y_j) = B, which is solvable in polynomial time.

3c — Reference verification: The G&J reference garey1979 exists in docs/paper/references.bib. However, the specific problem number "SP17" and page "P144" cannot be independently verified online — the G&J appendix is not publicly available, and Wikipedia's NP-complete problem list only goes up to SP16 (Numerical 3-Dimensional Matching). The problem definition is internally consistent and the "Extra Remark" section with verbatim book text lends credibility, so this is a warning rather than a failure.

3d — NP-completeness source: The issue says NP-completeness is "by transformation from NUMERICAL 3-DIMENSIONAL MATCHING." SP16 (Num3DM) is confirmed as strongly NP-complete, so a reduction from it would indeed establish strong NP-completeness. → Plausible but unverifiable online.

3e — Representation feasibility: The schema uses Vec<i64> for sizes and targets with Z^+ (positive integers). i64 is sufficient for practical instances. → Pass

Well-written

4a — Information completeness:

• Motivation: ✅ Present and substantive
• Name: ✅ NumericalMatchingWithTargetSums
• Reference: ✅ G&J 1979
• Definition: ✅ Formal INSTANCE/QUESTION format
• Variables: ✅ Present (m^2 binary variables)
• Schema: ✅ Field table provided
• Complexity: ❌ No concrete complexity expression — the section describes algorithms informally but does not provide a string like "2^num_pairs" or "factorial(num_pairs)" that could be used in declare_variants!
• How to solve: ⚠️ ILP is checked but no companion rule issue is linked
• Example Instance: ⚠️ Present but has quality issues (see below)
• Expected Outcome: ✅ Both positive and negative examples with solutions

4b — Definition completeness: The formal definition is precise and implementable. All quantifiers are explicit. → Pass

4c — Symbol consistency: Symbols are consistent across sections. m, X, Y, s(a), B_i are used consistently throughout. → Pass

4d — Example quality:
The positive example (m=3) has a significant weakness: all y-values are identical (y_1=y_2=y_3=7). This means the matching is trivially determined by the x-values alone — any permutation of Y elements gives the same pair sums. The example does not exercise the core matching structure of the problem, where different y-values create non-trivial matching choices. A correct reduction could be buggy in how it handles Y-element assignment and still pass this example.

The negative example (m=2) is good — it demonstrates infeasibility clearly.

For the positive example, the instance should have distinct y-values so that the pairing decision is non-trivial and a round-trip test can catch bugs in the matching logic. → Fail

4e — Representation feasibility: Vec<i64> for positive integers is appropriate. → Pass

Recommendations

• Add a companion [Rule] NumericalMatchingWithTargetSums to ILP issue and link it in the "How to solve" section, or remove the ILP checkbox.
• Replace the positive example with one that has distinct y-values (e.g., sizes_y = [4, 6, 8]) so the matching is non-trivial.
• Add a concrete complexity expression for declare_variants!, e.g., "2^num_pairs" based on the DP approach.
• The variable description mentions z_{i,j,k} in the ILP section but z_{i,j} in the Variables section — clarify which formulation the implementation will use.

[isPANN]

Fix-issue changelog

• Positive example: Replaced trivial example (all y-values = 7) with non-trivial instance: sx=(1,4,7), sy=(2,5,3), targets=(3,7,12). Unique valid matching requires x2↔y3 and x3↔y2 (identity matching fails). Verified by exhaustive Python script.
• Complexity: Added concrete expression "2^num_pairs" for declare_variants! (DP on subsets).
• ILP: Added note that companion [Rule] NumericalMatchingWithTargetSums to ILP issue to be filed separately.
• Variables section: Split simple z_{i,j} matching variables from z_{i,j,k} ILP formulation for clarity.
• Schema notes: Added num_pairs() getter description.
• Added Python validation script verifying both positive (1 unique matching) and negative (0 matchings) examples.

Applied by /fix-issue.