Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
In general finding one solution is NP complete, check en.wikipedia.org/wiki/Integer_programming –  joro Nov 2 '11 at 8:37
    
A minor correction: You mean to say that any solution will have K+1-N 0's (not N-K-1). –  Barry Cipra Nov 2 '11 at 11:16
    
@joro Yep, but is there a fast way to know the number of solutions? –  Aditya Bhatt Nov 2 '11 at 13:36
1  
Check #P complete secure.wikimedia.org/wikipedia/en/wiki/Sharp_P_complete. Btw, If you can count the solutions, you can find a solution fast - guess a variable, if it is correct you get >0 solutions, otherwise you get 0 so you guessed incorrect. Your specific example might happen to be fast by accident, don't know. –  joro Nov 2 '11 at 13:52
1  
@Gerhard are sure sharp 2SAT is efficient? What I read and the wikipedia page say otherwise. Note the OP is counting, not solving. –  joro Nov 3 '11 at 6:12
show 7 more comments

6 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Nice CSP solver, thank you. –  joro Nov 3 '11 at 6:10
    
If you want to list all solutions, minion is very good. Gordon and I used it to solve a difficult problem in finite geometries recently. If you only want the number of solutions and there are many, you need something like Latte (as in my answer). For example, Latte tells me there are 113399133783022089799549753762945 symmetric nonnegative integer matrices of order 9 with zero diagonal and all row sums equal to 56. Try to do that by listing solutions! –  Brendan McKay Nov 4 '11 at 0:14
    
How does minion compete on large #sat instances compared to #sat solvers like dsharp? BDD and d-DNNF based ones give quite good avarege time according to my tests. –  joro Nov 4 '11 at 5:58
add comment

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/.

share|improve this answer
    
Brendan, I don't see why the hardness of (binary) integer programming implies the hardness of the OP's problem. Don't you have to show that every instance of the known hard problem can be recast as an instance of the OP's problem? Maybe it's obvious how to do this, and I just don't see it. –  Barry Cipra Nov 2 '11 at 15:26
1  
@Breanad I am not entirely sure your wording cannot hope is correct. Exponential worst time does not necessarily mean exponential random instance (or crafted instance) time. On the SAT competition state of the art sat solvers solve quite large random instances... –  joro Nov 2 '11 at 16:28
    
@Barry: Some #P-hard problems like counting perfect matchings in bipartite graphs can be cast into a form matching the OP's problem, so the general case is #P-hard. It doesn't mean that there aren't special cases which are easier. –  Brendan McKay Nov 4 '11 at 0:04
    
@joro: One cannot reasonably hope to have a polynomial time bound for problems like this, unless you think it is reasonable to hope that P=NP. That says nothing about the difficulty of specific instances, and indeed the software I referenced can sometimes solve very large problems. –  Brendan McKay Nov 4 '11 at 0:07
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
Hamiltonian cycle is NP-complete for planar cubic graphs, I suppose you can represent these on a grid. –  Emil Jeřábek Nov 3 '11 at 17:26
    
Gerhard, I'm only a casual observer, but it wasn't obvious to me until you pointed it out just now: Each variable corresponds to an edge of a (generic) graph, and each equation describes what's going on at a vertex. The condition that each variable appears in exactly two equations simply says that an edge connects two vertices. Thank you! –  Barry Cipra Nov 3 '11 at 17:32
    
Isn’t it already mentioned in the original question? –  Emil Jeřábek Nov 3 '11 at 17:42
    
Emil, it was, but its significance was lost on me until Gerhard made it clear -- and even then it took me a few minutes to see how obvious the connection is. –  Barry Cipra Nov 3 '11 at 18:36
2  
Barry, Gerhard, That is indeed how I arrived at this model. I was trying to find a fast way to figure out the number of hamiltonian paths between two arbitrary nodes in a rectangular grid graph with holes. Solving this system is not equivalent to finding that, however. The solution set for this problem includes different hamiltonian paths, and configurations where there are a number of cycles and one path from the start to the end vertex, all tightly packed but edge-and-vertex-disjoint. en.wikipedia.org/wiki/Karp's_21_NP-complete_problems lists both problems. Could be equivalent? –  Aditya Bhatt Nov 3 '11 at 20:03
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Sorry: a small mistake: There are exatly 5 (not 4) solutions. –  sedjelmaci Mar 19 at 11:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.