Node.js如何实现混合整数规划？求解器选型与实战详解

混合整数规划（Mixed Integer Programming，简称MIP）是运筹学中非常实用的一类优化问题，它要求部分或全部决策变量必须取整数值，同时在一组线性约束下求目标函数的最大或最小值。比如工厂排产时设备数量必须是整数，快递装箱时包裹个数不能是小数，这些都属于典型的混合整数规划场景。本文将以Node.js为技术栈，介绍如何在JavaScript环境中建模并求解这类问题。

混合整数规划的基本原理与Node.js求解思路

标准的线性规划允许决策变量取任意实数，而混合整数规划在其基础上增加了整数约束。从数学形式上看，它由目标函数、线性约束和变量类型声明三部分组成。求解MIP的主流算法是分支定界法（Branch and Bound），其核心思想是先放松整数约束求解线性规划，如果得到的小数解不满足整数要求，就将问题分支成两个子问题继续求解，直到找到整数最优解或证明问题无解。

对Node.js而言，实现MIP有三条主要路径：一是使用纯JavaScript编写的求解库，优点是零依赖、跨平台部署方便；二是通过Node.js的FFI或N-API绑定调用成熟的本地求解器，例如GLPK、CBC或商业求解器Gurobi，性能更强但部署复杂；三是把Node.js作为服务层，通过子进程或HTTP接口调用Python、C++等语言编写的求解程序。三种方案各有取舍，下面会逐一展开。

需要特别提醒的是，纯JavaScript实现在大规模问题上性能明显吃亏。分支定界法在最坏情况下复杂度是指数级的，如果模型涉及上万个变量和约束，纯JS方案可能跑几个小时都出不了结果，而GLPK这类C实现的求解器往往几十秒就能完成。因此选型时要先评估问题规模。

javascript-lp-solver：轻量级的纯JS方案

javascript-lp-solver是目前npm生态中最容易上手的求解库，它支持线性规划和混合整数规划，API设计非常直观，直接用JavaScript对象描述模型即可，不需要学习额外的建模语言。安装方式如下：

npm install javascript-lp-solver

下面通过一个生产计划问题演示用法。假设某工厂生产A、B两种产品，A每件利润30元需要2小时机器时间和1小时人工，B每件利润45元需要3小时机器时间和2小时人工，机器总工时100小时，人工总工时80小时，且产品必须按整数件生产，求最大利润。

const solver = require("javascript-lp-solver");

const model = {
  optimize: "profit",
  opType: "max",
  constraints: {
    machineHours: { max: 100 },
    laborHours: { max: 80 }
  },
  variables: {
    productA: {
      profit: 30,
      machineHours: 2,
      laborHours: 1,
      int: true   // 声明为整数变量
    },
    productB: {
      profit: 45,
      machineHours: 3,
      laborHours: 2,
      int: true
    }
  }
};

const result = solver.solve(model);
console.log(result);

求解结果中result.variables会给出每种产品的最优产量，result.result是最大利润值。整个建模过程就像在填写一张表格，变量对象里的键名对应约束名和目标函数系数，int: true这一行就是整数约束的声明方式，非常契合JavaScript开发者的思维习惯。

这个库的局限也很明显：它基于单纯形法加分支定界的JS实现，变量规模建议控制在几百个以内；不支持更高级的特性如半连续变量、SOS约束；而且项目维护活跃度一般，遇到bug可能需要自己读源码解决。对于教学演示、小型排班、简单选品这类场景它完全够用，一旦模型膨胀就要考虑换方案了。

绑定GLPK：性能与功能的平衡之选

GLPK是GNU旗下的开源线性规划求解器，支持MIP，性能远超纯JS实现。社区提供了如glpk.js（编译到WebAssembly的版本）以及通过node-ffi调用本地GLPK动态库的方案。GLPK接受标准的MPS或CPLEX LP格式模型文件，因此典型做法是在Node.js中拼接模型文本，然后交给GLPK求解。

一个LP格式模型文件的样例如下，对应上面的生产计划问题：

Maximize
  obj: 30 xA + 45 xB
Subject To
  machine: 2 xA + 3 xB <= 100
  labor: 1 xA + 2 xB <= 80
Bounds
Generals
  xA xB
End

其中Generals段声明的变量会被视为整数，这就是混合整数规划与普通线性规划在模型文件上的区别。Node.js侧可以用模板字符串动态生成这段文本，再通过child_process调用glpsol命令行工具，或者使用WASM版本在进程内求解：

const { execFile } = require("child_process");
const fs = require("fs");

function buildLp(machine, labor, profitA, profitB) {
  return `Maximize
  obj: ${profitA} xA + ${profitB} xB
Subject To
  machine: 2 xA + 3 xB <= ${machine}
  labor: 1 xA + 2 xB <= ${labor}
Generals
  xA xB
End`;
}

async function solve(machine, labor) {
  const lpFile = "/tmp/model.lp";
  fs.writeFileSync(lpFile, buildLp(machine, labor, 30, 45));
  return new Promise((resolve, reject) => {
    execFile("glpsol", ["--lp", lpFile, "-o", "/tmp/sol.txt"], (err) => {
      if (err) return reject(err);
      const output = fs.readFileSync("/tmp/sol.txt", "utf-8");
      resolve(output);
    });
  });
}

solve(100, 80).then(console.log);

这种方式的优点是求解性能可靠，GLPK经过多年打磨，处理几千变量的模型毫无压力；缺点是需要额外安装系统依赖，在Docker或Serverless环境中部署时要多做一层配置。如果预算允许，接入了Gurobi或CPLEX的商业许可证，还可以通过它们的官方REST或Python接口获得更强的求解能力，Node.js只负责组装数据和解析结果。

实战案例：用Node.js求解排班与装箱问题

混合整数规划在实际业务中最常见的两类应用是排班问题和装箱问题。以一个简化的员工排班为例：一天分为早、中、晚三个班次，每班至少需要3人，共5名员工，每人最多上一个班且连续两班之间要休息（这里简化为每人只能上一个班），同时希望总人力成本最低。建模时用0-1变量表示员工是否被安排到某班次，这属于0-1整数规划，是MIP的特例。

const solver = require("javascript-lp-solver");

const employees = ["e1", "e2", "e3", "e4", "e5"];
const shifts = { morning: 3, afternoon: 3, night: 3 };
const cost = { e1: 100, e2: 120, e3: 90, e4: 110, e5: 130 };

const variables = {};
const constraints = { totalShifts: { max: 3 } };

// 每个班次人数约束
for (const [shift, need] of Object.entries(shifts)) {
  constraints["need_" + shift] = { min: need };
}

employees.forEach(e => {
  const v = { totalShifts: 1 };  // 每人最多一个班
  Object.keys(shifts).forEach(s => {
    v["need_" + s] = 1;          // 上该班则计数1
    v.cost = cost[e];            // 目标函数系数
    constraints["assign_" + e + "_" + s] = { max: 1 };
  });
  // 用一个技巧：把三个班次的指派拆成独立变量
  Object.keys(shifts).forEach(s => {
    variables[e + "_" + s] = {
      cost: cost[e],
      ["need_" + s]: 1,
      int: true
    };
  });
});

// 每人最多被安排到一个班次的约束
employees.forEach(e => {
  constraints["one_" + e] = { max: 1 };
  Object.keys(shifts).forEach(s => {
    variables[e + "_" + s]["one_" + e] = 1;
  });
});

const model = {
  optimize: "cost",
  opType: "min",
  constraints,
  variables,
  ints: Object.keys(variables)  // 全部变量为0-1整数
};

console.log(solver.solve(model));

这段代码展示了0-1变量建模的典型套路：为每个员工和班次的组合建立一个二元变量，用约束保证每个班次人数达标、每人不超一个班。运行后即可得到成本最低的人员分配方案。同样的思路稍加改造就能处理更复杂的规则，比如休息间隔、技能匹配、公平性软约束等。

装箱问题的建模也类似，用二元变量表示物品是否放入某个箱子，目标是最小化启用箱子数量或总成本。需要注意的是，装箱这类组合优化问题本身就接近NP难，变量组合数随规模爆炸式增长，实践中应结合问题规模选择求解器，并对求解时间设置上限（大多数求解器支持time limit参数），超时后返回当前可行解而不是无限等待。

总结一下，在Node.js中实现混合整数规划，小规模模型直接用javascript-lp-solver快速起步；中等规模建议走GLPK绑定或WASM路线；超大规模或对求解速度有硬性要求时，接入商业求解器或独立优化服务才是正解。建模能力比工具更重要，学会把业务规则翻译成目标函数和约束条件，才是解决实际优化问题的关键。

Node.js混合整数规划javascript-lp-solver修改时间：2026-09-05 11:59:23