Finding the set of all $0$-$1$ vectors in an affine subspace

Question

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) where $\mathbf{1}$ is the all $1$ vector. If there exists such a binary vector then we would like to compute all of them or at least comment on the total number.

Are there any theoretical results in this direction? If not, then can we compute this without going through all $2^n$ possibilities where $n$ is number of columns of $A$?

In full generality it seems to be an NP-complete problem as pointed out here: https://mathoverflow.net/a/97140/34180. So, assume that $A$ is the incidence matrix of a highly symmetrical incidence structure whose full automorphism group is known.

Edit: If the row sum is $r$ and column sum $s$ then this can be interpreted as finding perfect matchings in an $s$-uniform $r$-regular hypergraph. The smallest case I am interested in is a $5$-uniform $5$-regular linear hypergraph (at most one edge through every pair of vertices) which has $1365$ edges (and the same number of vertices). Its full automorphism group is $G_2(4):2$ of order $503193600$.

Answer 1

Even though it is NP-complete, you can do a lot better than searching through all $2^n$ possibilities. In practice, you might try a SAT solver, with the clauses $\bigvee_{j: A_{ij} = 1} x_j$ for each row $i$ and $\overline{x_j} \vee \overline{x_k}$ for each pair $(j,k)$ such that for some row $i$, $A_{ij} = 1$ and $A_{ik} = 1$.
This can sometimes solve a problem with hundreds of clauses and variables in a reasonable time.

Counting or estimating the number of solutions (in a case where that number is not $0$) might be more difficult. See e.g. #-P-complete

Answer 2

You may also like to pose this problem as a Closest Vector Problem and use LLL algorithm to solve it.

Namely, if matrix $A$ has size $m\times n$, multiply it by sufficiently large constant $c$ and extend it at the bottom with an $n\times n$ identity matrix $I$ to get matrix $B=\left[\frac{c\cdot A}{I}\right]$ of size $(m+n)\times n$. Now, if $Ax=\mathbf{1}$, then $Bx$ represent a vector close to the vector $\left[\frac{c\cdot \mathbf{1}}{\mathbf{0}}\right]$. So it is worth to solve CVP for matrix $B$ and vector $\left[\frac{c\cdot \mathbf{1}}{\mathbf{0}}\right]$.

A vector $x$ obtained from solving this CVP problem will have small components, while the choice of $c$ ensures that it satisfies $Ax=\mathbf{1}$. It is not guaranteed to have 0-1 components, but you may be lucky.