Learn about our RFC process, Open RFC meetings & more.Join in the discussion! »

linear-program-solver

1.2.0 • Public • Published

Linear Program Solver

npm version Build Status Coverage Status License: MIT

JS/TS wrapper for simplex linear programming solver by jeronimonunes

Requirements

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

Linear-program-solver is a JavaScript / TypeScript wrapper to simplex C++ engine by jeronimonunes. It's intended to be used together with linear-program-parser written in TypeScript. There are several linear program solvers found in npm. Linear-program-parser is relatively new, written in TypeScript and personally easy to use among them. Linear-program-solver can accept the output of linear-program-parser directly.

Code snippets

Sync version

import { parse } from 'linear-program-parser';
import { simplex, findSolution, simplexIsOK  } from 'linear-program-solver';
import { SimplexSolution } from 'linear-program-solver';
 
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 'linear-program-parser';
import { simplexAsync, findSolution, simplexIsOK  } from 'linear-program-solver';
import { SimplexSolution } from 'linear-program-solver';
 
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();
const val: SimplexSolution = await simplexAsync(fpi.toMatrix());
const a: number = findSolution('a', val.solution, val.vars);
...

Async version(2)

import { solveAsync, SimplexSolution } from 'linear-program-solver';
 
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): SimplexSolution
async function simplexAsync(arg: SimplexTableau): Promise

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,
  • okey, 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 (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

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().

type SimplexSolution

Type of return object of simplex().

extern type SimplexSolution {
  result: ( 'otima' | 'ilimitada' | 'inviavel' );
  solution: number[];
  vars: string[];
}

Install

> npm i linear-program-solver

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.

> export CXX=/your/new/c++/Compiler

Solution seems wrong.

Three possible reasons.

  1. When the build conditions do not meet, it returns 'inviavel' regardless the given problem.
  2. The given problem is grammatically wrong.
  3. Bugs of the solver or wrapper.

During installation of this module, it compiles C++ code on your computer. Compiling this module requires N-API (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, node-gyp you are running is old. Some Linux has a pretty old node-gyp that came with apt install. You can install the latest node-gyp by

> npm i -g node-gyp

To check the grammar of the problem, you may try Simplex-web.

Failed to install to Windows

Sorry, install scripts are written for Unix and I don' have a Windows PC. But the main code would and should work on Windows. If you can volunteer a script for Windows, very welcome.

If you already have a C++ compiler, python, node-gyp 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/linear-program-solver.git
> cd linear-program-solver
> git clone https://github.com/jeronimonunes/simplex.git
> cd simplex
> git clone https://github.com/jeronimonunes/bigint.git
> cd .. (note: you go back to linear-program-solver.)
> node-gyp rebuild
> npm run build
> cd c:\users\your\root
> npm i c:\users\your\prefered\folder\linear-program-solver

Known issues

The tableau data generated by linear-program-parser 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

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.

Install

npm i linear-program-solver

DownloadsWeekly Downloads

13

Version

1.2.0

License

MIT

Unpacked Size

53 kB

Total Files

17

Last publish

Collaborators

  • avatar