Linear Program Solver
JS/TS wrapper for simplex linear programming solver by jeronimonunes
Requirements
 Linux or macOS (may work on Windows also by manual installation, see Trouble shooting)
 C++ compiler with C++17 or newer support.
 Node 10.20.0 or newer except 11. (To be exact, NAPI version 6 or newer)
 linearprogramparser 1.0.11 or newer (npm module).
 jeronimonunes/simplex (C++ code).
 jeronimonunes/bigint (C++ code).
This module will be built even these conditions do not meet. When so, simplex() always returns 'inviavel' (infeasible) without actually solving the problem. To check if simplex() works, use simplexIsOK().
Description
Linearprogramsolver is a JavaScript / TypeScript wrapper to simplex C++ engine by jeronimonunes. It's intended to be used together with linearprogramparser written in TypeScript. There are several linear program solvers found in npm. Linearprogramparser is relatively new, written in TypeScript and personally easy to use among them. Linearprogramsolver can accept the output of linearprogramparser directly.
Code snippets
Sync version example, as in linearprogramparser
import { parse } from 'linearprogramparser';
import { simplex, findSolution, simplexIsOK } from 'linearprogramsolver';
import { SimplexSolution } from 'linearprogramsolver';
const linearProgram = parse(`max(3a 4b +5c 5d)
st:
+1a +1b +0c +0d <= +5;
1a +0b 5c +5d <= 10;
+2a +1b +1c 1d <= +10;
2a 1b 1c +1d <= 10;
a >= 0;
b >= 0;
c >= 0;
d >= 0;
`);
if (simplexIsOK()) {
const fpi = linearProgram.toFPI();
const val: SimplexSolution = simplex(fpi.toMatrix());
const a: number = findSolution('a', val.solution, val.vars);
...
}
Async version(1)
import { parse } from 'linearprogramparser';
import { simplexAsync, findSolution, simplexIsOK } from 'linearprogramsolver';
import { SimplexSolution } from 'linearprogramsolver';
const linearProgram = parse(`max(3/10*a 4/10*b +5/10*c 5/10*d)
st:
+1a +1b <= +5;
1a +0b 5c +5d <= 10;
a >= 0;
b >= 0;
c >= 0;
d >= 0;
`);
const fpi = linearProgram.toFPI();
try {
const val: SimplexSolution = await simplexAsync(fpi.toMatrix());
const a: number = findSolution('a', val.solution, val.vars);
...
Async version(2) allinone
import { solveAsync, SimplexSolution } from 'linearprogramsolver';
const problem = `max(3/10*a 4/10*b +5/10*c 5/10*d)
st:
+1a +1b <= +5;
1a +0b 5c +5d <= 10;
+2a +1b +1c 1d <= +10;
2a 1b 1c +1d <= 10;
a >= 0;
b >= 0;
c >= 3;
`;
try {
const val: SimplexSolution = await solveAsync(problem);
} catch (e) {
console.log(e);
}
...
Functions
function simplex(arg: SimplexTableau<Fraction>): SimplexSolution
async function simplexAsync(arg: SimplexTableau<Fraction>): Promise<SimplexSolution>
Solves standard form matrix and vectors provided by Fpi. Input arguments are those of the output of Fpi.toMatrix().
Result is either of 'otima', 'ilimitada', 'inviavel' (in Portuguese), which mean
 great, a feasible solution found in limited iterations,
 okay, a solution found but iteration didn't converge,
 sorry, it's infeasible to solve.
When build condition did not meet, it always returns 'inviavel' without solving simplex.
Solution and vars are in pair. Vars is an array of given variables to solve with slack variables automatically introduced by the parser (f_1 ... ). If a given variable is not constrained nonnegative, it is replaced by two nonnegative variables. If your variable is x, it will be xp and xn.
function findSolution(variableName: string, solution: number[], vars: string[]): number
Obtain a solution that corresponds to variableName. Solution and vars are those given by simplex().
If variable is replaced to positive and negative parts (slack variables), e.g., xp and xn such that x = xp  xn,
findSolution()
will find both parts and returns the final solution (in above example, x).
If variableName is not in vars, it returns NaN.
function simplexIsOK(): boolean
Returns true when build condition meets. Else, return false;
async function solveAsync(problem: string): Promise<SimplexSolution>
A service function that does everything from parsing the problem to solve.
Types
type SimplexTableau<T>
Generic type for argument of simplex(). Currently T
is Fraction
for simplex()
and simplexAsync()
.
type SimplexSolution
(To be obsolete)
Type of return object of simplex().
extern type SimplexSolution {
result: ( 'otima'  'ilimitada'  'inviavel' );
solution: number[];
vars: string[];
}
Note: This type will be obsolete, by replacing function by async ones.
Tips to make LP program string
Linearprogramparser accepts the problem by a string. Here are some tips to make the problem string.

Fractional numbers (e.g., 123/100) are acceptable. You can convert floating numbers (e.g., 1.23) to fractional numbers using
Fraction.toFraction()
in fraction.js. 
When you do so, don't forget '
*
' between number and variable: e.g., '123/100*a'. 
You can use both 'max' or 'min' for the objective function.

Only one objective function is accepted. As a compromise, you can connect multiple objective functions by introducing weight factors applied to functions.

Variable constraint can be any. You can let linearprogramparser replace a nonzero constraint (>= 3, etc) by slack variables.

Variable names can be any string
 Starting by alphabet (not number, signs),
 Case sensitive,
 Not containing '_f__'.
However it should be avoided to use such names that
findSolution()
can confuse, e.g., ending with 'n' or 'p'.
Install
> npm i linearprogramsolver
Trouble shooting
Warning 'Compiler supporting C++17 or newer required'
You may see this message during installation, if your default C++ compiler is so. You can specify other compiler by setting CXX environment parameter before installation.
> export CXX=/your/newer/c++/Compiler
> npm i linearprogramsolver
Solution seems wrong.
Three possible reasons.
 When the build conditions do not meet, it returns 'inviavel' regardless the given problem.
 The given problem is grammatically wrong.
 Bugs of the solver or wrapper.
During installation of this module, it compiles C++ code. Compiling this module requires NAPI (node API) version 6 or greater, that comes with BigInt support. Node 10.20.0 has it. Node 11.15.0 seems not. See the version matrix.
In some cases, nodegyp you are running is old. Some Linux has a pretty old nodegyp that came with apt install. You can install the latest nodegyp by
> npm i g nodegyp
To check the grammar of the problem, you may try Simplexweb.
Failed to install to Windows
Sorry, install scripts are written for Unix and I don't have a Windows PC to test. But the main code would and should work on Windows. If you can volunteer an istallation script for Windows, very welcome.
If you already have a C++ compiler, python, nodegyp and installed every necessary module, you can manually build it from command console like this way (sorry not tested),
> cd c:\users\your\prefered\folder
> git clone https://github.com/kchinzei/linearprogramsolver.git
> cd linearprogramsolver
> git clone https://github.com/jeronimonunes/simplex.git
> cd simplex
> git clone https://github.com/jeronimonunes/bigint.git
> cd .. (note: you go back to linearprogramsolver.)
> nodegyp rebuild
> npm run build
> cd c:\users\your\root
> npm i c:\users\your\prefered\folder\linearprogramsolver
Known issues
The tableau data generated by linearprogramparser is represented by Fraction
(but not that of fraction.js).
To translate javascript Fraction
to C++ class, it uses BigInt
to long
coercion, that can be a lossy conversion.
Credits
 linearprogramparser and simplex by jeronimonunes.
 bigint originally by Matt McCutchen with modification by jeronimonunes.
License
The MIT License (MIT) Copyright (c) K. Chinzei (kchinzei@gmail.com) Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
simplex and modified bigint by jeronimonunes
https://github.com/jeronimonunes/simplex
MIT License
Copyright (c) 2020 Jerônimo Nunes Rocha
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
bigint originally by Matt McCutchen
https://mattmccutchen.net/bigint/
I, Matt McCutchen, the sole author of the original Big Integer Library, waive my copyright to it, placing it in the public domain. The library comes with absolutely no warranty.