algorithm - 有哪些非常适合整数线性规划的问题示例？

Question

我一直在编写软件来解决业务问题。我在浏览其中一篇 SO 帖子时遇到了 LIP。我用谷歌搜索了它，但我无法说明如何使用它来解决业务问题。如果有人能用通俗易懂的方式帮助我理解，我将不胜感激。

Answer 1

ILP 基本上可以用来解决任何涉及做出一系列决策的问题，每个决策只有几个可能的结果，所有结果都是提前知道的，并且其中的整体“质量”可以使用不依赖于选项之间“交互”的函数来描述任何选项组合。要查看它是如何工作的，最简单的方法是进一步限制只能为 0 或 1(整数的最小有用范围)的变量。现在:

• 每个需要回答是/否的决定都变成一个变量
• 目标函数应该将我们想要最大化(或最小化)的事物描述为这些变量的加权组合
• 您需要找到一种方法来使用一个或多个线性等式或不等式约束来表达每个约束(不能同时做出的选择的组合)

例子

例如，假设您有 3 个 worker Anne、Bill 和 Carl，以及 3 个工作岗位:除尘、打字和包装。所有的人都可以做所有的工作，但他们每个人在每项工作中的效率/能力水平不同，所以我们想为他们每个人找到最好的任务，以最大限度地提高整体效率。我们希望每个人恰好完成一份工作。

变量

设置此问题的一种方法是使用 9 个变量，每个变量对应 worker 和工作的每个组合。如果 Anne 应该 Dust 在最优解中，变量 x_ad 将获得值 1，否则为 0；如果 Bill 应该在最优解中打包，x_bp 将获得值 1，否则为 0；等等。

目标函数

接下来要做的是制定一个我们想要最大化或最小化的目标函数。假设根据 Anne、Bill 和 Carl 最近的绩效评估，我们有一个包含 9 个数字的表格，告诉我们他们每个人完成这 3 项工作需要多少分钟。在这种情况下，取所有 9 个变量的总和是有意义的，每个变量乘以该特定 worker 执行该特定工作所需的时间，并寻求最小化这个总和——也就是说，最小化完成该工作所花费的总时间完成所有工作。

约束

最后一步是给出约束条件，以强制执行 (a) 每个人只做 1 份工作，以及 (b) 每份工作只由 1 个人完成。 (请注意，实际上这些步骤可以按任何顺序完成。)

为了确保 Anne 恰好完成 1 个工作，我们可以添加 x_ad + x_at + x_ap = 1 的约束。可以为 Bill 和 Carl 添加类似的约束。

为了确保正好有 1 个人 Dusts，我们可以添加 x_ad + x_bd + x_cd = 1 的约束。可以为 Typing 和 Packing 添加类似的约束。

一共有6个约束条件。您现在可以将这个 9 变量、6 约束问题提供给 ILP 求解器，它会吐出其中一个最优解中变量的值——正好其中 3 个为 1，其余为 0。 1 的 3 告诉你哪些人应该做哪些工作!

ILP 是通用的

碰巧，这个特殊问题有一个 special structure这使得它可以使用不同的算法更有效地解决。使用 ILP 的优点是可以很容易地合并问题的变体:例如，如果实际上有 4 个人和只有 3 个工作，那么我们需要放宽限制，以便每个人最多 1 份工作，而不是恰好 1 份工作。这可以通过将第一个 3 个约束中的每个约束中的等号更改为小于或等于符号来简单地表达。