- #1
h6ss
- 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 xi + xj = 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 = x1 + x4
2 = x2 + x3 + x10
2 = x5 + x3 + x14
2 = x1 + x5 + x6 + x8
2 = x7 + x9 + x11
2 = x9 + x13
2 = x4 + x12 + x13 + x15
2 = x10 + x11
2 = x2 + x8 + x15
2 = x6 + x12
1 = x7 + x14
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 xi + xj = 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 = x1 + x4
2 = x2 + x3 + x10
2 = x5 + x3 + x14
2 = x1 + x5 + x6 + x8
2 = x7 + x9 + x11
2 = x9 + x13
2 = x4 + x12 + x13 + x15
2 = x10 + x11
2 = x2 + x8 + x15
2 = x6 + x12
1 = x7 + x14
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: