# Underdertermined system of equations

Let's say we have 2 equations and 3 variables (N equations and M variables, where M > N), for example:

0.3a+0.1b+0.2*c=10 + E

0.1a+0.2b+0.3*c=11 + E

We want to find a, b, c that are in the range [0.0, 1.0] and we want to minimize the error E.

We want a smooth solutions that in this context means that if we chart a, b, c in a chart, the chart is smooth.

How this kind of problems can be approached with sagemath?

edit retag close merge delete

This kind of problems can be solved with MILP - see details and examples at https://doc.sagemath.org/html/en/them...

( 2024-04-16 12:44:25 +0200 )edit

Hello, in my case all variables are non-integer (can have decimals)

( 2024-04-16 12:59:26 +0200 )edit

That's fine. MILP supports non-integer variables as well.

( 2024-04-16 13:13:26 +0200 )edit

In fact it's not $E$ which should be minimized but $|E|$. So the problem should receive a special formalization which can transform a minimization of an absolute value (which is not linear) in the minimization of an affine objective. This can be correctly be done as Max underline with MixedIntegerLinearProgram in SageMath. Elle if you need some help I can write the program for ypu.

( 2024-04-18 10:45:24 +0200 )edit

Good catch! E is actually |E|. If you have any example of how to code the system would be great!

( 2024-04-19 11:15:28 +0200 )edit

Sort by ยป oldest newest most voted

Here is an example, in which we use x[0], x[1], x[2] for a, b, c, and x[-1] for the (absolute) bound for errors.

milp = MixedIntegerLinearProgram(maximization=False) # we do minimization

x = milp.new_variable(real=True)
milp.set_min(x[0],0)
milp.set_min(x[1],0)
milp.set_min(x[2],0)
milp.set_max(x[0],1)
milp.set_max(x[1],1)
milp.set_max(x[2],1)

eq1 = 0.3*x[0] + 0.1*x[1] + 0.2*x[2] - 10

eq2 = 0.1*x[0] + 0.2*x[1] + 0.3*x[2] - 11

milp.set_objective(x[-1])    # minimize the error bound

milp.solve()
print( milp.get_values(x) )


The code produces the following result: {0: 1.0, 1: 1.0, 2: 1.0, -1: 10.4}, that is $a=b=c=1.0$, and the maximum error of $10.4$.

more

Thanks a lot!

I can see that f = |E|

is translated as f <= E f >= -E

but let's suppose that E=5 and f=4, the translated system of equations will be true in this case while 4 = |5| is false

( 2024-04-21 00:58:58 +0200 )edit

Errors may differ across the equations. x[-1] bounds their absolute values from above.

( 2024-04-21 02:27:57 +0200 )edit