- #1

- 77

- 9

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

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,

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

2 = x

2 = x

2 = x

2 = x

2 = x

2 = x

2 = x

2 = x

2 = x

1 = 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!

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!

Last edited: