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 = require('fourier-motzkin');
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.log(fme(mx));

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 faster Array implementation)
• If the system is not solvable, provide proof (Farkas' lemma)
• If the system has one solution, find it
• etc

License

MIT