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

本文概述

• 运筹学算法
• 示例问题：计划
• 加大难度：其他限制
• 总结

运筹学是使用计算机做出最佳决策的科学, 已在许多软件领域得到使用和应用。举几个例子, 物流公司用它来确定从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人员配备小组帮助, 该小组每班可提供10名Dothraki工人, 每班40美元。

此外, 假设由于工厂外不断发生人际冲突, Cersei和Jaime无法与Daenerys或Jon一起工作。此外, Jaime和Cersei无法一起工作。最后, 人际关系特别复杂的Arya无法与Jaime, Cersei或Melisandre一起轮班工作。

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

解

但是, 使用混合整数规划, 要容易得多。我们只需要像下面这样修改我们的代码：

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

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

有了我们, 结果就是尊重被禁止的工人名单, 遵守劳动法规, 并明智地使用Dothraki工人。

总结

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

我希望本文能激发你学习有关运筹学的更多知识, 并让你考虑如何将此技术应用于你的项目。当涉及到令人兴奋的优化算法和运筹学世界时, 我们才真正看到了冰山一角。

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