混合整数规划：计算决策指南

运筹学是一门使用计算机做出最佳决策的科学，已在软件的许多领域得到应用和应用。 举几个例子，物流公司用它来确定从 A 点到 B 点的最佳路线，电力公司用它来确定电力生产计划，制造公司用它来寻找工厂的最佳人员配置模式。

今天，我们将通过一个假设问题来探索运筹学的力量。 具体来说，我们将使用混合整数规划 (MIP) 来确定假设工厂的最佳人员配置模式。

运筹学算法

在我们深入研究示例问题之前，回顾一下运筹学中的一些基本概念并了解我们今天将使用的一些工具会很有帮助。

线性规划算法

线性规划是一种运筹学技术，用于确定数学模型中的最佳结果，其中目标和约束表示为线性方程组。 示例线性规划模型可能如下所示：

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

在我们非常简单的示例中，我们可以看到最优结果是 5，其中 a = 2 和 b = 3。虽然这是一个相当简单的示例，但您可能可以想象一个使用数千个变量和数百个约束的线性规划模型.

一个很好的例子可能是投资组合问题，您最终可能会得到类似下面的伪代码：

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

这将是相当复杂且难以通过手动或反复试验来解决。 运筹学软件将使用几种算法来快速解决这些问题。 如果你对底层算法感兴趣，我建议在这里学习单纯形法和内点法。

整数规划算法

整数规划类似于线性规划，但额外允许部分或全部变量为整数值。 虽然一开始这似乎不是一个很大的改进，但它使我们能够解决许多单独使用线性规划可能无法解决的问题。

一个这样的问题是背包问题，我们得到一组具有指定值和重量的物品，并被要求找到我们可以装入背包的物品的最高价值组合。 线性规划模型将无法解决这个问题，因为没有办法表达您可以将物品放入背包或不放入背包的想法，但您不能将物品的一部分放入背包 - 每个变量都是连续的多变的！

一个示例背包问题可能具有以下参数：

MIP 模型将如下所示：

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

在这种情况下，最优解是 a=0, b=1, c=0, d=1，总项的值为 17。

我们今天要解决的问题还需要整数规划，因为工厂的员工可以安排轮班或不安排轮班——为简单起见，您不能安排该工厂的员工轮班 2/3。

为了使整数规划成为可能，使用了几种数学算法。 如果你对底层算法感兴趣，我建议在这里学习切割平面算法和分支定界算法。

示例问题：调度

问题描述

今天，我们将探讨一个工厂的人员配备问题。 作为工厂的管理层，我们希望尽量减少劳动力成本，但我们希望确保每个班次都有足够的覆盖率以满足生产需求。

假设我们有五个班次，人员需求如下：

并且，假设我们有以下工人：

为简单起见，让我们暂时假设可用性和成本是唯一关心的问题。

我们的工具

对于今天的问题，我们将使用一个名为 CBC 的开源分支切割软件。 我们将使用 PuLP 与该软件进行交互，PuLP 是一个流行的 Python 运筹学建模库。 您可以在此处找到有关它的信息。

PuLP 允许我们以非常 Python 的方式构建 MIP 模型，并与现有的 Python 代码很好地集成。 这非常有用，因为一些最流行的数据操作和分析工具是用 Python 编写的，而且大多数商业运筹学系统都需要在优化前后进行大量的数据处理。

为了展示 PuLP 的简单性和优雅性，这里是早期的背包问题并在 PuLP 中解决：

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

运行这个，你应该得到输出：

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

现在进入我们的调度问题！

编码我们的解决方案

我们解决方案的编码相当简单。 首先，我们要定义我们的数据：

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

接下来，我们将要定义模型：

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

现在我们只要求它解决并打印结果！

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

运行代码后，您应该会看到以下输出：

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

稍微提高难度：附加约束

尽管之前的模型很有趣且有用，但它并没有充分展示混合整数编程的威力。 我们还可以轻松编写一个for循环来为每个班次找到最便宜的x工人，其中x是一个班次所需的工人数。 为了演示如何使用 MIP 来解决以命令式方式难以解决的问题，让我们看看如果我们添加一些额外的约束会发生什么。

附加约束

假设，由于新的劳动法规，任何工人都不能被分配到超过 2 个班次。 为了解决工作量的增加，我们聘请了 Dothraki Staffing Group 的帮助，他们将为每班提供多达 10 名 Dothraki 工人，每班 40 美元。

另外假设，由于我们工厂外一些持续的人际冲突，瑟曦和詹姆无法与丹妮莉丝或琼恩一起轮班工作。 此外，詹姆和瑟曦无法一起轮班工作。 最后，人际关系特别复杂的艾莉亚无法与詹姆、瑟曦或梅丽珊卓一起轮班工作。

增加这两个新的约束和资源绝不会使问题无法通过命令式方式解决，但它会使解决方案变得更加困难，因为必须考虑将工人安排到特定班次的机会成本。

解决方案

然而，对于混合整数编程，它要容易得多。 我们只需要像这样修改我们的代码：

定义禁止列表和一些约束：

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

填充用于实施禁令和最大班次约束的变量：

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

添加 Dothraki 变量：

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

我们还需要一个稍微修改的循环来计算班次和禁令要求：

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

最后，打印结果：

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

我们应该很高兴。 运行代码，您应该会看到如下输出：

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

我们得到了它，这是一个尊重被禁止工人名单、遵守劳动法规并明智地使用多斯拉克工人的结果。

结论

今天，我们探索了使用混合整数规划来做出更好的决策。 我们讨论了运筹学中使用的底层算法和技术，并研究了一个代表混合整数编程在现实世界中的应用的示例问题。

我希望这篇文章能启发你更多地了解运筹学，并让你思考如何将这项技术应用到你的项目中。 当谈到令人兴奋的优化算法和运筹学世界时，我们才真正看到了冰山一角。

您可以在 GitHub 上找到与本文相关的所有代码。 如果您想讨论更多，请在下面分享您的评论！