[Model] MinimumWeightSolutionToLinearEquations

[isPANN]

Motivation

MINIMUM WEIGHT SOLUTION TO LINEAR EQUATIONS (P211) from Garey & Johnson, A6 MP5. A classical NP-complete problem (in the strong sense). Serves as a target for the X3C reduction. The problem is equivalent to finding a minimum-support (sparsest) solution to a linear system, a foundational problem in compressed sensing (L1 relaxation / basis pursuit) and machine learning (minimum feature set selection). Also known as Min-RVLS[=] (Minimum Relevant Variables in Linear System with equality constraints).

Associated rules:

• [Rule] X3C to MinimumWeightSolutionToLinearEquations #860: ExactCoverBy3Sets → MinimumWeightSolutionToLinearEquations (NP-completeness proof)

Definition

Name: MinimumWeightSolutionToLinearEquations
Reference: Garey & Johnson, Computers and Intractability, A6 MP5

Mathematical definition:

INSTANCE: Finite set X of pairs (x̄,b), where x̄ is an m-tuple of integers and b is an integer.
OBJECTIVE: Find an m-tuple ȳ with rational entries satisfying x̄·ȳ = b for all (x̄,b) ∈ X that minimizes the number of nonzero entries (Hamming weight) of ȳ.

Variables

• Count: m (one rational variable per dimension of the solution vector)
• Per-variable domain: Q (rationals)
• Meaning: y_j is the j-th component of the solution vector. The problem minimizes the Hamming weight ||ȳ||_0 = |{j : y_j ≠ 0}| subject to Aȳ = b.

Schema (data type)

Type name: MinimumWeightSolutionToLinearEquations
Variants: none

Field	Type	Description
matrix	Vec<Vec<i64>>	The n × m coefficient matrix A: each row is an m-tuple x̄
rhs	Vec<i64>	Right-hand side vector b of length n

Notes:

• This is an optimization problem: Value = Min<usize> (minimum Hamming weight).
• Key getter methods: num_equations() (= n), num_variables() (= m).
• The system Aȳ = b must be satisfied with rational entries. The objective minimizes the number of nonzero entries in ȳ.

Complexity

• Decision complexity: NP-complete in the strong sense (Garey & Johnson; transformation from X3C). Polynomial when K = m (no sparsity constraint — reduces to ordinary linear system solving).
• Best known exact algorithm: Enumerate all C(m, K) subsets of K variables for increasing K; solve each restricted n × K system — O(C(m, K) · poly(n, m)) time.
• Concrete complexity expression: "2^num_variables" (for declare_variants!)
• Inapproximability: Cannot be approximated within a constant factor unless P = NP (Amaldi & Kann, 1998). Cannot be approximated within 2^{log^{1-ε}(n)} for any ε > 0 unless NP ⊆ DTIME(n^{polylog(n)}) (Arora, Babai, Stern & Sweedyk, 1997).
• References:
  • E. Amaldi, S.E. Kann (1998). "On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems." Theoretical Computer Science 209(1-2), pp. 237-260.
  • S. Arora, L. Babai, J. Stern, Z. Sweedyk (1997). "The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations." JCSS 54(2), pp. 317-331.

Extra Remark

Full book text:

INSTANCE: Finite set X of pairs (x̄,b), where x̄ is an m-tuple of integers and b is an integer, and a positive integer K ≤ m.
QUESTION: Is there an m-tuple ȳ with rational entries such that ȳ has at most K non-zero entries and such that x̄·ȳ = b for all (x̄,b) ∈ X?

Reference: [Garey and Johnson, ——]. Transformation from X3C.
Comment: NP-complete in the strong sense. Solvable in polynomial time if K = m.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate subsets of columns by increasing size; for each subset, solve the restricted linear system; return smallest feasible weight.)
• It can be solved by reducing to integer programming. (Binary indicators z_j and big-M constraints: -M·z_j ≤ y_j ≤ M·z_j, minimize Σ z_j, Aȳ = b. Companion rule issue to be filed separately.)
• Other: L1 relaxation (basis pursuit) provides a convex relaxation.

Example Instance

Input:
n = 2 equations, m = 4 variables.
A = [[1, 2, 3, 1], [2, 1, 1, 3]], b = [5, 4].

Equation	y_1	y_2	y_3	y_4	= b
1	1	2	3	1	5
2	2	1	1	3	4

Weight-1 check: No single column is proportional to b (verified: col_1·α gives (α, 2α) = (5, 4) → α=5 but 2·5≠4; similarly for other columns). No weight-1 solution exists.

Optimal solution (weight 2): ȳ = (1, 2, 0, 0)

• Eq 1: 1·1 + 2·2 = 5 ✓
• Eq 2: 2·1 + 1·2 = 4 ✓
• Hamming weight = 2

Optimal value: Min(2).

Other weight-2 solutions exist (e.g., cols {0,2} give ȳ ≈ (1.4, 0, 1.2, 0) — non-integer but valid), but (1, 2, 0, 0) is the cleanest integer solution.

Python validation script

import numpy as np
from itertools import combinations

A = np.array([[1, 2, 3, 1], [2, 1, 1, 3]], dtype=float)
b = np.array([5, 4], dtype=float)

# Check no weight-1 solution
for j in range(4):
    col = A[:, j]
    if np.linalg.norm(col) > 0:
        alpha = b[0] / col[0] if col[0] != 0 else (b[1] / col[1] if col[1] != 0 else None)
        if alpha is not None and np.allclose(col * alpha, b):
            assert False, f"Weight-1 found via col {j}"
print("No weight-1 solution exists")

# Check weight-2 solution
y = np.array([1, 2, 0, 0], dtype=float)
assert np.allclose(A @ y, b)
print(f"Weight-2 solution y=(1,2,0,0) verified: A@y = {A @ y}")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; companion rule issue #860 (X3C → MWSLE) exists
Non-trivial	✅ Pass	Distinct feasibility constraints (sparsity of solution vector) from all existing problems
Correctness	❌ Fail	Inapproximability bound misattributed to Amaldi & Kann (1998); actual source is Arora et al. (1997)
Well-written	⚠️ Warn	Missing companion ILP rule issue link; example is borderline simple

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

Pass. The problem MinimumWeightSolutionToLinearEquations does not exist in the current reduction graph (pred show fails). The issue identifies a concrete connection via issue #860 ([Rule] X3C to Minimum Weight Solution to Linear Equations), preventing this from being an orphan node. The motivation is substantive: the problem is GJ A6 MP5, foundational to compressed sensing (basis pursuit / L1 relaxation) and feature selection in machine learning. Both brute-force and ILP solver paths are identified.

Non-trivial

Pass. This problem has genuinely distinct feasibility constraints from all existing problems in the codebase. The closest existing problem is FeasibleBasisExtension (which requires nonsingularity and non-negativity of a basis inverse), while this problem asks for a minimum-support (sparsest) solution to a linear system. IntegerKnapsack, Knapsack, and other algebraic/set problems have fundamentally different structure.

Correctness

Fail. The issue states:

"The problem cannot be approximated within a factor of 2^{log^{1-epsilon}(n)} for any epsilon > 0 unless NP ⊆ DTIME(n^{polylog(n)}) (Amaldi & Kann, 1998)."

This is misattributed. The 2^{log^{1-ε}(n)} inapproximability bound is from Arora, Babai, Stern & Sweedyk (1997), "The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations," Journal of Computer and System Sciences, 54(2):317–331. The Amaldi & Kann (1998) paper ("On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems," Theoretical Computer Science, 209(1–2):237–260) showed that Min-RVLS cannot be approximated within any constant factor unless P = NP, which is a weaker (though still important) result.

Additionally, the issue claims "NP-complete in the strong sense" in the Complexity section, which is consistent with the GJ book text quoted in the Extra Remark. However, the Wikipedia article on Min-RVLS only confirms NP-hardness without explicitly mentioning strong NP-completeness. This claim is plausible given GJ's classification but could not be independently verified online.

The GJ reference (A6 MP5) and the problem definition itself are correct and match the book text.

Well-written

Warn. Most sections are present and substantive, but there are several issues:

1. Missing companion ILP rule issue: The "How to solve" section checks ILP solvability and describes a big-M formulation, but per project conventions, a [Rule] MinimumWeightSolutionToLinearEquations to ILP companion issue must be linked. No such issue exists.

2. Missing concrete complexity expression: The Complexity section provides only a brute-force bound O(binom(m,K) * poly(n,m)) but does not give a concrete worst-case complexity expression suitable for declare_variants! (e.g., "binom(num_columns, bound) * num_equations^3"). A specific expression in terms of problem parameters is required.

3. Example quality (borderline): The example is correct — ȳ = (2,0,0,0,0) satisfies all 3 equations with 1 nonzero component (≤ K=2). However, the optimal solution is immediately obvious from equation 2 alone (y₁ = 2, all others zero), requiring no real search. For a feasibility problem, the example should ideally require examining multiple column subsets before finding (or ruling out) a feasible one. That said, the example does have non-satisfying configurations (e.g., restricting to columns {3,5} yields an infeasible subsystem), so it meets the minimum bar.

4. Variable section mixes two representations: The Variables section describes both rational variables y_j and binary indicators z_j, but the actual problem only has m rational variables — the binary indicators are an ILP modeling artifact, not part of the problem definition. This may cause confusion during implementation.

Recommendations

• Fix the inapproximability attribution: cite Arora, Babai, Stern & Sweedyk (1997) for the 2^{log^{1-ε}(n)} bound, and Amaldi & Kann (1998) for the constant-factor inapproximability.
• File a companion [Rule] MinimumWeightSolutionToLinearEquations to ILP issue or remove the ILP checkbox.
• Add a concrete complexity expression for declare_variants!, e.g., based on the brute-force enumeration.
• Simplify the Variables section to describe only the m rational variables; move the ILP formulation details to the companion rule issue.
• Consider strengthening the example: e.g., an instance where K is tight (the minimum weight equals K exactly) so that a round-trip test is more discriminating.

[isPANN]

Converted from decision framing (bound K) to optimization framing (minimize Hamming weight of solution vector). Removed bound field from schema. Removed Wrong label.

[isPANN]

Fix-issue changelog

• Correctness fix: Fixed inapproximability attribution — 2^{log^{1-ε}(n)} is from Arora, Babai, Stern & Sweedyk (1997), not Amaldi & Kann (1998). Amaldi & Kann provides the constant-factor hardness.
• Example: Replaced trivial weight-1 instance (y=(2,0,0,0,0)) with non-trivial weight-2 instance (A=[[1,2,3,1],[2,1,1,3]], b=[5,4], optimal y=(1,2,0,0)). No single-variable solution exists.
• Associated rules: Linked [Rule] X3C to MinimumWeightSolutionToLinearEquations #860.
• Complexity: Added concrete expression "2^num_variables".
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Added Python validation script.

Applied by /fix-issue.