3
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Daryl
    May 11, 2013 at 21:50
  • $\begingroup$ @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. $\endgroup$
    – csvan
    May 11, 2013 at 21:54
  • $\begingroup$ 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. $\endgroup$
    – Daryl
    May 11, 2013 at 22:07
  • $\begingroup$ @Daryl this is gold, thank you so much! $\endgroup$
    – csvan
    May 11, 2013 at 22:11
  • $\begingroup$ Ok. I will add as an answer. $\endgroup$
    – Daryl
    May 12, 2013 at 0:31

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .