CODEWITHSUNDEEP
prologlinear-programmingswi-prologsimplex
catbow
catbow

Reputation: 55

Solving linear system of equations with Prolog library Simplex

I am trying to use SWI-Prolog simplex library to solve a linear system of equations with the set of real numbers as domain. Would anyone please have a clue why the following query does not succeed?

maximize(
[],
state(
 0,
 [],
 [ 
   c(0,
    [- 0.95*x(3),0.05*x(0),0.05*x(1),0.05*x(2)],
    =,
    1479754163278877r9007199254740992),
   c(0,
    [0.95*x(2),- 0.05*x(0),- 0.05*x(1),- 0.05*x(3)],
    =,
    185786871969449310676024028079063r3975352282315727403093661252059136
   ),
   c(0,
    [0.95*x(1),- 0.05*x(0),- 0.05*x(2),- 0.05*x(3)],
    =,
    756128230024134313216574233897861r15901409129262909612374645008236544
   ),
   c(0,
    [0.95*x(0),- 0.05*x(1),- 0.05*x(2),- 0.05*x(3)],
    =,
    294112628726237r72057594037927936
   )
 ],
 []
),
S).

The system I intend to solve is the following:

0.05*x(0)+0.05*x(1)+0.05*x(2)-0.95*x(3)
= 
1479754163278877/9007199254740992

- 0.05*x(0)- 0.05*x(1)+0.95*x(2)- 0.05*x(3) 
=
185786871969449310676024028079063/3975352282315727403093661252059136

- 0.05*x(0)+0.95*x(1)- 0.05*x(2)- 0.05*x(3)
=
756128230024134313216574233897861/15901409129262909612374645008236544

0.95*x(0)- 0.05*x(1)- 0.05*x(2)- 0.05*x(3)
=
294112628726237/72057594037927936

Alternatively, would you please know a better way to solve this in Prolog?

Upvotes: 2

Views: 335

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16772

It looks like the solver assumes all variables are non-negative. So the question becomes: can we reformulate Ax=b, where x are free variables, into something that uses non-negative variables? The answer is: yes. Using a technique called variable splitting we can replace each x(j) by xplus(j)-xmin(j) where xplus(j),xmin(j)>=0. So the system of equations becomes:

  sum(j, a(i,j)*(xplus(j)-xmin(j))) = b(i)   for all i
  xplus(j),xmin(j)>=0

We may need to make sure that only one of the pair (xplus(j),xmin(j)) can become nonzero. This may hold automatically as the basis matrix B will become singular if both are in the basis. But we also can set an objective that handles this:

  min sum(j, xplus(j)+xmin(j))

As long as the system of equations has a feasible solution, the objective will make sure that only one of (xplus(j),xmin(j)) is nonzero.

Upvotes: 2

Related Questions