Solutions of a system of linear equations

[h6ss]

Hello,

I am working on a hybrid simulation-optimization problem of a hamiltonian cycle in two-dimensional Euclidean space, and have encountered the following problem:

Say I have a system of N linear equations and M unknowns, where M > N, with the following constraints:

1. Every coefficient of every unknown has to be equal to 1;
2. Every unknown appears exactly twice;
3. There are exactly two equations of the form x_i + x_j = 1;
4. All the other equations are equal to 2;
5. Every equation must have at least 2 unknowns;
6. The unknowns are expected results of a Heaviside step function, therefore they can only take the values 0 or 1.

Also, if you sum all the equations and divide both sides by 2, you get:

\sum_{i=1}^{M} x_{i} = N-1

Therefore, for any solution, there will be exactly (N - 1) 1's and (M - (N - 1)) 0's.

Here is an example of such system where N = 11 and M = 15:

1 = x₁ + x₄
2 = x₂ + x₃ + x₁₀
2 = x₅ + x₃ + x₁₄
2 = x₁ + x₅ + x₆ + x₈
2 = x₇ + x₉ + x₁₁
2 = x₉ + x₁₃
2 = x₄ + x₁₂ + x₁₃ + x₁₅
2 = x₁₀ + x₁₁
2 = x₂ + x₈ + x₁₅
2 = x₆ + x₁₂
1 = x₇ + x₁₄

My question is, how many solutions does a generalized version of this system has?

Is there a fast way to find these solutions? A deterministic algorithm of any kind?

The only programming software I'm good with is R, and I haven't found a way to simulate this on R's platform yet.

Thanks in advance!

 

[AlephZero]

For small size problems, a "brute force" idea would be to do an elimination procedure to express all the variables in terms of $M-N$ "master" variables, and then use trial and error for the $2^{M-N}$ possiible solution sets.

But for your example problem, you get several values direct from the equations and the constraint that the solutions are all 0 or 1:

$x_9 = x_{13} = 1$, $x_{10} = x_{11} = 1$, $x_6 = x_{12} = 1$.

Substituting in those values, you get some more values ... is there something general about the structure of the equations that you can exploit here?

A completely different approach would be to add the equations $x_k(1-x_k) = 0$, $k = 1\dots M$ and throw everything at a nonlinear equation solver. But that might run into problems finding all possible solutions.

 

[h6ss]

Substituting in those values, you get some more values ... is there something general about the structure of the equations that you can exploit here?

Most likely there is, and this method would simplify my specific example, but I believe every simulation will have its own unique structure, therefore it will be hard to extrapolate a generalized structure from only a limited number of simulations, wouldn't it? I've tried running thousands of simulations and look for common structure between one and another and I haven't been able to find something interesting yet.

A completely different approach would be to add the equations $x_k(1-x_k) = 0$, $k = 1\dots M$ and throw everything at a nonlinear equation solver. But that might run into problems finding all possible solutions.

That's interesting. It's a pretty accurate method in my opinion, but only to solve a particular system. I'm looking for a method that would solve (or at least attempt to) for fixed but unknown values of M and N.

After some time working on this problem I have started being rather pessimistic about finding all solutions in practice. Some people said that the counting problem is #P-hard and a lattice-point enumeration problem of this kind is probably impossible to solve. How accurate are those claims?

I'm starting to believe that I might be able to do better by exploiting the structure of specific simulations, but I wouldn't know where to start. I'd be interested in suggestions about this if anyone has any idea. Thank you!

 

[Bipolarity]

I'm curious to know what motivated this problem, and specifically, how it is related to the Hamiltonian path/cycle problems?

BiP

 

[h6ss]

I'm curious to know what motivated this problem, and specifically, how it is related to the Hamiltonian path/cycle problems?

BiP

For the learning of a neural network, I am trying to find a different method to determine the number of hamiltonian paths between two chosen points in a square lattice.

In this system, each variable corresponds to an edge and each equation illustrates the "behaviour" of the system at every point. Basically, every variable appears exactly twice because every edge connects two points. The starting and ending points are equal to 1 because the operation around them is unidirectional, while all the other equations are equal to 2 because they operate bidirectionally.

More exactly, a two-dimensional finite square lattice is generated to help represent the different paths available from a chosen starting point to a chosen ending point. The paths are hamiltonian because each simulation requires our neural network to visit every point exactly once. In the end, we want to teach the network to take an autonomous and optimized decision according to the number of paths found. A generalized solution for the system would give us an idea of how the network would behave knowing only the starting/ending points, independently of the distance that separates them.