Skip to content

Latest commit

 

History

History
49 lines (32 loc) · 1.23 KB

README.md

File metadata and controls

49 lines (32 loc) · 1.23 KB
Raw

node-fourier-motzkin Build Status

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:

Original system

First, you have to transform it, so now you have a single matrix:

Matrix form

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