javascript-lp-solver

When working with or extending the solver's numerical logic, be aware that certain optimizations can cause numerical drift and break Mixed Integer Programming (MIP) branching.

Do not attempt the following optimizations:

• Using multiplication instead of division for pivot row normalization: You must use division (matrix[row] / quotient) to maintain precision. Using multiplication by an inverse (matrix[row] * invQuotient) introduces small errors that affect branching decisions.
• Removing zero checks in pivot loops: Even if a column is expected to be non-zero, keeping explicit zero checks (e.g., if (row[pivotColumnIndex] !== 0)) prevents the accumulation of floating-point errors that compound during MIP branching.

To restrict variables to integer or binary values, add the ints or binaries property to your model object. This enables Mixed-Integer Programming (MIP) via branch-and-cut.

const model = {
    optimize: "profit",
    opType: "max",
    constraints: {
        wood: { max: 300 },
        labor: { max: 110 },
    },
    variables: {
        table: { wood: 30, labor: 5, profit: 1200 },
        dresser: { wood: 20, labor: 10, profit: 1600 },
    },
    ints: { table: 1, dresser: 1 },
};

console.log(solver.Solve(model));
// { feasible: true, result: 14400, table: 8, dresser: 3 }

By default, all variables are non-negative (≥ 0).

To allow a variable to take negative values, add it to the unrestricted object in your model. To set specific upper bounds on variables, define them as constraints.

// Allowing negative values
const model = {
    optimize: "profit",
    opType: "max",
    constraints: {
        balance: { equal: 0 },
    },
    variables: {
        income: { profit: 1, balance: 1 },
        expense: { profit: -1, balance: -1 },
    },
    unrestricted: { income: 1, expense: 1 }, // Allow negative values
};

// Setting upper bounds via constraints
const modelWithBounds = {
    optimize: "output",
    opType: "max",
    constraints: {
        x_upper: { max: 100 }, // x <= 100
        y_upper: { max: 50 }, // y <= 50
    },
    variables: {
        x: { output: 10, x_upper: 1 },
        y: { output: 15, y_upper: 1 },
    },
};

You can restrict the domain of your decision variables using the following properties in the model object:

• Integer Variables (ints): Restricts variables to integer values. Use 1 or true to enable.
• Binary Variables (binaries): Restricts variables to exactly 0 or 1. Use 1 or true to enable.
• Unrestricted Variables (unrestricted): Allows variables to be negative (the default is non-negative). Use 1 or true to enable.

const model = {
    variables: { x: { profit: 10 }, y: { profit: 20 }, use_a: { profit: 5 }, delta: { profit: 1 } },
    ints: { x: 1, y: 1 },
    binaries: { use_a: 1 },
    unrestricted: { delta: 1 }
};

By default, the Mixed Integer Programming (MIP) service uses 'most-fractional' variable selection for branching. While this is the most compatible and often fastest method for standard problems, you can opt into an enhanced service that uses pseudo-cost branching.

To use pseudo-cost branching, set the branching option to "pseudocost" in your solver configuration. Note that for many common problem types (like 'Monster II' or 'Vendor Selection'), the default 'most-fractional' strategy may actually be faster due to lower computational overhead.

{
  "branching": "pseudocost"
}

When implementing or modifying the Mixed Integer Rounding (MIR) loop, you can achieve marginal performance improvements by reusing the 'after' volume value from the previous iteration as the 'before' value for the next. This avoids redundant calls to computeFractionalVolume(true).

Example Pattern:

// Before: compute twice per iteration
while (fractionalVolumeImproved) {
    const before = tableau.computeFractionalVolume(true);
    tableau.applyMIRCuts();
    const after = tableau.computeFractionalVolume(true);
    if (after >= 0.9 * before) break;
}

// After: reuse previous after
let volume = tableau.computeFractionalVolume(true);
while (volume > 0) {
    tableau.applyMIRCuts();
    const after = tableau.computeFractionalVolume(true);
    if (after >= 0.9 * volume) break;
    volume = after;
}

You can install the solver via npm for Node.js environments, use a CDN for browsers, or import it as an ES Module.

npm install javascript-lp-solver

For potentially better performance, you can delegate solving to an external tool like lp_solve.

Note: External solvers require Node.js and are not available in browsers.

To use an external solver, include an external object in your model:

• solver: Must be "lpsolve".
• binPath: Path to the executable.
• tempName: Path for the temporary LP model file.
• args: Array of command-line arguments.

const model = {
    optimize: "profit",
    opType: "max",
    constraints: { ... },
    variables: { ... },
    external: {
        solver: "lpsolve",
        binPath: "/usr/bin/lp_solve",
        tempName: "/tmp/model.lp",
        args: ["-s2", "-timeout", "240"]
    }
};

To prevent large optimization problems from blocking the main UI thread, run the solver inside a Web Worker.

// worker.js
importScripts("https://unpkg.com/javascript-lp-solver/dist/solver.global.js");

onmessage = function (e) {
    postMessage(solver.Solve(e.data));
};

// main.js
const worker = new Worker("worker.js");
worker.onmessage = (e) => console.log(e.data);
worker.postMessage(model);