[Rule] Feasible Basis Extension to ILP

[isPANN]

Source: FEASIBLE BASIS EXTENSION
Target: ILP (0-1 Integer Programming)
Motivation: Provides an outbound reduction from FeasibleBasisExtension to the existing ILP/bool node, enabling ILP-based solving of FBE instances. This connects the algebraic/LP-theoretic problem to the central ILP hub in the reduction graph.

Reference: Standard Big-M linearization technique; see Wolsey, Integer Programming (Wiley, 1998), Ch. 9 for linearization of bilinear terms in mixed-integer formulations.

Reduction Algorithm

Given a FeasibleBasisExtension instance (A, a-bar, S) with A an m x n integer matrix:

Core idea: We seek m columns (containing S) such that their nonnegative conic combination equals a-bar. The column selection is binary; the coefficients are nonnegative reals that we discretize via binary expansion.

Step 1 — Column selection variables:
Introduce binary variables x_j for j = 0..n-1, indicating whether column j is in the basis B.

• Force x_j = 1 for all j in S.
• Add cardinality constraint: sum_j x_j = m.

Step 2 — Coefficient variables (binary expansion):
Let M_bound be an upper bound on the magnitude of any coefficient in A_B^{-1} a-bar (derivable from Cramer's rule: M_bound = m! * max|a_{ij}|^m * max|a-bar_i|). Choose K = ceil(log2(M_bound / delta)) bits of precision with scaling factor delta.

For each column j, introduce K binary variables z_{j,0}, ..., z_{j,K-1} encoding the nonnegative coefficient y_j = delta * sum_{k=0}^{K-1} 2^k * z_{j,k}.

Step 3 — Linking constraints (Big-M):
For each j and k: z_{j,k} <= x_j. This ensures y_j = 0 when column j is not selected.

Step 4 — System equality constraints:
For each row i (i = 0..m-1): sum_{j=0}^{n-1} a_{i,j} * y_j = a-bar_i.
Substituting the binary expansion: sum_{j=0}^{n-1} sum_{k=0}^{K-1} a_{i,j} * delta * 2^k * z_{j,k} = a-bar_i.

Step 5 — Objective:
Empty (feasibility problem). Sense: Minimize.

Solution extraction: From a feasible ILP assignment, read x_j to determine B = {j : x_j = 1}.

Size Overhead

Let n = num_columns, m = num_rows, K = bit precision = O(m * log(max_entry)).

Target metric (code name)	Formula
num_vars	n + n * K = O(n * m * log(max_entry))
num_constraints

Validation Method

• Closed-loop test: construct FBE instance → reduce to ILP/bool → solve ILP → extract column set B → verify A_B is nonsingular and A_B^{-1} a-bar >= 0.

Example

Use the non-trivial example from issue #530:
A = [[1,0,1,2,-1,0],[0,1,0,1,1,2],[0,0,1,1,0,1]], a-bar = (7,5,3)^T, S = {0,1}.
Expected: feasible (B = {0,1,3} with x_B = (1,2,3)).

References

• Garey & Johnson, Computers and Intractability, A6 MP4
• L.A. Wolsey, Integer Programming (Wiley, 1998), Ch. 9 (Big-M linearization)