5
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ In general finding one solution is NP complete, check en.wikipedia.org/wiki/Integer_programming $\endgroup$
    – joro
    Nov 2, 2011 at 8:37
  • $\begingroup$ A minor correction: You mean to say that any solution will have K+1-N 0's (not N-K-1). $\endgroup$ Nov 2, 2011 at 11:16
  • $\begingroup$ @joro Yep, but is there a fast way to know the number of solutions? $\endgroup$
    – Bee San
    Nov 2, 2011 at 13:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – joro
    Nov 2, 2011 at 13:52
  • 1
    $\begingroup$ @Gerhard are sure sharp 2SAT is efficient? What I read and the wikipedia page say otherwise. Note the OP is counting, not solving. $\endgroup$
    – joro
    Nov 3, 2011 at 6:12

6 Answers 6

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Nov 4, 2011 at 0:14
  • $\begingroup$ 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. $\endgroup$
    – joro
    Nov 4, 2011 at 5:58
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2011 at 15:26
  • 1
    $\begingroup$ @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... $\endgroup$
    – joro
    Nov 2, 2011 at 16:28
  • $\begingroup$ @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. $\endgroup$ Nov 4, 2011 at 0:04
  • $\begingroup$ @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. $\endgroup$ Nov 4, 2011 at 0:07
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Hamiltonian cycle is NP-complete for planar cubic graphs, I suppose you can represent these on a grid. $\endgroup$ Nov 3, 2011 at 17:26
  • $\begingroup$ 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! $\endgroup$ Nov 3, 2011 at 17:32
  • $\begingroup$ Isn’t it already mentioned in the original question? $\endgroup$ Nov 3, 2011 at 17:42
  • $\begingroup$ 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. $\endgroup$ Nov 3, 2011 at 18:36
  • 2
    $\begingroup$ 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? $\endgroup$
    – Bee San
    Nov 3, 2011 at 20:03
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry: a small mistake: There are exatly 5 (not 4) solutions. $\endgroup$
    – sedjelmaci
    Mar 19, 2014 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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