1

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.

Τίμων
  • 1,669
deepesh
  • 21

2 Answers2

3

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
mvw
  • 34,562
1

LP should be able to solve it, but it cannot work with equalities.

For example a+b = 5 has to be transformed into:

a + b <= 5

a + b >= 5 -- which should be further transformed --> -a + -b <= -5 (The reason behind this, that durring the simplex method all relation should point to the same direction. Meaning all constrains must be either "less "or "less or equal")

Some LP engines takes care of this.

If something infeasable it could mean two thing: The solution set of the equitations is empty. Like x < 10 and x > 11

There is no constrains which limit the results. For example looking for a solution for the two constrain x + y < 3 & x + y > 1, than for no matter what x you will find an y which meets critera. Some LP implementations treats them infeasable but others correctly reports it as no constrains/unbounded. (constant = 1 is something like this. It is unbounded on the right )

I've tried your problem to solve it with Excel Solver (It has LP implementation) and worked: I cannot share the image but here are the steps. (First in Excel enable the Solver Extension if it haven't been already) Leave cells from A1 to E1 empty. (These will be your variables a,b,c...) Than you need 7 entries. In column F the formulas and in G your constrains:

column F | columng G

=A1 + B1 + D1| 10

=B1 + C1 + D1| 12

... etc

Than click on the solver button. (At the Data tab) Select maximising on the form and select any cell except A1, B1..., E1 or the constrains for objective (You don't need objective because we are not maximising) By Changin Varriable Cells list the cells: A1,B1,C1,D1,E1 (I put in the form: \$A\$1:\$E\$1)

For constrains (I put the formulas in the colum F and constrains G) Add

formulas: \$F\$1:\$F\$8

constain: make sure you select the "=" sign. (This what I referred earlier. Excel takes care of equality and transforms into inequalities)

constrains: \$G\$1:\$G\$8

Select the simplex method (It is the LP procedure) and hit solve

Hope this helps

David Cifer
  • 11
  • I tried to share the Excel spread sheet but I cannot find how to upload it. – David Cifer Apr 04 '16 at 16:43
  • The modeling of the constraints depends on what form your LP solver accepts ($Ax = b$, $Ax \le b$, $x \in \mathbb{R}^n$, $x \in \mathbb{R}^n_+$). The forms are equivalent, one can be transformed into another, as you demonstrated for your case. – mvw Apr 04 '16 at 17:45