[Model] FeasibleBasisExtension

[isPANN]

Motivation

FEASIBLE BASIS EXTENSION (P210) from Garey & Johnson, A6 MP4. A classical NP-complete problem arising in linear programming theory. The problem asks whether a linear system Ax = b, x >= 0 has a feasible basis containing a prescribed set of columns -- a fundamental question in simplex-method initialization and LP sensitivity analysis. Its NP-completeness (Murty 1972, via reduction from HAMILTONIAN CIRCUIT) shows that even basic structural questions about LP bases can be computationally hard.

Associated rules:

• R155: Hamiltonian Circuit -> Feasible Basis Extension (Murty 1972)
• [Rule] Feasible Basis Extension to ILP #784: Feasible Basis Extension -> ILP (Big-M linearization)

Definition

Name: FeasibleBasisExtension
Canonical name: Feasible Basis Extension; also: Basis Extension Problem
Reference: Garey & Johnson, Computers and Intractability, A6 MP4

Mathematical definition:

INSTANCE: An m x n integer matrix A, m < n, a column vector a-bar of length m, and a subset S of the columns of A with |S| < m.
QUESTION: Is there a feasible basis B for Ax-bar = a-bar, x-bar >= 0, i.e., a nonsingular m x m submatrix B of A such that B^{-1}a-bar >= 0, and such that B contains all the columns in S?

A "feasible basis" B is a set of m column indices such that the corresponding m x m submatrix A_B is nonsingular and the basic solution x_B = A_B^{-1} a-bar satisfies x_B >= 0 (with all non-basic variables set to zero). The extension requirement is that a prescribed subset S of columns must be included in B.

Variables

• Count: n - |S| binary variables (one per column of A not already in S), deciding which additional columns to include in the basis.
• Per-variable domain: binary {0, 1} -- whether column j (not in S) is selected for the basis.
• Meaning: The configuration selects m - |S| additional columns from A \ S to form a basis B = S union {selected columns}. The assignment is satisfying if (1) |B| = m, (2) A_B is nonsingular, and (3) A_B^{-1} a-bar >= 0.

Schema (data type)

Type name: FeasibleBasisExtension
Variants: none (integer matrix with no graph/weight parameterization)

Field	Type	Description
matrix	Vec<Vec<i64>>	The m x n integer matrix A (row-major)
rhs	Vec<i64>	The column vector a-bar of length m
required_columns	Vec<usize>	The subset S of column indices that must appear in the basis

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Key getter methods: num_rows() (= m), num_columns() (= n), num_required() (= |S|).
• The matrix entries are integers (matching the GJ definition).

Complexity

• Decision complexity: NP-complete (Murty, 1972; transformation from HAMILTONIAN CIRCUIT).
• Best known exact algorithm: Brute-force enumeration of all C(n - |S|, m - |S|) subsets of columns to extend S, checking nonsingularity and nonnegativity of B^{-1}a-bar for each candidate basis. Time: O(C(n - |S|, m - |S|) * m^3) where m^3 is the cost of matrix inversion/solving. No sub-exponential algorithm is known.
• Complexity string for declare_variants!: "2^num_columns * num_rows^3" (conservative upper bound; the binomial coefficient C(n-|S|, m-|S|) <= 2^n).
• Special cases: When |S| = 0 (no required columns), the problem reduces to finding any feasible basis, which is equivalent to Phase I of the simplex method and can be solved in polynomial time. When |S| = m - 1, only one column needs to be chosen, and the problem is solvable in O(n * m^2) time.
• References:
  • K.G. Murty (1972). "A fundamental problem in linear inequalities with applications to the travelling salesman problem." Mathematical Programming 2(3), pp. 296-308. The reduction from Hamiltonian Circuit is implicit in Murty's constructive approach; Garey & Johnson cite this as the NP-completeness source.
  • R. Chandrasekaran, S.N. Kabadi, K.G. Murty (1982). "Some NP-complete problems in linear programming." Operations Research Letters 1(3), pp. 101-104. Explicitly establishes NP-completeness of several LP basis problems.

Specialization

• This is a special case of: Integer Linear Programming (the feasibility question can be encoded as an ILP).
• Known special cases: When |S| = 0, the problem is equivalent to LP Phase I (polynomial). When the matrix A has special structure (e.g., totally unimodular), the problem may be easier.
• Related problems: Linear Programming feasibility, Basis Enumeration.

Extra Remark

Full book text:

INSTANCE: An m x n integer matrix A, m < n, a column vector a-bar of length m, and a subset S of the columns of A with |S| < m.
QUESTION: Is there a feasible basis B for Ax-bar = a-bar, x-bar >= 0, i.e., a nonsingular m x m submatrix B of A such that B^{-1}a-bar >= 0, and such that B contains all the columns in S?

Reference: [Murty, 1972]. Transformation from HAMILTONIAN CIRCUIT.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all C(n - |S|, m - |S|) ways to extend S to an m-column set B; for each, check that A_B is nonsingular and A_B^{-1} a-bar >= 0. Total time O(C(n,m) * m^3).
• It can be solved by reducing to integer programming. Encode column selection as binary variables, coefficient values via binary expansion, and link them with Big-M constraints. See companion issue: [Rule] Feasible Basis Extension to ILP #784.
• Other: (TBD)

Example Instance

Instance (satisfiable — trivial):

Consider the system Ax = a-bar, x >= 0 with m = 3 rows and n = 6 columns:

A = | 1  0  0  1  1  0 |
    | 0  1  0  1  0  1 |
    | 0  0  1  0  1  1 |

a-bar = (2, 3, 1)^T

Required columns: S = {0} (column 0 must be in the basis).

We need to find a 3 x 3 nonsingular submatrix B containing column 0 such that B^{-1} a-bar >= 0.

Analysis:

• Try B = {0, 1, 2}: A_B = I_3 (identity). B^{-1} a-bar = (2, 3, 1)^T >= 0. This is a feasible basis containing column 0.
• Answer: YES.

Instance (unsatisfiable — trivial):

A = | 1  1  1 |
    | 2  2  3 |

m = 2, n = 3, a-bar = (1, 1)^T, S = {0, 1}.

Required columns S = {0, 1}, so B must be {0, 1} (since |B| = m = 2).
A_B = [[1, 1], [2, 2]], which is singular (columns are linearly dependent).
No feasible basis containing S exists.
Answer: NO.

Non-trivial instance (satisfiable):

A = | 1  0  1  2 -1  0 |
    | 0  1  0  1  1  2 |
    | 0  0  1  1  0  1 |

m = 3, n = 6, a-bar = (7, 5, 3)^T, S = {0, 1} (columns 0 and 1 must be in the basis).

Need to pick one more column from {2, 3, 4, 5} to form a 3-column basis B.

Exhaustive analysis of all 4 candidate extensions:

1. B = {0, 1, 2}:
   A_B = [[1,0,1],[0,1,0],[0,0,1]]. det(A_B) = 1 (nonsingular).
   Solve A_B x = (7,5,3)^T: row 3 gives x_2 = 3; row 2 gives x_1 = 5; row 1 gives x_0 = 7 - 3 = 4.
   x_B = (4, 5, 3)^T >= 0. Feasible basis. ✅

2. B = {0, 1, 3}:
   A_B = [[1,0,2],[0,1,1],[0,0,1]]. det(A_B) = 1 (nonsingular).
   Solve A_B x = (7,5,3)^T: row 3 gives x_3 = 3; row 2 gives x_1 = 5 - 3 = 2; row 1 gives x_0 = 7 - 6 = 1.
   x_B = (1, 2, 3)^T >= 0. Feasible basis. ✅

3. B = {0, 1, 4}:
   A_B = [[1,0,-1],[0,1,1],[0,0,0]]. det(A_B) = 0 (singular). Not a valid basis. ❌

4. B = {0, 1, 5}:
   A_B = [[1,0,0],[0,1,2],[0,0,1]]. det(A_B) = 1 (nonsingular).
   Solve A_B x = (7,5,3)^T: row 3 gives x_5 = 3; row 2 gives x_1 = 5 - 6 = -1.
   x_B = (7, -1, 3)^T. x_1 < 0. Not feasible (nonnegativity violated). ❌

Summary: 2 feasible bases ({0,1,2} and {0,1,3}), 1 singular, 1 infeasible. Answer: YES.

The two feasible bases yield different basic solutions — (4,5,3) vs (1,2,3) — confirming the instance is non-trivial and exercises both the nonsingularity and nonnegativity checks.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem with discrete variables; however, associated reduction requires HamiltonianCircuit which is not in the codebase
Non-trivial	✅ Pass	Genuinely distinct from all existing problems
Correctness	❌ Fail	Non-trivial example has incorrect solution values; Murty 1972 reference verified
Well-written	⚠️ Warn	Mostly complete but missing concrete complexity string; ILP encoding described as "non-trivial" without details

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not exist in the codebase. FeasibleBasisExtension is a legitimate NP-complete problem from Garey & Johnson (A6 MP4).

Positive: Unlike issues #528 and #529, this problem has discrete binary variables (selecting which columns to include in the basis), making it compatible with the dims() framework. Each non-required column is a binary choice, so dims() = vec![2; n - |S|].

Warning: The only associated reduction is from Hamiltonian Circuit, which is not currently implemented in the codebase. This means the problem would be an orphan node until HamiltonianCircuit is added. The motivation section does not discuss any outbound reductions from FeasibleBasisExtension to existing problems.

Non-trivial

FeasibleBasisExtension is genuinely distinct from all existing problems:

• It involves matrix nonsingularity and nonnegativity constraints, which are structurally different from graph, formula, or set problems
• It is not a variant of ILP (though the feasibility can be encoded in ILP, the basis-extension constraint with nonsingularity is a distinct structural requirement)
• The combination of subset selection + matrix inversion + nonnegativity is unique among existing models

Pass.

Correctness

Murty 1972 reference — Verified: K.G. Murty, "A fundamental problem in linear inequalities with applications to the travelling salesman problem," Mathematical Programming 2(1), pp. 296-308, 1972. The paper exists on Springer (https://link.springer.com/article/10.1007/BF01584550) and establishes the NP-completeness via reduction from Hamiltonian Circuit, consistent with Garey & Johnson's citation.

Non-trivial example — FAIL: The third example contains an arithmetic error. For the matrix:

A = | 1  0  2  1  0  3 |
    | 0  1  1  0  2  1 |
    | 1  1  0  2  1  0 |

with a-bar = (4, 3, 5)^T, S = {0, 3}, the issue claims B = {0, 3, 1} yields x_0 = 3, x_3 = 1, x_1 = 2. However, solving A_B x = a-bar with A_B = [col0, col3, col1]:

| 1  1  0 |   | x_0 |   | 4 |
| 0  0  1 | * | x_3 | = | 3 |
| 1  2  1 |   | x_1 |   | 5 |

Row 2 gives x_1 = 3. Row 1 gives x_0 + x_3 = 4. Row 3 gives x_0 + 2x_3 + 3 = 5, so x_0 + 2x_3 = 2. Subtracting: x_3 = 2 - 4 = -2 < 0. This basis is not feasible (x_3 is negative). The claimed solution values are incorrect.

First two examples: The satisfiable example (B = {0,1,2} = I_3) and the unsatisfiable example (singular matrix) are correct.

Complexity claims: The brute-force bound O(C(n-|S|, m-|S|) * m^3) is correct. The special case |S| = 0 being polynomial (LP Phase I) is a standard result.

Well-written

Mostly complete, with some gaps:

1. Definition: Well-stated, faithfully reproduces GJ. The additional explanation of feasible basis is helpful.

2. Variables section: Good — correctly identifies binary variables for column selection, compatible with dims(). Count and domain are correct.

3. Schema: Reasonable. Vec<Vec<i64>> for integer matrix matches the definition.

4. Complexity section — Warning: No concrete complexity string for declare_variants! is provided. The brute-force bound involves binomial coefficients, which are not directly expressible in the overhead expression language (+, -, *, /, ^, exp, log, sqrt). A reasonable approximation like "2^num_columns" or equivalent should be specified.

5. How to solve — Warning: Brute-force is checked and described adequately. ILP reduction is checked but described as having "non-trivial" encoding of the nonsingularity constraint via big-M — this needs more detail to be implementable.

6. Example — FAIL: The non-trivial example has incorrect arithmetic (see Correctness section above). The first two examples are correct but trivial (identity matrix, singular matrix).

7. Naming: FeasibleBasisExtension follows codebase conventions (no optimization prefix needed for a satisfaction problem).

Recommendations

• Fix the non-trivial example: Recompute A_B^{-1} a-bar for B = {0, 3, 1} or find a different column extension that actually yields a feasible basis.
• Add a concrete complexity string for declare_variants!, e.g., "2^num_columns * num_rows^3" as an upper bound.
• Flesh out the ILP encoding or remove that solver option if the big-M encoding is not practical.
• Consider adding outbound reductions to improve graph connectivity (e.g., FeasibleBasisExtension -> ILP, or connections to other algebraic problems).

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12 (1 pass, 2 warnings, 1 fail). Re-checking with --force.

Check	Result	Details
Usefulness	❌ Fail	ILP solving claimed but no companion [Rule] FeasibleBasisExtension to ILP issue linked
Non-trivial	✅ Pass	Genuinely distinct — matrix nonsingularity + nonnegativity constraints unique among existing problems
Correctness	❌ Fail	Non-trivial example is wrong (no feasible basis exists); Murty 1972 attribution questionable
Well-written	❌ Fail	Missing complexity string; ILP encoding hand-waved; non-trivial example has incorrect arithmetic

Overall: 1 passed, 0 warnings, 3 failed

Previously: 1 passed, 2 warnings, 1 failed → Now: 1 passed, 0 warnings, 3 failed. HamiltonianCircuit now exists in codebase (previous Usefulness warning resolved), but new issues identified.

---

Usefulness

Problem novelty: FeasibleBasisExtension does not exist in the codebase. ✅

Graph connectivity — improved: HamiltonianCircuit now exists in the codebase (pred show HC), so the planned reduction R155 (HC → FBE) connects to an existing node. Previous check warned HC was missing — this is now resolved.

ILP companion issue — Fail: The "How to solve" section checks the ILP box ("It can be solved by reducing to integer programming") but no companion [Rule] FeasibleBasisExtension to ILP issue is linked in the issue body. Per project conventions, direct ILP solvability claims require a linked companion rule issue. Either:

• Add a "Reduction Rule Crossref" section linking a planned [Rule] FeasibleBasisExtension to ILP issue, or
• Uncheck the ILP box if the big-M encoding is not practical (the issue itself calls it "non-trivial")

Motivation: Solid — LP theory, simplex initialization, sensitivity analysis. ✅

Non-trivial

FeasibleBasisExtension is genuinely distinct from all 112 existing problems:

• Involves matrix nonsingularity AND nonnegativity of the inverse-times-RHS simultaneously
• The subset-extension constraint (prescribed columns must be in the basis) is structurally unique
• Not a variant of ILP — the basis nonsingularity requirement is a distinct structural constraint

Pass.

Correctness

Murty 1972 Reference — ⚠️ Questionable attribution

The paper exists on Springer (DOI: 10.1007/BF01584550):

• Title: "A fundamental problem in linear inequalities with applications to the travelling salesman problem"
• Author: K.G. Murty, 1972, Mathematical Programming
• Issue correction: The issue cites "2(1)" but the paper appears in Volume 2, Issue 3, pp. 296-308

However, the 1972 paper appears to be algorithmic (providing a constructive method), not a complexity-theoretic hardness proof. The NP-completeness of related LP basis problems was later established by Chandrasekaran, Kabadi & Murty in a 1982 paper "Some NP-complete problems in linear programming" (Operations Research Letters). Garey & Johnson cite Murty 1972 for the NP-completeness transformation from Hamiltonian Circuit — GJ's attribution is authoritative, but the claim may be that the reduction is implicit in Murty's constructive approach rather than explicitly stated as NP-completeness (the concept was only formalized by Cook/Karp in 1971-72).

This is not a definitive failure since GJ is the primary source, but the citation should be more precise.

Non-trivial example — ❌ FAIL (confirmed with Python)

The third example claims B = {0, 1, 3} is a feasible basis for:

A = | 1  0  2  1  0  3 |
    | 0  1  1  0  2  1 |
    | 1  1  0  2  1  0 |

with a_bar = (4, 3, 5)^T, S = {0, 3}.

Python verification of ALL 4 candidate extensions from {1, 2, 4, 5}:

Extension	B	det(A_B)	x_B = A_B⁻¹ a_bar	Feasible?
col 1	{0,1,3}	1.0	(6, 3, -2)	❌
col 2	{0,2,3}	1.0	(-9, 3, 7)	❌
col 4	{0,3,4}	-2.0	(4.5, -0.5, 1.5)	❌
col 5	{0,3,5}	-1.0	(-15, 10, 3)	❌

No feasible basis extension exists. The correct answer is NO, not YES. The issue's claimed solution (x_0=3, x_3=1, x_1=2) is wrong — the actual solution for B={0,1,3} is (6, 3, -2).

The first two examples (identity matrix, singular matrix) are correct but trivial.

Complexity claims ✅

The brute-force bound O(C(n−|S|, m−|S|) · m³) is correct. The special case |S|=0 being polynomial (LP Phase I) is standard.

Well-written

Template completeness:

Section	Status
Motivation	✅ Present and substantive
Name	✅ FeasibleBasisExtension follows satisfaction problem naming
Reference	⚠️ Murty 1972 citation has wrong issue number (says 2(1), should be 2(3))
Definition	✅ Well-stated, reproduces GJ faithfully
Variables	✅ Binary variables for column selection, compatible with dims()
Schema	✅ Reasonable (Vec<Vec<i64>>, Vec<i64>, Vec<usize>)
Complexity	❌ No concrete complexity string for declare_variants! — binomial coefficient is not expressible; needs an approximation like "2^num_columns * num_rows^3"
How to solve	❌ ILP checked but encoding described as "non-trivial" without details; no companion issue linked
Example Instance	❌ Non-trivial example is factually wrong (see Correctness)
Expected Outcome	❌ Non-trivial example claims YES but correct answer is NO

Additional issues:

• The non-trivial example needs to be completely replaced with a correct instance that actually has a YES answer
• The example should have multiple feasible and infeasible extensions to properly exercise round-trip testing

Recommendations

• Replace the non-trivial example with a carefully constructed instance where at least one extension yields a feasible basis. A good approach: start with a known feasible basic solution and construct the matrix around it.
• Add a concrete complexity string, e.g., "2^num_columns * num_rows^3" as a conservative upper bound.
• Either flesh out the ILP encoding with concrete constraint formulations or uncheck the ILP box and note it as future work.
• Fix the Murty citation to Volume 2, Issue 3 (not Issue 1).
• Consider citing Chandrasekaran, Kabadi & Murty (1982) "Some NP-complete problems in linear programming" as an additional reference for the NP-completeness result.

Python verification script

import numpy as np

A = np.array([[1, 0, 2, 1, 0, 3],
              [0, 1, 1, 0, 2, 1],
              [1, 1, 0, 2, 1, 0]], dtype=float)
a_bar = np.array([4, 3, 5], dtype=float)
S = {0, 3}
for c in [1, 2, 4, 5]:
    B = sorted(list(S) + [c])
    A_B = A[:, B]
    x_B = np.linalg.solve(A_B, a_bar)
    print(f"B={B}, x_B={x_B}, feasible={all(x >= 0 for x in x_B)}")
# Output: ALL four candidates have negative components → answer is NO

[isPANN]

Fix-issue changelog

• Fixed Murty 1972 citation: Volume 2(1) → 2(3) per Springer metadata
• Added supplementary reference: Chandrasekaran, Kabadi & Murty (1982) for explicit NP-completeness proof
• Added complexity string: "2^num_columns * num_rows^3" for declare_variants!
• Kept ILP box checked: Created companion issue [Rule] Feasible Basis Extension to ILP #784 ([Rule] Feasible Basis Extension to ILP) with Big-M linearization encoding
• Updated Associated rules: Added [Rule] Feasible Basis Extension to ILP #784 (FBE → ILP)
• Replaced non-trivial example: Old example had no feasible basis (answer was NO, not YES). New 3×6 instance with S={0,1} has 2 feasible, 1 singular, 1 infeasible extension — verified by Python (numpy.linalg.solve)

Applied by /fix-issue.