4
$\begingroup$

Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 to 4 at most), but in exchange, there are a lot of equations (30-60).

The system is known to always have these properties:

  • The equations are linear and nonhomogenous, coefficients and solutions are natural. In other words, equation $k$ has form $a_{k1}x_{k1}+a_{k2}x_{k2}+...+a_{kn}x_{kn}=b_k$ where
    • $b_k\in N$
    • $a_{k1},a_{k2},..,a_{kn} \in N$
    • $x_{k1},x_{k2},..,x_{kn} \in N$
  • There is at least one non trivial solution.

Currently I am going with a bruteforce and heuristic approach that tries to narrow down the range I need to bruteforce before trying out all possible values but it can get messy pretty quick when I get a tricky system.

$\endgroup$
2
  • 1
    $\begingroup$ A standard approach to solve a system of linear equations over the integers is to convert the matrix to Hermite Normal Form (HNF). This can be done in polynomial time. However this might give you solutions with negative numbers; I'm not sure how to correct for that. $\endgroup$ – D.W. Jul 19 '20 at 8:26
  • $\begingroup$ FYI, the phrase you're looking for when doing a web search is "linear Diophantine equations". $\endgroup$ – Pseudonym Nov 16 '20 at 8:45
0
$\begingroup$

You can represent the system as a matrix equation as $Ax = b$, where $k^{th}$ row of $A$ is the coefficients $[a_{k1},a_{k2}...,a_{kn}]$, $x = [x_1, x_2,...,x_n]$ and $b = [b_1,b_2,...,b_m]$.

Unique Solution: If the system has a unique solution, you should be able to get $A$ into row-echelon form. Then, you'll find a row with only one non-zero coefficient, corresponding to an atomic expression like $x_j = b_k$. Plug this in by dropping the $j^{th}$ column and the $k^{th}$ row and updating all other rows as $b_l' = b_l - a_{lj}b_k$. Recursively keep doing this until all values are found. I finally remembered that the name of this procedure: Gaussian Elimination. Here is a nice concise description with a solved example.

Underdetermined System: If there are multiple solutions, then the number of linearly independent rows is less than the number of variables. Since you seem to have many more equations than variables, this is great news. Using the row-echelon form, you can weed out redundant equalities and end up with a much smaller system of equations.

Now, let $$z_k = \min_{\substack{1 \leq i \leq m \\ a_{ki} \neq 0}}\left\{\frac{b_i}{a_{ki}}\right\},$$

so we get $1 \leq x_k \leq z_k$ as the feasible set for each variable. One way to shrink the brute-force approach is to order the variables by their upper bounds. If $z_{k_1} \geq z_{k_2} \geq ... \geq z_{k_n}$, suppose variables satisfy $x_{k_1} \geq x_{k_2} \geq ... \geq x_{k_n}$. Then, you can enumerate the solutions under this constraint by enumerating.

For example, let's say $z_1 = 3, z_2 = 2, ...$. Then, you would have $(3,2,..),...,(3,1,..),...,(2,2,..),...,(2,1,...),...,(1,1,...),...$.

With this ordering assumption you are searching over a much smaller set. Once you have that, you can check the permutations of these solutions and if they are feasible for all variables, they are valid solutions.

For example, for $x_1 + x_2 + x_3 = 3$, let's say we break the tie as $x_1 \geq x_2 \geq x_3$. Then, the constrained solutions are $(3,0,0), (2,1,0), (1,1,1)$ and the permutations of these give you the whole set since they are all the feasible due to $z_1=z_2=z_3$.

$\endgroup$
4
  • $\begingroup$ I used RREF to try and solve my systems before but it is not guaranteed to return a row with a single coefficient. For example, my system can be very simple like $x_1+x_2+x_3=2$, which is guaranteed to have a few solutions (1-1-0, 1-0-1, 0-1-1) but obviously this system cannot be reduced since there is only one equation in the system. Usually my systems have a few dozen equations but this is to give a sense why REF might not work for me. $\endgroup$ – Koko191 Jun 19 '20 at 4:42
  • $\begingroup$ My bad for assuming the existence of unique solutions. Hopefully the edited answer helps with underdetermined systems. $\endgroup$ – curlycharcoal Jun 19 '20 at 6:30
  • 1
    $\begingroup$ The crux seems to be that the list for $z_1=3, z_2=2,\ldots$ is missing: $(1,2,\ldots)$, which is allowed because it's covered by $(2,1,\ldots)$ when permuting the variables (right?). I don't see how that adds value. In the end you're still trying all combination of variable values (i.e. brute-forcing), but only in the context of their upper bounds and using some bounds in the context of already branched variables. I'm sure OP already thought of such bounds. $\endgroup$ – Albert Hendriks Jun 19 '20 at 11:36
  • $\begingroup$ While checking the combination, you’re only checking if the entries of a candidate solution are in the feasible intervals. So it takes $2n$ operations. On the other hand, the naive brute-force search plugs it in the system and checks whether equalities hold, which is still polynomial, but costlier than the former option. The gain in the example is the smallest because $z_k$ are close, but if the difference is large, many cases are reduced from plugging-in to feasibility check. I don’t think the latter cost can be avoided for each combination anyway $\endgroup$ – curlycharcoal Jun 19 '20 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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