node-fourier-motzkin
Fourier-Motzkin Elimination can be used to determine whether an arbitrary system of linear inequalities has solutions or not.
Install
npm install fourier-motzkin
Usage
Let's say you have a linear system of inequalities:
First, you have to transform it, so now you have a single matrix:
Now simply run the elimination algorithm:
var fme = ;var mx = 1 1 1 1 -2 1 -1 -1 -1 -4 1 -2 -1 0 0 0 0 -1 0 0 0 0 -1 0; console;
Note
The algorithm has exponential complexity, but it works very well on smaller systems.
TODO
- Improve performance (remove those slow
map
/reduce
calls, switch to fasterArray
implementation) - If the system is not solvable, provide proof (Farkas' lemma)
- If the system has one solution, find it
- etc
License
MIT