Hello,(adsbygoogle = window.adsbygoogle || []).push({});

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:

[tex]\sum_{i=1}^{M} x_{i} = N-1[/tex]

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_{1}+ x_{4}

2 = x_{2}+ x_{3}+ x_{10}

2 = x_{5}+ x_{3}+ x_{14}

2 = x_{1}+ x_{5}+ x_{6}+ x_{8}

2 = x_{7}+ x_{9}+ x_{11}

2 = x_{9}+ x_{13}

2 = x_{4}+ x_{12}+ x_{13}+ x_{15}

2 = x_{10}+ x_{11}

2 = x_{2}+ x_{8}+ x_{15}

2 = x_{6}+ x_{12}

1 = x_{7}+ x_{14}

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Solutions of a system of linear equations

**Physics Forums | Science Articles, Homework Help, Discussion**