lp-model


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.

Installation

In Node.js:

``bash
npm install lp-model


optionally install the solvers


npm install highs
npm install glpk.js
npm install javascript-lp-solver
`

In the browser:

`html

`

Usage

$3

Setup in Node.js:

`javascript
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:

`html




`

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

`

$3

`javascript
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.

$3

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

`javascript
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".

$3

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.

`javascript
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: 3included[A] + 4included[B] + 5included[C] + 8included[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
`

$3

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.

`javascript
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
`

$3


`javascript
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);
`

API

$3

Represents an LP or ILP model.

$3

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

$3

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

$3

The value of the objective function in the optimal solution.

$3

Adds a variable to the model.

Returns: Var - The created variable instance.

| Param | Type | Default | Description |
| --- | --- | --- | --- |
| options | Object | | Options for creating the variable. |
| [options.lb] | number \| "-infinity" | 0 | The lower bound of the variable. |
| [options.ub] | number \| "+infinity" | "+infinity" | The upper bound of the variable. |
| [options.vtype] | "CONTINUOUS" \| "BINARY" \| "INTEGER" | "CONTINUOUS" | The type of the variable. |
| [options.name] | string | | The name of the variable. If not provided, a unique name is generated. |

$3

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.

| Param | Type | Default | Description |
| --- | --- | --- | --- |
| varNames | Array.<string> | | Array of names for the variables to be added. |
| options | Object | | Common options for creating the variables. |
| [options.lb] | number \| "-infinity" | 0 | The lower bound for all variables. |
| [options.ub] | number \| "+infinity" | "+infinity" | The upper bound for all variables. |
| [options.vtype] | "CONTINUOUS" \| "BINARY" \| "INTEGER" | "CONTINUOUS" | The type for all variables. |

$3

Sets the objective function of the model.

| Param | Type | Description |
| --- | --- | --- |
| expression | Array | The linear expression representing the objective function. |
| sense | "MAXIMIZE" \| "MINIMIZE" | The sense of optimization, either "MAXIMIZE" or "MINIMIZE". |

$3

Adds a constraint to the model.

Returns: Constr - The created constraint instance.

| Param | Type | Description |
| --- | --- | --- |
| lhs | Array | The left-hand side expression of the constraint. |
| comparison | string | The comparison operator, either "<=", "=", or ">=". |
| rhs | number \| Array | The right-hand side, which can be a number or a linear expression. |

$3

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

$3

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

| Param | Type | Description |
| --- | --- | --- |
| lpString | string | The LP file as a string. |

$3

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.

| Param | Type | Default | Description |
| --- | --- | --- | --- |
| solver | Object | | The solver instance to use for solving the model, either from highs-js, glpk.js, or jsLPSolver. |
| [options] | Object | {} | Options to pass to the solver's solve method (refer to their respective documentation: https://ergo-code.github.io/HiGHS/dev/options/definitions/, https://www.npmjs.com/package/glpk.js, https://github.com/JWally/jsLPSolver?tab=readme-ov-file#options). |