I am trying to device an algorithm for rapidly solving systems of linear equations/inequalities with constraints, without necessarily relying on existing LP algorithms, such as Simplex. The reason I do not necessarily want to use existing algorithms is because I am only looking to quickly find a general solution to the system, NOT an optimized one.
Some background notes on the algorithm itself:
The algorithm is developed with Java integers as target datatype, and all involved values thus need to respect the constraints imposed by Java on such values. In particular, this means that all such values need to be in the range [2^32-1, 2^32].
While the target values have to be integers, the values may be treated as real numbers during the computational part of the algorithm for the sake of simplicity, and just be rounded of in the result set (i.e. LP relaxation may be used).
Finally, an important basic assumption of the algorithm (due to the context it will be used in) is that a solution ALWAYS exists - there is hence no need to check for feasibility.
Consider the trivial example (a, b and c are Java integers):
- a <= b
- b >= c
Let MIN and MAX be the minimum and maximum possible values of Java integers, respectively. We thus add the following constraints to the system:
- a <= MAX
- a >= MIN
- b <= MAX
- b >= MIN
- c <= MAX
- c >= MIN
Now, the system above can be transformed to an equivalent system of equations by introducing dummy variables:
- a - b + s1 = 0
- b - c - s2 = c
- a + s3 = MAX
- a - s4 = MIN
- b + s5 = MAX
- b - s6 = MIN
- c + s7 = MAX
- c - s8 = MIN
In the above, the additional restriction is imposed that s1...s8 are all >= 0.
Now, this is where I am stuck, and my question is this: what method should I use to solve the above system, seeing as I have to account for the implied constrains on the dummy variables? From what I gather, it would be possible for me to apply the initial phase of the Simplex algorithm (i.e. using the algorithm itself in order to find an initial tableaux), but I do not know if this is the best way to go with performance in mind, since it still involves optimization, and hence potentially several steps of computation.
I am unfortunately not very math savvy, so are there any other theories for systems of equations which I can apply to reach a solution quickly? Thanks in advance!