• 整数优化

需要部分变量为整数的线性优化问题称为“混合整数程序”(MIP)。

这些变量可能以以下几种方式产生：

  • 整数变量，表示商品（例如汽车或电视机）的数量，问题是决定制造每件商品的数量，以最大限度地提高利润。
    通常，此类问题可以设置为标准线性优化问题，但需要增加变量必须为整数的要求。 下一部分将显示此类问题的示例。

  • 布尔值变量，表示值为 0-1 的决策。
    例如，请考虑将工作器分配给任务的问题（请参阅分配）。如要设置此类问题，您可以定义布尔变量 xi,j，使其等于 1（如果将工作器 i 分配给任务 j），否则等于 0。

如需大致了解整数优化，建议您参阅 Mosek 建模实战宝典。

工具

Google 提供了几种解决 MIP 问题的方法：

  • MPSolver：多个第三方 MIP 求解器的封装容器，这些求解器使用标准分支和绑定技术。
  • CP-SAT 求解器：使用 SAT（可满足性）方法的约束编程求解器。
  • 原始 CP 求解器：约束编程求解器。

我应该使用哪种求解器？

在决定是使用 MIP 求解器还是 CP-SAT 求解器，并没有严格的规则。以下为粗略指南：

  • MIP 求解器更适合用于可以设置为标准 LP，但具有任意整数变量的问题，例如上面的第一个示例。
  • CP-SAT 求解器更适合用于大部分变量都是布尔值的问题，如上面的第二个示例所示。

对于同时包含整数和布尔值变量的典型 MIP，这两种求解器在速度上通常没有明显的差异，因此您的选择可能完全取决于您个人的喜好。

如需查看同时使用 MIP 和 CP-SAT 求解器的示例，请参阅解决赋值问题和其他赋值部分。

解决整数编程问题的另一种方法是使用网络流求解器。
如需查看示例，请参阅分配为最低费用流问题。
对于可设置为网络流的问题，最小成本流求解器可能比 MIP 或 CP-SAT 求解器更快。但是，并非所有 MIP 都可以通过这种方式设置。