YALPS

What is This (For)?

This is Yet Another Linear Programming Solver (YALPS). It is intended as a performant, lightweight linear programming (LP) solver geared towards small LP problems. It can solve non-integer, integer, and mixed integer LP problems. While webassembly ports of existing solvers perform well, they tend to have larger bundle sizes and may be overkill for your use case. YALPS is the alternative for the browser featuring a small bundle size.

YALPS is a rewrite of jsLPSolver. The people there have made a great and easy to use solver. However, the API was limited to objects only, and I saw other areas that could have been improved. You can check out jsLPSolver for more background and information regarding LP problems.

Compared to jsLPSolver, YALPS has the following differences:

• More flexible API (e.g., support for Iterables alongside objects)
• Better performance (especially for non-integer problems, see Performance for more details.)
• Good Typescript support (YALPS is written in Typescript)

On the other hand, these features from jsLPSolver were dropped:

• Unrestricted variables (might be added later)
• Multiobjective optimization
• External solvers

Usage

Installation

npm i yalps

Import

The main solve function:

import { solve } from "yalps"

Optional helper functions:

import { lessEq, equalTo, greaterEq, inRange } from "yalps"

Types, as necessary:

import { Model, Constraint, Coefficients, OptimizationDirection, Options, Solution } from "yalps"

Examples

Using objects:

const model = {
  direction: "maximize" as const,
  objective: "profit",
  constraints: {
    wood: { max: 300 },
    labor: { max: 110 }, // labor should be <= 110
    storage: lessEq(400), // you can use the helper functions instead
  },
  variables: {
    table: { wood: 30, labor: 5, profit: 1200, storage: 30 },
    dresser: { wood: 20, labor: 10, profit: 1600, storage: 50 },
  },
  integers: ["table", "dresser"], // these variables must have an integer value in the solution
}

const solution = solve(model)
// { status: "optimal", result: 14400, variables: [ ["table", 8], ["dresser", 3] ] }

Iterables and objects can be mixed and matched for the constraints and variables fields. Additionally, each variable's coefficients can be an object or an iterable. E.g.:

const constraints = new Map<string, Constraint>()
  .set("wood", { max: 300 })
  .set("labor", lessEq(110))
  .set("storage", lessEq(400))

const dresser = new Map<string, number>()
  .set("wood", 20)
  .set("labor", 10)
  .set("profit", 1600)
  .set("storage", 50)

const model: Model = {
  direction: "maximize",
  objective: "profit",
  constraints: constraints, // is an iterable
  variables: { // kept as an object
    table: { wood: 30, labor: 5, profit: 1200, storage: 30 }, // an object
    dresser: dresser, // an iterable
  },
  integers: true, // all variables are indicated as integer
}

const solution: Solution = solve(model)
// { status: "optimal", result: 14400, variables: [ ["table", 8], ["dresser", 3] ] }

For more extensive documentation, use the JSDoc annotations / hover information in your editor. In particular, you probably want to take a look at the documentation comments for the Options, Solution, and Model types.

In the browser

In case you need it, a minified version of the code is available under dist/index.min.js. When loading this file as a script, YALPS will be available as a global variable named YALPS:

<script src="https://unpkg.com/[email protected]/dist/index.min.js"></script>
<!-- For unpkg, `dist/index.min.js` is the default, so you can choose to omit it. -->
<!-- <script src="https://unpkg.com/[email protected]"></script> -->
<script>
  const { solve } = YALPS
  /* your code */
</script>

Like unpkg above, a similar shorthand is also supported for jsdelivr:

<script src="https://cdn.jsdelivr.net/npm/[email protected]"></script>
<!-- Same as the below -->
<!-- <script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/index.min.js"></script> -->
<script>
  const { solve } = YALPS
  /* your code */
</script>

Performance

While YALPS generally performs better than javascript-lp-solver, this solver is still geared towards small problems (hundreds of variables or constraints). For example, the solver keeps the full representation of the matrix in memory as a dense array. As a general rule, the number of variables and constraints should probably be a few thousand or less, and the number of integer variables should be a few hundred at the most. If your use case has large problems, it is recommended that you first benchmark and test the solver on your own before committing to using it. For very large and/or integral problems, a more professional solver is recommended, e.g. glpk.js.

Nevertheless, below are the results from some benchmarks comparing YALPS to other solvers. Each solver was run 30 times for each benchmark problem. A full garbage collection was manually triggered before starting each solver's 30 trials. The averages and standard deviations are measured in milliseconds. Slowdown is calculated as mean / fastest mean. The benchmarks were run on ts-node v10.9.1 and node v19.8.1. Your mileage may vary in a browser setting.

The code used for these benchmarks is available under benchmarks/. Measuring performance isn't always straightforward, so take these synthetic benchmarks with a grain of salt. It is always recommended to benchmark for your use case. Then again, if your problems are typically of small size, then this solver should have no issue (and may be faster)!

Maintenance/Status

This package is still being maintained (i.e., bug fixes and security updates as necessary). However, no new features are planned or being worked on at this time.