[Math] Solving a feasible system of linear equations using Linear Programming

linear algebralinear programmingsystems of equations

I am wondering if one could solve a feasible system of linear equations using a Linear programming approach, instead of standard linear algebra techniques such as gaussian elimination. For instance, below is an overdetermined system:

$$\begin{cases}
a+b+d = 10 \\
b+c+d = 12\\
a+b+c = 9 \\
a+c+d = 11 \\
a+b+e = 15 \\
a+b = 5 \\
b+c = 7
\end{cases}$$

The unique solution to this is
$$\begin{cases}
a = 2\\
b = 3\\
c = 4\\
d = 5\\
e = 10
\end{cases}$$
I tried solving using LP library in python, it says that system is infeasible. I had used a constant objective function (=1) and maximized it. However, I get a message that the system is infeasible. Could someone throw some light on it please?

Thank you.

Best Answer

Your objective function $c^\top x$ seems wrong. Just use \begin{matrix} \min & 0^\top x \\ \text{w.r.t.} & A x = b \end{matrix} and your LP solver should return no solution if there is no solution for $Ax = b$ or otherwise one of the solutions.

Example using lpSolve from R:

If not done already, install lpSolve:

> install.packages("lpSolve")
> install.packages("lpSolveAPI")

Load the library:

> library(lpSolveAPI)

Create a new model in $5$ unknowns and store it in the variable lprec:

> lprec<-make.lp(0,5)

Set the objective function t0 $c = 0$:

> set.objfn(lprec, c(0,0,0,0,0))

Now add the constraints, thus the rows of $A x = b$:

> add.constraint(lprec, c(1,1,0,1,0), "=", 10)
> add.constraint(lprec, c(0,1,1,1,0), "=", 12)
> add.constraint(lprec, c(1,1,1,0,0), "=", 9)
> add.constraint(lprec, c(1,0,1,1,0), "=", 11)
> add.constraint(lprec, c(1,1,0,0,1), "=", 15)
> add.constraint(lprec, c(1,1,0,0,0), "=", 5)
> add.constraint(lprec, c(0,1,1,0,0), "=", 7)

Have a look at the model:

> lprec
Model name: 
            C1    C2    C3    C4    C5       
Minimize     0     0     0     0     0       
R1           1     1     0     1     0  =  10
R2           0     1     1     1     0  =  12
R3           1     1     1     0     0  =   9
R4           1     0     1     1     0  =  11
R5           1     1     0     0     1  =  15
R6           1     1     0     0     0  =   5
R7           0     1     1     0     0  =   7
Kind       Std   Std   Std   Std   Std       
Type      Real  Real  Real  Real  Real       
Upper      Inf   Inf   Inf   Inf   Inf       
Lower        0     0     0     0     0

Now solve:

> solve(lprec)
[1] 0

And check the found optimal value:

> get.objective(lprec)
[1] 0

Then check for the found feasible solution

> get.variables(lprec)
[1]  2  3  4  5 10
Related Question