Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  chrsva 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! –  chrsva May 11 '13 at 22:11
    
Ok. I will add as an answer. –  Daryl May 12 '13 at 0:31

1 Answer 1

up vote 1 down vote accepted

As mentioned in the comments, this document under point (2) described a solution algorithm for the problem posed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.