JavaScript package for modelling (Integer) Linear Programs

This is a lightweight JS package for specifying LPs and ILPs using a convenient syntax. Models can be read from and exported to the .lp CPLEX LP format, and solved using

• highs-js (WebAssembly wrapper for the HiGHS solver, a high-performance LP/ILP solver),
• glpk.js (WebAssembly wrapper for the GLPK solver), and
• jsLPSolver (a pure JS solver, not as fast as the others, but small bundle size).

All solvers work both in the browser (demo page) and in Node.js.

In Node.js:

npm install lp-model
# optionally install the solvers
npm install highs
npm install glpk.js
npm install javascript-lp-solver

In the browser:

<script src="https://cdn.jsdelivr.net/npm/lp-model@latest/dist/lp-model.min.js"></script>

Setup in Node.js:

const LPModel = require('lp-model');
// optionally load the solvers
async function main() {
    const model = new LPModel.Model();
    // ...
    const highs = await require("highs")();
    model.solve(highs);
    // or
    const glpk = await require("glpk.js")();
    model.solve(glpk);
    // or
    const jsLPSolver = require("javascript-lp-solver");
    model.solve(jsLPSolver);
}
main();

Setup in the browser for high-js and jsLPSolver:

<script src="https://cdn.jsdelivr.net/npm/lp-model@latest/dist/lp-model.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/highs/build/highs.js"></script>
<script src="https://unpkg.com/javascript-lp-solver/prod/solver.js"></script>
<script>
    async function main() {
        const model = new LPModel.Model();
        // ...
        const highs = await Module();
        model.solve(highs);
        // or
        const jsLPSolver = window.solver;
        model.solve(jsLPSolver);
    }
    main();
</script>

Setup in the browser for glpk.js (needs to be loaded from a module):

<script type="module">
    import { Model } from "https://cdn.jsdelivr.net/npm/lp-model@latest/dist/lp-model.es.min.js";
    import GLPK from "https://cdn.jsdelivr.net/npm/glpk.js";

    async function main() {
        const model = new Model();
        // ...
        const glpk = await GLPK();
        model.solve(glpk);
    }
    main();
</script>

const x = model.addVar({ vtype: "BINARY" }); // equivalent to model.addVar({ lb: 0, ub: 1, vtype: "INTEGER" })
const y = model.addVar({ lb: 0, name: "y" }); // default vtype is "CONTINUOUS"

model.setObjective([[4, x], [5, y]], "MAXIMIZE"); // 4x + 5y
model.addConstr([x, [2, y], 3], "<=", 8); // x + 2y + 3 <= 8
model.addConstr([[3, x], [4, y]], ">=", [12, [-1, x]]); // 3x + 4y >= 12 - x
console.log(model.toLPFormat());

await model.solve(highs);
console.log(`Solver finished with status: ${model.status}`);
console.log(`Objective value: ${model.ObjVal}`);
console.log(`x = ${x.value}\n y = ${y.value}`);

Check out the demo page to see your browser solve this program.

The general syntax for model.addConstr can be broken down as follows:

model.addConstr(expression, operator, rhs);

where:

• expression: This is the left-hand side (LHS) of the constraint, which is typically a linear combination of decision variables and their coefficients. The expression is specified as an array of terms, where each term is either

  • a two-element array [coefficient, variable]. For example, [2, y] represents $2y$.
  • a variable var. This is equivalent to [1, var].
  • a single number (for example 3), which is a constant term.

  Examples: [0] is a constant expression; [[1, x], [2, y]] represents $x + 2y$ and can also be written as [x, [2, y]]; [x, [2, x], x] represents $x + 2x + x$ which equals $4x$ and is thus equivalent to [4, x].

• operator: This is a string that specifies the relational operator for the constraint which can be "<=" for less than or equal to, ">=" for greater than or equal to, and "=" for equality ("==" is also accepted). This defines the relationship between the LHS expression and the RHS value.

• rhs : This stands for the right-hand side of the constraint, which is a constant value (for example 8) or an expression in the same format as the LHS expression.

For setting the objective function, use model.setObjective(expression, sense), where the same syntax for an expression is used, and the sense of optimization is specified as a string "MAXIMIZE" or "MINIMIZE".

Here is how to model the knapsack problem (select a bundle of items of highest total value subject to a capacity constraint) using binary variables.

const problem = {
    capacity: 15,
    items: [
        { name: "A", weight: 3, value: 4 },
        { name: "B", weight: 4, value: 5 },
        { name: "C", weight: 5, value: 8 },
        { name: "D", weight: 8, value: 10 }
    ]
};

const itemNames = problem.items.map(item => item.name);

// make binary variables for each item
const included = model.addVars(itemNames, { vtype: "BINARY" });
// included[A], included[B], included[C], included[D] are binary variables

// sum of weights of included items <= capacity
model.addConstr(
    problem.items.map(
        (item, i) => [item.weight, included[item.name]]
    ), "<=", problem.capacity);
// equivalent to: 3*included[A] + 4*included[B] + 5*included[C] + 8*included[D] <= 15

// maximize sum of values of included items
model.setObjective(
    problem.items.map((item, i) => [item.value, included[item.name]]), 
    "MAXIMIZE"
    );

await model.solve(highs);
console.log(`Objective value: ${model.ObjVal}`); // 17
console.log(`Included items: ${itemNames.filter(name => included[name].value > 0.5)}`); // A,B,D

The HiGHS solver supports (convex) quadratic objective functions (as does the LP format output function). Quadratic terms are specified as length-3 arrays, with coefficient followed by the two variables that are being multiplied (which may be the same variable in case of a squared term). Here is an example of how to model a quadratic objective function.

const x = model.addVar({ name: "x" });
model.addConstr([x], ">=", 10);
model.setObjective([[3, x, x]], "MINIMIZE"); // minimize 3 x^2
await model.solve(highs);
console.log(`Objective value: ${model.ObjVal}, with x = ${x.value}`); // 300, with x = 10

const lpFile = `Maximize
obj: 1 x1 + 2 x2 + 3 x3 + 1 x4
Subject To
 c1: -1 x1 + 1 x2 + 1 x3 + 10 x4 <= 20
 c2: 1 x1 - 3 x2 + 1 x3 <= 30
 c3: 1 x2 - 3.5 x4 = 0
Bounds
 0 <= x1 <= 40
 2 <= x4 <= 3
General
 x4
End`;
model.readLPFormat(lpFile);
await model.solve(highs);

Represents an LP or ILP model.

The solution of the optimization problem, provided directly by the solver, see the solver's documentation for details.

The status of the optimization problem, e.g., "Optimal", "Infeasible", "Unbounded", etc.

The value of the objective function in the optimal solution.

Adds a variable to the model.

Returns: Var - The created variable instance.

Adds multiple variables to the model based on an array of names. Each variable is created with the same provided options.

Returns: Object - An object where keys are variable names and values are the created variable instances.

Sets the objective function of the model.

Adds a constraint to the model.

Returns: Constr - The created constraint instance.

Converts the model to CPLEX LP format string.

Returns: string - The model represented in LP format.
See: https://web.mit.edu/lpsolve/doc/CPLEX-format.htm

Clears the model, then adds variables and constraints taken from a string formatted in the CPLEX LP file format.

See: https://web.mit.edu/lpsolve/doc/CPLEX-format.htm

Solves the model using the provided solver. highs-js, glpk.js, or jsLPSolver can be used. The solution can be accessed from the variables' value properties and the constraints' primal and dual properties.