# Algorithm for solving a linear system of equations with external constraints?

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):

1. a <= b
2. 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:

1. a <= MAX
2. a >= MIN
3. b <= MAX
4. b >= MIN
5. c <= MAX
6. c >= MIN

Now, the system above can be transformed to an equivalent system of equations by introducing dummy variables:

1. a - b + s1 = 0
2. b - c - s2 = c
3. a + s3 = MAX
4. a - s4 = MIN
5. b + s5 = MAX
6. b - s6 = MIN
7. c + s7 = MAX
8. 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!

-
If you aren't trying to optimise anything, you are just solving a set of linear equations. As it appears that the system may be rectangular, try the QR Decomposition to solve the linear system. – Daryl May 11 '13 at 21:50
@Daryl - I understand that, but since I have the implied restriction that all dummy variables need to be greater than 0, standard solution methods do not seem to work in this case (i.e. it is possible to find a solution which satisfies the system per se, but still violates the constraints). What I am interested in is if there is a solution method which solves system while still respecting the constraints. – csvan May 11 '13 at 21:54
See here. What you are doing is able to be done by these algorithms, as it corresponds to item 2 under description on page 2. – Daryl May 11 '13 at 22:07
@Daryl this is gold, thank you so much! – csvan May 11 '13 at 22:11
Ok. I will add as an answer. – Daryl May 12 '13 at 0:31