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 - The Fusion of Science and Community**

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

Loading...

Similar Threads - Solutions system linear | Date |
---|---|

Inhomogeneous Linear System Solutions | Aug 11, 2014 |

Unique solution to an arbitrary monotonic non-linear system | Aug 5, 2014 |

Solution of system of non-linear equations | Jun 15, 2014 |

Linear systems: zero, one, infinite solutions | Sep 22, 2012 |

Existent solution to the linear system Ax=b | Jun 21, 2012 |

**Physics Forums - The Fusion of Science and Community**