Last active
June 11, 2018 15:46
-
-
Save alexbepple/0bfeda764985cca8f9b94d48544d170d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
LP solvers in JS | |
jsLPSolver, https://github.com/JWally/jsLPSolver, https://www.npmjs.com/package/javascript-lp-solver | |
++ no trouble whatsoever with 10000 constraints, however I got tired of waiting for 20000 (multiple minutes) | |
there is quite a lot on optimizing the problem formulation at http://lpsolve.sourceforge.net/5.5/lp-format.htm | |
SOS (special ordered sets) look interesting: http://lpsolve.sourceforge.net/5.5/SOS.htm | |
https://www.npmjs.com/package/simple-simplex | |
! violated constraints in some instances | |
-- cumbersome that all variables have to be named everywhere | |
https://www.npmjs.com/package/simplex-solver | |
++ very nice first impression | |
- the version no. is scary (0.0.3) | |
! only allows for up to around 450 constraints; the runtime at 500 already seems prohibitively expensive (ca. 30 sec) | |
# Solve linear (in)equation systems | |
http://www.wolframalpha.com/input/?i=a%2Bb%3D1,+c%2Bd%3D2,+e%2Bf%3D3,+a%2Bf%3D3,+b%2Bc%3D2,+d%2Be%3D1 | |
## Solve linear equation systems: JS libs | |
https://livingthing.danmackinlay.name/javascript_mathematics.html | |
performance comparison | |
http://mlweb.loria.fr/benchmark/ | |
### Candidate libs | |
math.js, http://mathjs.org | |
? can this solve eq systems? | |
Sushi, http://mil-tokyo.github.io/sushi/ | |
not obvious how to use it | |
### Dismissed libs | |
Numeric.js, http://numericjs.com | |
-- lack of precision | |
> numeric.solve([[1,2],[3,4]],[17,39]) | |
[ 5.000000000000001, 5.999999999999999 ] | |
!!! does not seem to work with A, where n != m | |
> numeric.solve([[1,1]], [1]) | |
[ 1 ] | |
!!! does not seem to work with underdetermined systems: | |
> numeric.solve([[1,1], [1,1]], [1,1]) | |
[ NaN, NaN ] | |
nerdamer, http://nerdamer.com | |
! cannot solve underdetermined system | |
> n.solveEquations(['xa+xb=1', 'yb+yc=2', 'zc+za=3', 'xa+za=3', 'xb+yb=2', 'yc+zc=1']) | |
Error: Division by zero not allowed! | |
> n.solveEquations(['xa+xb=1', 'ya+yb=1', 'xa+ya=1', 'xb+yb=1']) | |
Error: Division by zero not allowed! | |
> n.solveEquations(['x+y=1']) | |
[ [ 'x', 1 ] ] | |
vectorious, https://mateogianolio.com/vectorious/ | |
!!! cannot solve overdetermined. | |
> new Matrix([[1,1], [1,0], [0,1]]).solve(new Matrix([[2], [1], [1]])).toArray() | |
[ [ NaN ], [ NaN ], [ NaN ] ] | |
algebra.js, http://algebra.js.org/#equations-linear | |
! seems more like symbolic computation | |
LALOLib, http://mlweb.loria.fr/lalolab/lalolib.html | |
- not on npm | |
- not requirable out-of-the-box | |
However, this is easily fixable by adding `module.exports = lalolib` at end of 'lalolib-module.min.js' | |
-- cannot always solve what it calculated (however, this is an unlikely edge case) | |
> a = l.array2mat([[1, 1]]) | |
> b = l.array2mat([[1], [0]]) | |
> l.mul(a, b) | |
1 | |
> l.solve(a, l.mul(a, b)) | |
NaN | |
!! cannot solve underdetermined system | |
> a = l.array2mat([[1,1], [1,1]]) | |
> b = l.array2mat([[0.5], [0.5]]) | |
> l.mul(a, b) | |
Float64Array [ 1, 1 ] | |
> l.solve(a, l.mul(a, b)) | |
TypeError: Cannot read property 'm' of undefined | |
at ... | |
> a = l.array2mat([[1,1,0,0,0,0], [0,0,1,1,0,0], [0,0,0,0,1,1], [1,0,0,0,0,1], [0,1,1,0,0,0], [0,0,0,1,1,0]]) | |
> b = l.array2mat([[1], [0], [2], [0], [1], [2]]) | |
> l.mul(a, b) | |
Float64Array [ 1, 2, 3, 3, 2, 1 ] | |
> l.solve(a, l.mul(a, b)) | |
TypeError: Cannot read property 'm' of undefined | |
-- precision issues | |
> a = l.array2mat([[1,1], [1,0], [0,1]]) | |
> b = l.array2mat([[1], [1]]) | |
> l.mul(a, b) | |
Float64Array [ 2, 1, 1 ] | |
> l.solve(a, l.mul(a, b)) | |
Float64Array [ 0.9999999999999999, 1 ] | |
++ can solve overdetermined system | |
> a = l.array2mat([[1,1,0], [0,0,1], [1,0,0], [0,1,1]]) | |
> b = l.array2mat([[1], [1], [1]]) | |
> l.mul(a, b) | |
Float64Array [ 2, 1, 1, 2 ] | |
> l.solve(a, l.mul(a, b)) | |
Float64Array [ 0.9999999999999999, 0.9999999999999998, 1.0000000000000002 ] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* eslint-disable */ | |
const m = require('moment') | |
const r = require('ramda') | |
const td = require('testdouble') | |
const __ = require('hamjest') | |
const n = require('numeral') | |
const Simplex = require('simple-simplex') | |
// const solver = new Simplex({ | |
// objective: { | |
// xa: 1, | |
// xb: 1, | |
// yb: 1, | |
// }, | |
// optimizationType: 'max', | |
// constraints: [ | |
// { | |
// namedVector: { xa: 2, xb: 0, yb: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xb: 2, xa: 0, yb: 0 }, | |
// constraint: '<=', | |
// constant: 2, | |
// }, | |
// { | |
// namedVector: { yb: 1, xa:0, xb:0 }, | |
// constraint: '<=', | |
// constant: 2, | |
// }, | |
// ], | |
// }) | |
// const solver = new Simplex({ | |
// objective: { | |
// xa: 1, | |
// xb: 1, | |
// yb: 1, | |
// yc: 1, | |
// zc: 1, | |
// za: 1, | |
// }, | |
// optimizationType: 'max', | |
// constraints: [ | |
// { | |
// namedVector: { xa: 1, xb: 0, yb: 0, yc: 0, zc: 0, za: 3 }, | |
// constraint: '<=', | |
// constant: 3, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 1, yb: 2, yc: 0, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 2, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 0, yb: 0, yc: 2, zc: 3, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { // this constraint is clearly violated | |
// namedVector: { xa: 1, xb: 0, yb: 0, yc: 0, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 1, yb: 0, yc: 0, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 0, yb: 1, yc: 0, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 0, yb: 0, yc: 1, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 0, yb: 0, yc: 0, zc: 1, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 0, yb: 0, yc: 0, zc: 0, za: 1 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// ], | |
// }) | |
// const solver = new Simplex({ | |
// objective: { | |
// xa: 1, | |
// xb: 1, | |
// yb: 1, | |
// yc: 1, | |
// zc: 1, | |
// za: 1, | |
// }, | |
// optimizationType: 'max', | |
// constraints: [ | |
// { | |
// namedVector: { xa: 1, xb: 0, yb: 0, yc: 0, zc: 0, za: 1 }, | |
// constraint: '<=', | |
// constant: 3, | |
// }, | |
// { | |
// namedVector: { xa: 0, xb: 1, yb: 1, yc: 0, zc: 0, za: 0 }, | |
// constraint: '<=', | |
// constant: 2, | |
// }, | |
// { // the solver clearly violates this constraint | |
// namedVector: { xa: 0, xb: 0, yb: 0, yc: 1, zc: 1, za: 0 }, | |
// constraint: '<=', | |
// constant: 1, | |
// }, | |
// ], | |
// }) | |
// const result = solver.solve({ | |
// methodName: 'simplex' | |
// }) | |
// console.log({ | |
// solution: result.solution, | |
// isOptimal: result.details.isOptimal | |
// }) | |
const simplex = require('simplex-solver') | |
// const result1 = simplex.maximize('xa + xb + yb', [ | |
// 'xa <= 1', | |
// 'xb + yb <= 2', | |
// 'xa + xb <= 2', | |
// 'yb <= 1' | |
// ]) | |
//console.log(result1) | |
// const result2 = simplex.maximize('xa + xb + yb + yc + zc + za', [ | |
// 'xa + za <= 3', | |
// 'xb + yb <= 2', | |
// 'yc + zc <= 1', | |
// 'xa + xb <= 1', | |
// 'yb + yc <= 2', | |
// 'za + zc <= 3', | |
// ]) | |
// console.log(result2) | |
// const variables = r.pipe( | |
// () => r.range(1, 500), | |
// r.map(i => 'x' + i) | |
// )() | |
// v2 = ['x1', 'x2', 'x3'] | |
// constraints = r.map(r.concat(r.__, '<=3'))(variables) | |
// console.log(constraints) | |
// const result3 = simplex.maximize(r.join(' + ')(variables), constraints) | |
// console.log(result3) | |
// const result3 = simplex.maximize('xa + xb + yb + yc + zc + za', [ | |
// 'xa + za <= 60', | |
// 'xb + yb <= 40', | |
// 'yc + zc <= 20', | |
// 'xa + xb <= 20', | |
// 'yb + yc <= 40', | |
// 'za + zc <= 60', | |
// 'xa >= 1', | |
// 'xb >= 1', | |
// 'yb >= 1', | |
// 'yc >= 1', | |
// 'zc >= 1', | |
// 'za >= 1', | |
// ]) | |
// console.log(result3) | |
const lp = require('javascript-lp-solver') | |
// console.log(lp.Solve({ | |
// "optimize": "sum", | |
// "opType": "max", | |
// "constraints": { | |
// "x": {"max": 2}, | |
// "y": {"max": 1}, | |
// "a": {"max": 1}, | |
// "b": {"max": 2}, | |
// }, | |
// "variables": { | |
// "xa": { | |
// "x": 1, | |
// "a": 1, | |
// "sum": 1, | |
// }, | |
// "xb": { | |
// "x": 1, | |
// "b": 1, | |
// "sum": 1, | |
// }, | |
// "yb": { | |
// "y": 1, | |
// "b": 1, | |
// "sum": 1, | |
// }, | |
// }, | |
// })) | |
// const model = [ | |
// 'max: xa xb yb', | |
// 'xa + xb <= 2', | |
// 'yb <= 1', | |
// 'xa <= 1', | |
// 'xb + yb <= 2' | |
// ] | |
// const model = [ | |
// 'max: xa xb yb yc zc za', | |
// 'xa + xb <= 1', | |
// 'yb + yc <= 2', | |
// 'zc + za <= 3', | |
// 'xa + za <= 3', | |
// 'xb + yb <= 2', | |
// 'yc + zc <= 1', | |
// ] | |
// const vars = r.pipe( | |
// () => r.range(1, 20000), | |
// r.map(i => 'x' + i) | |
// )() | |
// const constraints = r.map(r.concat(r.__, ' <= 3'))(vars) | |
// const model = [ | |
// 'max: ' + r.join(' ', vars), | |
// ...constraints, | |
// ...r.map(r.concat('int '))(vars) | |
// ] | |
// console.log(lp.Solve(lp.ReformatLP(model))) | |
const numeric = require('numericjs') | |
// const A = [[1,2],[3,4]] | |
// const b = [17,39] | |
// const A = [ | |
// [1, 1, 0, 0, 0, 0], | |
// [0, 0, 1, 1, 0, 0], | |
// [0, 0, 0, 0, 1, 1], | |
// [1, 0, 0, 0, 0, 1], | |
// [0, 1, 1, 0, 0, 0], | |
// [0, 0, 0, 1, 1, 0], | |
// ] | |
// const b = [1, 2, 3, 3, 2, 1] | |
const A =[ | |
[1, 1], | |
[1, 0], | |
[0, 1], | |
] | |
const b = [2, 1, 1] | |
console.log(numeric.solve(A,b)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment