How many 0, 1 solutions would this system of underdetermined linear equations have?

Question

The problem:

I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.

Here's an example with N=11 equations and K=15 unknowns:

$1 = x_1 + x_9$
$2 = x_{1} + x_{2} + x_{10}$
$2 = x_{2} + x_{3} + x_{11}$
$2 = x_{3} + x_{12}$
$2 = x_{9} + x_{4} + x_{13}$
$2 = x_{10} + x_{4} + x_{5} + x_{14}$
$2 = x_{11} + x_{5} + x_{6} + x_{15}$
$2 = x_{12} + x_{6}$
$2 = x_{13} + x_{7}$
$2 = x_{14} + x_{7} + x_{8}$
$1 = x_{15} + x_{8}$

Things that will always hold true in the general case:

• Every coefficient is $1$.
• In the entire collection of equations, each $x_i$ appears exactly twice.
• There are exactly two equations of the form $x_i + x_j = 1$.
• All the other equations will have $2$ as the constant.

Some observations:

• If you sum all of the above equations and divide both sides by $2$, you get $\sum_{i=1}^{i=K}x_i=N-1$. In this case,
  $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 10$.
  So, in any solution, there will be exactly N-1 1's and K-(N-1) 0's.

My Questions:

• How many solutions does this general system have?
• Is there a fast way to find these solutions?

FWIW, I encountered this problem when trying to find the longest (hamiltonian) path between two points in a square lattice.

Answer 1

In complexity terms, no "efficient" (polynomial time) solution is likely.

However in practical terms you may be able to solve quite large problems of this nature, either by using integer linear programming software (I recommend Gurobi) or constraint satisfaction programming software.

For example, here is how you would do it in the CSP solver "Minion"

Create a file called something like "problem.min" containing the following (notice that I have changed x15 to x[0] to use an array of variables).

MINION 3
**VARIABLES**
BOOL x[15]
**CONSTRAINTS**
sumgeq([x[1],x[9]],1)
sumleq([x[1],x[9]],1)

sumgeq([x[1],x[2],x[10]],2)
sumleq([x[1],x[2],x[10]],2)

sumgeq([x[2],x[3],x[11]],2)
sumleq([x[2],x[3],x[11]],2)

sumleq([x[3],x[12]],2)
sumgeq([x[3],x[12]],2)

sumleq([x[9],x[4],x[13]],2)
sumgeq([x[9],x[4],x[13]],2)

sumgeq([x[10],x[4],x[5],x[14]],2)
sumleq([x[10],x[4],x[5],x[14]],2)

sumleq([x[11],x[5],x[6],x[0]],2)
sumgeq([x[11],x[5],x[6],x[0]],2)

sumleq([x[6],x[12]],2)
sumgeq([x[6],x[12]],2)

sumleq([x[7],x[13]],2)
sumgeq([x[7],x[13]],2)

sumleq([x[7],x[8],x[14]],2)
sumgeq([x[7],x[8],x[14]],2)

sumgeq([x[8],x[0]],1)
sumleq([x[8],x[0]],1)

**EOF**

(Notice that minion makes the somewhat idiosyncratic decision to require equalities to be expressed as two opposite inequalities, but apart from that the syntax is obvious.)

Then just run

$ minion -findallsols problem.min

In less than 0.05 seconds it reports 5 solutions.

Answer 2

As other people noted, this is a #P-hard problem and you cannot hope to count the solutions in time which is polynomial in the size of the problem. However, in many cases you can do it a lot faster than listing the solutions. You are trying to find all the integer points in some convex polytope. (Include the inequalities $0\le x_i\le 1$ to make sure all integer points are 0-1 points.) This is lattice point enumeration, see for example the software Latte at http://www.math.ucdavis.edu/~latte/.

Answer 3

As noted, the general case is believed to be hard.

You can simplify your specific example though.

The equations $2=a+b$ mean both $a$ and $b$ are $1$ - check all possibilities.

The equations $1=a+b$ mean exactly one is $1$ or $a=1-b$.

One can plug the above simplifications in the other equations and one gets a simpler problem.

[added] If I had to solve the problem, I would convert it to SAT and use a sharpsat solver, possibly something based on d-DNNF or BDD.

Answer 4

It may be obvious to the casual observer, but it only just hit me recently that Hamiltonian cycle can be reduced to this problem, so of course the decision and counting problems are hard. I do not know if it gets easier when restricted to subgraphs of a rectangular 2d grid, but casting it in this form will not make it any easier.

Gerhard "Ask Me About System Design" Paseman, 2011.11.03

Answer 5

Your problem is an instance of what is (also) known as Binary Integer Programming. As noted in the other answers, the decision problem is NP-complete and the counting problem is #P-hard.

I do know that there has been some work on finding solutions, and there are libraries available that are pretty efficient. (I've played around with lp_solve). Despite the progresses made, my experience with this suggests that computations are prohibitively long on non-trivial instances (unlike some NP-hard problems which have decent practical algorithms). So I'm rather pessimistic about finding all solutions in practice, at least with an out-of-the-box algorithm.

You might be able to do better by exploiting the structure of your specific problems, but I wouldn't know where to start. I'd be interested in suggestions about this myself.

Answer 6

There are exactly 4 solutions which correspond to the 5 cases for x_1, x_2 and x_8, with x_1+x_2 = 1 or 2 and x_2+x_8 = 1 or 2. These 5 solutions are:

x_3=x_12=x_6=x_7=x_13=1 and

x_4=x_1 ; x_5=x_2+x_8 -1 ; /* x_2+x_8 = 1 or 2 */ x_9=1-x_1 ; x_10=2-x_1-x_2 ; /* x_1+x_2 = 1 or 2 */ x_11= 1-x_2 ; x_14 =x_15 =1-x_8 ;

I used an algorithm not yet published. Hope it helps.