[Model] QuadraticProgramming

[isPANN]

Important

Scoped to Bounded Integer Quadratic Programming. The fully continuous (rational) QP of Garey & Johnson MP2 requires continuous-domain machinery that the library's Problem trait (dims() -> Vec<usize>, a finite product of discrete sets) does not provide. We instead implement a discrete superset of QUBO: integer variables y_i ∈ {-K, ..., K} for a fixed bound K ≥ 1, with linear constraints and quadratic objective. NP-hardness is preserved (Sahni 1974 PARTITION reduction lands in {0,1}^m ⊂ {-K, ..., K}^m). The fully continuous / rational QP version is out of scope for this library and is left as future work; cite Vavasis (1990) for the NP-completeness of the rational form.

Build as optimization, not decision. Value = Min<f64>.
Objective: Minimize the quadratic objective Σ (cᵢyᵢ² + dᵢyᵢ) subject to linear constraints.
Do not add a bound/threshold field for the objective — let the solver find the optimum directly. (The bound field below is the per-variable domain bound K, not an objective threshold.) See #765.

Motivation

QUADRATIC PROGRAMMING (P208) from Garey & Johnson, A6 MP2, restricted to bounded integer variables. A foundational NP-complete optimization problem that bridges integer programming and combinatorial optimization. NP-hardness arises from PARTITION via Sahni (1974); since that reduction places the optimum on {0,1}^m, it remains valid for any per-variable bound K ≥ 1 and the bounded integer variant is therefore NP-hard. Bounded Integer QP is also a strict superset of QUBO (the case K = 1 with y_i ∈ {-1, 0, 1} subsumes {0, 1}-QUBO after a standard affine change of variables) and a superset of QUBO-with-linear-constraints.

The fully continuous / rational case (MP2 as stated in G&J) was open in 1979 (G&J's "(*)" marker) and was shown to be in NP by Vavasis (1990), making it NP-complete. We do not implement the rational version here — the Problem trait's dims() API requires finite discrete domains. Adding continuous-domain support is a separate trait-level design problem, left as future work.

Associated rules:

• R153: PARTITION to QUADRATIC PROGRAMMING (Sahni-style reduction; lands on {0,1}^m, valid for any K ≥ 1).

Definition

Name: QuadraticProgramming (variant: bounded integer)
Reference: Garey & Johnson, Computers and Intractability, A6 MP2; Sahni (1974) for NP-hardness; Vavasis (1990) for NP-membership of the rational form.

Mathematical definition:

INSTANCE: A positive integer m, a positive integer bound K ≥ 1, a finite set X of pairs (x̄, b) where x̄ ∈ ℤ^m (or rational; integer coefficients suffice for NP-hardness) and b ∈ ℝ, and two m-tuples c̄, d̄ ∈ ℝ^m.

OBJECTIVE: Find an m-tuple ȳ ∈ {-K, -K+1, ..., K-1, K}^m that minimizes Σᵢ₌₁ᵐ (cᵢ yᵢ² + dᵢ yᵢ) subject to x̄ · ȳ ≤ b for all (x̄, b) ∈ X.

The original GJ formulation is a decision problem with threshold B over rationals; here we use the optimization framing with Value = Min<f64> and restrict the variable domain to a finite integer box. The decision answer is YES iff the minimum value ≤ −B (after negating the objective).

Variables

• Count: m (one variable per dimension of the decision vector ȳ).
• Per-variable domain: y_i ∈ {-K, -K+1, ..., K-1, K} for a fixed bound K ≥ 1. The dims vector is vec![2*K + 1; m]. The internal config index c ∈ {0, ..., 2K} maps to y_i = c - K.
• Meaning: yᵢ is the i-th component of the integer decision vector. The feasible region is {-K, ..., K}^m intersected with the polyhedron {ȳ : x̄·ȳ ≤ b for all (x̄, b) ∈ X}. Infeasible configurations evaluate to Min<f64>::infeasible() (or +∞) so the optimum is taken over the feasible set.

Schema (data type)

Type name: QuadraticProgramming
Variants: none (integer domain hard-coded; no graph or weight type parameters).

Field	Type	Description
num_vars	usize	Number of variables m
bound	usize	Per-variable domain bound K; each y_i ∈ {-K, ..., K} so dims = vec![2K+1; m]
constraints	Vec<LinearConstraint>	Linear constraints x̄·ȳ ≤ b (reuses ILP's LinearConstraint)
quad_coeffs	Vec<f64>	Quadratic coefficients c̄ = (c₁, ..., cₘ) in objective
lin_coeffs	Vec<f64>	Linear coefficients d̄ = (d₁, ..., dₘ) in objective

Getter methods:

• num_vars() → number of variables m
• bound() → per-variable bound K
• num_constraints() → number of linear constraints |X|

Complexity

• Best known exact algorithm: Bounded Integer QP is NP-hard via Sahni (1974) PARTITION → QP (the reduction lands in {0,1}^m, so any K ≥ 1 preserves NP-hardness). No published O*(c^m) bound improves on naive enumeration over the discrete box {-K, ..., K}^m in the general non-convex case; we therefore use the exhaustive bound.
• Complexity expression: (2*bound + 1)^num_vars

Extra Remark

Full book text (rational version, for reference):

INSTANCE: Finite set X of pairs (x̄,b), where x̄ is an m-tuple of rational numbers and b is a rational number, two m-tuples c̄ and d̄ of rational numbers, and a rational number B.
QUESTION: Is there an m-tuple ȳ of rational numbers such that x̄·ȳ ≤ b for all (x̄,b) ∈ X and such that Σᵢ₌₁ᵐ (cᵢyᵢ² + dᵢyᵢ) ≥ B?

Reference: [Sahni, 1974]. Transformation from PARTITION.
Comment: Not known to be in NP in 1979 [Garey & Johnson, 1979]; resolved by Vavasis (1990): QP is in NP and hence NP-complete. The continuous / rational case is out of scope for this library — Problem::dims() requires finite discrete domains. If we instead require all entries of ȳ be integers in {-K, ..., K} (this issue's scope), NP-hardness is preserved by Sahni's reduction. The Jeroslow (1973) undecidability result concerns unbounded integer variables with quadratic constraints and is not relevant to this bounded-integer formulation.

How to solve

• It can be solved by (existing) bruteforce. The finite domain {-K, ..., K}^m with dims = vec![2K+1; m] is compatible with BruteForce; infeasible configurations evaluate to +∞.
• It can be solved by reducing to integer programming. Standard linearization: introduce auxiliary variables z_i = y_i² (encoded via a small constraint gadget over the finite domain {0, ..., K²}), giving a linear objective in (y, z). We do not claim direct ILP solvability in this issue; the dedicated BoundedIntegerQP → ILP reduction can be filed as a follow-up rule.
• Other: For the K = 1 case with all y_i ∈ {0, 1} (after affine shift), the problem reduces to QUBO-with-linear-constraints. PARTITION instances embedded via Sahni's reduction can be brute-forced directly.

Example Instance

A small Sahni-style PARTITION instance with m = 3, K = 1 (so y_i ∈ {-1, 0, 1}, dims = [3, 3, 3], search space 27).

Underlying PARTITION instance: items with sizes a = (1, 1, 2), total sum S = 4, target half S/2 = 2. We ask whether a subset sums to 2.

QP encoding (Sahni 1974): put c_i = -1, d_i = a_i = (1, 1, 2), and add constraints to force y_i ∈ {0, 1} (i.e., restrict to the {0, 1} slice of {-1, 0, 1}):

Constraint	x̄	b	Meaning
1	(-1, 0, 0)	0	y₁ ≥ 0
2	(0, -1, 0)	0	y₂ ≥ 0
3	(0, 0, -1)	0	y₃ ≥ 0
4	(1, 1, 2)	2	y₁ + y₂ + 2y₃ ≤ 2
5	(-1, -1, -2)	-2	y₁ + y₂ + 2y₃ ≥ 2

Constraints 1–3 force y_i ∈ {0, 1} (combined with the domain y_i ∈ {-1, 0, 1}). Constraints 4–5 together force a · y = 2 (subset sums to exactly 2).

Quadratic coefficients: c̄ = (-1, -1, -1).
Linear coefficients: d̄ = (1, 1, 2).

Objective: Minimize Σ (cᵢ yᵢ² + dᵢ yᵢ) = Σ (-yᵢ² + aᵢ yᵢ). For y_i ∈ {0, 1} we have y_i² = y_i, so the objective reduces to Σ (-y_i + a_i y_i) = Σ (a_i - 1) y_i = 0·y₁ + 0·y₂ + 1·y₃.

Expected Outcome

Feasible configurations (satisfying all 5 constraints and y_i ∈ {-1, 0, 1}):

ȳ	a·ȳ	Objective Σ(-yᵢ² + aᵢ yᵢ)
(1, 1, 0)	2	0
(0, 0, 1)	2	1

All other points in {-1, 0, 1}³ violate at least one constraint (either negativity, or a·y ≠ 2).

Optimal solution: ȳ = (1, 1, 0) with objective value 0. This corresponds to the PARTITION solution {a₁, a₂} = {1, 1} summing to 2.

Suboptimal feasible point: ȳ = (0, 0, 1) with objective value 1 (corresponds to {a₃} = {2} summing to 2; same partition, opposite side).

Infeasible examples: (1, 0, 0) (a·y = 1 ≠ 2); (-1, 0, 0) (violates y₁ ≥ 0); (1, 1, 1) (a·y = 4 > 2).

Brute-force over the 27 configurations confirms the optimum is 0.

References

• [Sahni, 1974]: [Sahni1974] S. Sahni (1974). "Computationally related problems". SIAM Journal on Computing 3, pp. 262–279.
• [Vavasis, 1990]: [Vavasis1990] S. A. Vavasis (1990). "Quadratic programming is in NP". Information Processing Letters 36, pp. 73–77.
• [Kozlov, Tarasov, Khachiyan, 1979]: [Kozlov1979] M. K. Kozlov, S. P. Tarasov, L. G. Khachiyan (1979). "The polynomial solvability of convex quadratic programming". Soviet Mathematics Doklady 20, pp. 1108–1111.
• [Jeroslow, 1973]: [Jeroslow1973] Robert G. Jeroslow (1973). "There cannot be any algorithm for integer programming with quadratic constraints". Operations Research 21, pp. 221–224.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but continuous variables are incompatible with codebase dims() framework
Non-trivial	✅ Pass	Distinct from QUBO (constrained, continuous) and ILP (quadratic objective)
Correctness	❌ Fail	Issue claims QP "not known to be in NP" — this was resolved by Vavasis (1990); Klee 1978 reference not verifiable
Well-written	❌ Fail	Variables section acknowledges continuous domain incompatibility but offers no resolution; complexity section lacks a concrete bound

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem does not yet exist in the codebase. QuadraticProgramming is a well-known NP-hard problem (GJ A6 MP2) and is a reasonable addition to the reduction graph.

However, the issue itself acknowledges that continuous rational variables do not fit the dims() framework, which requires finite discrete domains. The codebase's Problem trait assumes dims() returns a vector of finite domain sizes (e.g., [2, 2, 2] for 3 binary variables). A problem with continuous variables cannot implement this interface without discretization or restriction, making it unclear how to actually integrate this model. The Variables section lists three possible workarounds but none is committed to. The only associated rule (R153: PARTITION to QP) is a single inbound reduction with no outbound reductions planned, limiting graph connectivity.

Non-trivial

QuadraticProgramming is genuinely distinct from existing problems:

• QUBO: unconstrained, binary variables, quadratic objective — QP has linear constraints and continuous variables
• ILP: linear objective, integer variables — QP has quadratic objective and continuous variables

The feasibility constraints (linear inequalities over continuous rationals) and objective (quadratic form) are structurally different from all existing models. Pass.

Correctness

Sahni 1974 reference: Verified. Sahni, S., "Computationally Related Problems," SIAM J. Comput. 3 (1974), 262-279. Correctly cited as establishing NP-hardness of QP.

Klee 1978 reference — FAIL: The issue states "not known to be in NP [Klee, 1978]." I was unable to find any 1978 publication by Klee about QP's membership in NP. This appears to be from Garey & Johnson's commentary on the problem (the (*) marker), which they attribute to an observation without a formal paper. More importantly, this claim was resolved in 1990: Vavasis proved that quadratic programming IS in NP (Vavasis, S.A., "Quadratic programming is in NP," Information Processing Letters, 36, 73-77, 1990). This makes QP NP-complete, not merely NP-hard with unknown NP membership. The issue's complexity discussion is therefore outdated by 35+ years.

Horowitz-Sahni 1974 complexity bound: The issue cites O*(2^(n/2)) for the PARTITION-derived case, which is correct for the Horowitz-Sahni meet-in-the-middle algorithm for PARTITION/Subset Sum, but this is the complexity for PARTITION, not for QP in general. No complexity bound is given for general QP.

Kozlov, Tarasov, Khachian 1979: Correctly cited for convex QP polynomial solvability.

Well-written

Missing/incomplete sections:

1. Variables section — FAIL: Explicitly states the problem "does not fit the standard dims() framework" but does not resolve this. An implementable issue must specify exactly how variables will be represented. Three options are listed but none is chosen.

2. Complexity section — FAIL: No concrete complexity string suitable for declare_variants! is provided. The section discusses three different cases (general, convex, PARTITION-derived) without settling on a single best-known bound. The declare_variants! macro requires a single concrete expression like "2^num_vars".

3. How to solve section — FAIL: Neither brute-force nor ILP reduction is checked. The "Other" option describes two separate methods for two separate sub-cases, but the codebase requires at least one solver to verify reductions. Without discrete variables, brute-force enumeration is not possible.

4. Example section: The example is well-constructed and illustrative, showing the PARTITION connection clearly. However, it exercises a very specific sub-case (binary-optimal points) rather than the general continuous QP.

5. Schema section: Uses f64 for all numeric types, which is reasonable for implementation but loses the rational arithmetic semantics of the formal definition.

6. Symbol consistency: Symbols are generally consistent between sections. The notation x-bar, y-bar, c-bar, d-bar is used consistently.

Recommendations

• Update complexity claims: Incorporate Vavasis (1990) to note QP is NP-complete, not merely NP-hard with unknown NP status.
• Resolve the variable domain issue: Either (a) restrict to 0-1 QP (binary quadratic programming), which fits dims() naturally, or (b) propose a new trait extension for continuous problems. Option (a) is strongly recommended as it aligns with the codebase architecture.
• Consider renaming to BinaryQuadraticProgramming if restricting to binary variables, to distinguish from general QP.
• Provide a concrete complexity bound for declare_variants!.

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but continuous variables incompatible with dims() framework; only 1 inbound reduction planned
Non-trivial	✅ Pass	Distinct feasibility constraints and objective from all existing problems
Correctness	❌ Fail	"Klee, 1978" is a misattribution; "not known to be in NP" outdated since Vavasis (1990); example PARTITION interpretation is wrong
Well-written	❌ Fail	Example degenerate (B=0 trivially satisfied everywhere); no concrete complexity bound; variable domain unresolved

Overall: 1 passed, 1 warning, 2 failed

Previously (2026-03-12): 1 passed, 1 warning, 2 failed (Wrong, PoorWritten) — same verdict after re-check.

---

Usefulness

QuadraticProgramming (GJ A6 MP2) does not exist in the codebase (pred show QuadraticProgramming fails). It is a well-known NP-complete problem and a reasonable addition.

Concerns:

• The issue acknowledges continuous rational variables do not fit the dims() framework (which requires finite discrete domains). The Variables section lists three possible workarounds but commits to none.
• Only one associated reduction is planned (R153: PARTITION → QP, inbound). No outbound reductions are mentioned, limiting graph connectivity. Note that Partition currently has no direct reductions registered but has a path to QUBO via Knapsack.

Non-trivial

QuadraticProgramming is genuinely distinct from existing problems:

• QUBO: unconstrained, binary variables, quadratic objective — QP has linear constraints and continuous variables
• ILP: linear objective, integer variables — QP has quadratic objective and continuous variables
• Knapsack: linear objective with capacity constraint — QP has quadratic objective with general linear constraints

The feasibility constraints (linear inequalities over continuous rationals) and objective (quadratic form) are structurally different from all 112 existing problems. Pass.

Correctness

Sahni, 1974 ✅ — Verified. "Computationally Related Problems," SIAM J. Comput. 3(4), 262-279. Correctly cited as establishing NP-hardness of QP via transformation from PARTITION.

"Klee, 1978" ❌ — Misattribution. No standalone 1978 Klee publication on QP's NP membership exists. Victor Klee was the series editor of the W.H. Freeman mathematical sciences series in which Garey & Johnson's book was published. The "not known to be in NP" observation is Garey & Johnson's own commentary (the (*) marker), not a result from a separate Klee paper. The issue should attribute this to Garey & Johnson (1979) directly.

"Not known to be in NP" ❌ — Outdated by 35+ years. Vavasis proved QP is in NP in: Vavasis, S.A., "Quadratic Programming is in NP," Information Processing Letters, 36, 73-77, 1990 (ScienceDirect, Cornell eCommons). Combined with Sahni's NP-hardness result, QP is NP-complete. The (*) marker from GJ no longer applies.

Horowitz & Sahni, 1974 ✅ — Verified. O*(2^(n/2)) meet-in-the-middle for PARTITION is correct, but this is the complexity for PARTITION, not for QP in general.

Kozlov, Tarasov, Khachiyan, 1979 ✅ — Verified. Polynomial solvability of convex QP is correct.

General QP complexity — No concrete bound of the form O*(c^n) exists in the literature for general non-convex QP. The issue provides no complexity expression suitable for declare_variants!.

Example PARTITION interpretation ❌ — The issue claims y = (1, 0, 1, 0) corresponds to partitioning {3, 5, 7, 1} into {3, 5} and {7, 1}. This is wrong: y = (1, 0, 1, 0) selects items at indices 0 and 2, which are weights 3 and 7 (sum = 10), not {3, 5} (sum = 8). The correct partition {3, 5} | {7, 1} would correspond to y = (1, 1, 0, 0).

Well-written

4a — Information Completeness:

Section	Status
Motivation	✅ Present
Name	✅ QuadraticProgramming
Reference	⚠️ "Klee 1978" is a misattribution (see Correctness)
Definition	✅ Formal definition from GJ
Variables	❌ Acknowledges dims() incompatibility but commits to no resolution
Schema	⚠️ Uses f64 for rationals — loses exact arithmetic semantics
Complexity	❌ No concrete expression for declare_variants!; discusses three sub-cases without settling on one
How to solve	❌ Neither brute-force nor ILP checked; "Other" describes two methods for two sub-cases
Example Instance	❌ Degenerate (see 4d)
Expected Outcome	❌ PARTITION interpretation is wrong

4b — Definition Completeness: The formal definition from GJ is well-formed and precise. Pass.

4c — Symbol Consistency: Symbols (x̄, ȳ, c̄, d̄, B) are used consistently across sections. Pass.

4d — Example Quality:

Python validation found critical issues:

• ❌ PARTITION interpretation wrong: y = (1, 0, 1, 0) selects {3, 7} (sum = 10), not the claimed {3, 5} (sum = 8). The valid partition is {3, 5} | {7, 1}, corresponding to y = (1, 1, 0, 0).
• ❌ Degenerate instance: The objective equals Σ wᵢ · yᵢ · (1 − yᵢ) with positive weights wᵢ = {3, 5, 7, 1}. This is non-negative on [0,1]ᵐ, so with B = 0, every feasible point satisfies the threshold. The answer is trivially YES regardless of input structure.
• ❌ No discrimination at binary points: All 16 binary corner points give objective = 0 = B. There is no binary point that fails the threshold, so brute-force over corners cannot distinguish YES from NO.
• ⚠️ Non-trivial encoding would need B > 0. The analytical maximum objective is 4.0 at y = (0.5, 0.5, 0.5, 0.5). Setting B to a positive value would create actual selectivity.
• Stats: 16 binary points, all feasible, all meeting threshold. 1 unique equal partition exists ({3,5} | {7,1}). Max objective = 4.0.

4e — Representation Feasibility: The f64 type cannot exactly represent rational arithmetic. For the specific PARTITION-derived form, binary variables suffice, but the issue does not commit to this restriction. Warn.

Recommendations

1. Update complexity claims: QP is NP-complete (Vavasis 1990), not merely NP-hard with unknown NP status
2. Remove "Klee, 1978": Attribute the (*) observation to Garey & Johnson (1979) directly
3. Resolve the variable domain: Either (a) restrict to 0-1 QP / Binary Quadratic Programming (fits dims() naturally, aligns with the PARTITION reduction), or (b) propose a trait extension for continuous problems. Option (a) is strongly recommended
4. Fix the example: Correct the PARTITION interpretation (y should be (1,1,0,0) not (1,0,1,0)), and use B > 0 to create non-trivial selectivity
5. Provide a concrete complexity bound for declare_variants! — for 0-1 QP, "2^num_vars" would be a naive upper bound
6. Check at least one solver method — if restricting to binary variables, brute-force becomes feasible

[isPANN]

Implementation note: build as optimization

This model should be implemented as an optimization problem (Value = Min<f64> or similar), not a decision problem with a bound field.

• Objective: Minimize (or maximize) the quadratic objective xᵀQx + cᵀx subject to linear constraints Ax ≤ b
• Do not add a threshold on the objective value — let the solver find the optimum directly
• This is one of the few models where optimization is the most natural formulation even in G&J (marked with * for not known to be in NP)

See #765 for context on the decision-vs-optimization policy.