Ask Your Question

Underdertermined system of equations

asked 2024-04-16 12:01:19 +0200

elle gravatar image

updated 2024-04-16 22:41:14 +0200

Max Alekseyev gravatar image

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 flag offensive close merge delete


This kind of problems can be solved with MILP - see details and examples at

Max Alekseyev gravatar imageMax Alekseyev ( 2024-04-16 12:44:25 +0200 )edit

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

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

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

Max Alekseyev gravatar imageMax Alekseyev ( 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.

Cyrille gravatar imageCyrille ( 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!

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

1 Answer

Sort by ยป oldest newest most voted

answered 2024-04-20 00:50:00 +0200

Max Alekseyev gravatar image

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)

eq1 = 0.3*x[0] + 0.1*x[1] + 0.2*x[2] - 10
milp.add_constraint( eq1 <= x[-1] )
milp.add_constraint( eq1 >= -x[-1] )

eq2 = 0.1*x[0] + 0.2*x[1] + 0.3*x[2] - 11
milp.add_constraint( eq2 <= x[-1] )
milp.add_constraint( eq2 >= -x[-1] )

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

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$.

edit flag offensive delete link 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

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

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

Max Alekseyev gravatar imageMax Alekseyev ( 2024-04-21 02:27:57 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2024-04-16 12:01:19 +0200

Seen: 248 times

Last updated: Apr 20