爱的数学：使用 Python 优化婚礼餐厅座位安排

原文：towardsdatascience.com/mathematics-of-love-optimizing-a-dining-room-seating-arrangement-for-weddings-with-python-f9c57cc5c2ce

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/942316a17f62525c32af43ca05b88715.png

请跟随我来到 woof-top 接待处…（由 DALLE-3 生成）

Hannah Fry 博士的书籍《爱的数学》[1]*，是那些罕见的发现之一，聪明、幽默，而且非常容易阅读。我非常喜欢它，以至于我把它送给了我的几位密友。他们也喜欢它，但其中几位在第八章遇到了麻烦，而讽刺的是，这正是他们最兴奋的章节。

本章深入探讨了组织婚礼座位安排的棘手业务，使用数学规划和优化来确定如何安排客人，以便每个人都能尽可能享受最好的时光。听起来很酷，对吧？但这里有个问题，这本书实际上并没有指导你如何设置或解决该问题，这使我的朋友们感到有些迷茫。

现在我知道你在想什么：婚礼座位？真的吗？但别被迷惑了，这是一个非常难以解决的问题，其解决方案的应用范围远不止婚礼（尽管这个问题本身已经很重要）。想想在游轮上安排餐桌[3]、组建运动队伍或工作小组、优化投资组合，以及在我作为商学院教授的世界里，为小组项目组建有效的团队（自从我开始使用本文中描述的方法组织小组以来，小组冲突和搭便车现象显著减少）。所以，至少在我看来，这是一个值得了解如何解决的问题。

在这篇文章中，我将延续 Fry 博士的思路，并展示如何使用 Python 和 Gurobi 实际解决这个问题。我们将从分解问题开始，然后深入其混合整数规划（MIP）公式的细节。之后，我们将引入一个示例数据集并逐步解决它。最后，我会谈谈一些酷炫的扩展和高级方法，你可以使用这些方法将事情做得更加深入。

如果你之前从未使用过 Gurobi，尤其是从 Google Colab（本文中我们将使用的 IDE）开始，我邀请你阅读我之前的一篇文章，我在那篇文章中解释了如何在 Colab 环境中设置你的 Gurobi 网络许可证。以下是你可以找到文章链接的地方：

优化项目进度：使用 Gurobipy 和 Cheche_pm 热启动高效 RCPSP…

如果你还需要关于线性规划（LP）或整数规划（IP）技术的教程和更多信息，我强烈推荐你查看由Bruno Scalia C. F. Leite撰写的这些优秀的文章，以下是我提供的链接。另一个很好的资源是威廉关于数学规划的 HP 书籍[2]。

线性规划：理论与应用

混合整数线性规划建模技术全面指南

文章索引：

• 问题

• RQMKP 的 MILP 公式

• 安装库和设置 Colab 环境

• 问题数据

• 解决 RQMKP

• 可视化 RQMKP 解决方案

• 结论

• 参考文献

问题

正如汉娜·弗莱博士所说，除了选择一个糟糕的伴郎来发表演讲之外，一对新人在婚礼上可能犯的最大错误之一就是将敌人安排在同一张桌子上（在我的祖国，如果没有足够的特基诺，也会被认为是一种致命的罪行）。犯下这个错误，你将面临一个充满冰冷目光、被动攻击性评论的夜晚，如果涉及到酒精，甚至可能引发斗殴。正确的座位安排可以在整个大日子中产生巨大的差异。

每个优化问题都有一个目标函数，在这个案例中，我们的目标是最大化客人的总幸福度。客人的幸福取决于他们如何相互交往。让我们举一个例子：庞戈和克鲁埃拉。克鲁埃拉喜欢庞戈那美丽的头发，所以从克鲁埃拉这边来的交互项是+1。但并不总是相互的——庞戈担心克鲁埃拉对他毛发的迷恋，感到不安，所以他的交互项是-1。如果他们坐在一起，他们的幸福度会相互抵消为零。现在，想象一下用 100 个客人而不是两个来做这件事。这会变得有多难？如果你试图强行解决这个问题，你会发现有 100 的阶乘（100!）种座位安排方式——这是一个天文数字。这正是为什么数学优化是我们的最佳选择。

要使问题更加复杂，我们需要考虑的约束条件。这不仅仅关乎最大化幸福；我们还需要尊重餐桌容量限制，并保持情侣们在一起（如果他们被分开，他们往往会生气）。因此，我们的问题是要找到一个将客人分配到餐桌上的方案，以最大化总幸福度同时遵守这些约束条件。

现在，这里有一个哲学上的转折：我们应该旨在最大化整个场所的总幸福，还是应该尝试最大化最不幸福的桌子的幸福？哪种方法对我们客人的公平性更高？如果最大化总幸福让一张桌子绝对痛苦怎么办？别担心，这篇文章将探讨这两种方法，但我将这个问题留作思考。

这些类型的问题在文献中被称为二次分配问题。然而，我们在这里解决的问题可以被视为 受限二次多背包问题 (RQMKP)。

你可能听说过二进制背包问题——Medium 上有很多关于如何解决它的文章，我会在下面留下一个由 Maria Mouschoutzi, PhD 撰写的有趣背包文章的链接。

能放多少只宝可梦？

但 RQMKP 呢？这就是背包问题在吃蔬菜、睡八个小时和每周去健身房五次之后演变而来的。这不仅仅是一个背包；这是“那个”背包问题——它的悟空超意识版本。它已被证明是强 NP-Hard [6]，这使得它成为一个真正的难题。

与常规背包问题不同，RQMKP 涉及多个（“M”）需要填充的背包。目标函数包括二次（“Q”）和线性项，在我们的情况下，这代表幸福——一个我们需要最大化的函数。“R” 代表受限，意味着我们必须将每个物品放入一个可用的背包中，而不超过它们的个别容量，但每个物品都必须放在某个地方。

在我们的婚礼餐饮场景中，当我们专注于最大化活动的总幸福时，我们处理的是 RQMKP 的 Max-Sum 变体。当我们旨在最大化最不幸福的桌子的幸福时，我们正在查看 Max-Min 变体（我们在最大化桌子的最小值）。

现在我们对问题有了广泛的理解，让我们来讨论正式的数学规划公式。

RQMKP 的数学公式

我们将从问题的简单版本开始，即 Max-Sum RQMKP。一旦我们解决了这个问题，我们就会转向更具挑战性的 Max-Min 变体。

Max-Sum RQMKP 的数学公式

下面图 1 展示了 Max-Sum RQMKP 问题的数学公式。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a5b2d52102ec0a52242b9a553dac0099.png

图 1. Max-Sum RQMKP 的数学公式（由作者创建）

初看，上述公式可能显得有些令人畏惧，但实际上非常简单。它使用二进制变量x_{i,k}，如果客人i坐在桌子k上，则等于 1，否则为 0。目标函数只是所有坐在同一张桌子上的一对个体{i,j}的交互项c_{i,j}的总和。

1. 约束（1）确保对于每个个体i，只有一个二进制变量x_{i,k}等于 1，这意味着每个人只能坐在一张桌子上。

2. 约束（2）确保桌子k上的客人数量不超过其最大容量B_k。请注意，不同的桌子可能有不同的容量，这就是为什么每个桌子都有一个特定的参数B_k。

3. 约束（3）确保集合E中的所有夫妻{i,j}都坐在同一张桌子k上。

4. 最后，约束（4）保证了变量x_{i,k}保持二进制。

Max-Min RQMKP

Max-Min RQMKP 问题的数学公式如图 2 所示。这个公式稍微难一些，但仍然容易理解。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4f1465ae4272b50b2254c4e56392ce3b.png

图 2. Max-Min RQMKP 的数学公式（由作者创建）

这个公式与 Max-Sum-RQMKP 非常相似，但在这里，目标函数是一个我们试图最大化的新变量 ζ。约束（1）迫使 ζ 小于或等于每个桌子的总幸福值。这意味着在最佳情况下，ζ 代表最不幸福桌子的幸福值。

其余的约束（2–5）与 Max-Sum 情况完全相同，因此没有必要重复。

公式就绪后，让我们继续设置解决这些问题的环境。

安装库和设置 Colab 环境

要在 Google Colab 中使用 Gurobi，我们首先需要使用以下代码进行安装：

!pip install gurobipy

安装完成后，我们可以继续导入此项目所需的库。

importpandasaspdimportnumpyasnpimportnetworkxasnximportmatplotlib.pyplotaspltimportgurobipyasgpfromgurobipyimportGRBfromgoogle.colabimportuserdata

我们将使用几乎任何 Python 项目的标准 “mirepoix”（🥬🥕🧅）：numpy, pandas, and matplotlib。此外，我们将导入 networkx 以可视化客人之间的关系，以及 gur`obipy 以制定和解决问题。所有库就绪后，剩下的唯一任务是初始化 Gurobi 环境。您可以使用下面的代码轻松完成此操作。请注意，您将需要您的 Gurobi API 凭证才能继续。我将我的存储在 Google Colab 的 “sec_rets” t_ab 中，但如果您愿意，您可以直接将 API 访问值复制到变量中。

WLSACCESSID=userdata.get('gurobi_WLSACCESSID')WLSSECRET=userdata.get('gurobi_WLSSECRET')LICENSEID=int(userdata.get('gurobi_LICENSEID'))params={"WLSACCESSID":WLSACCESSID,"WLSSECRET":WLSSECRET,"LICENSEID":LICENSEID,}env=gp.Env(params=params)#this line initializes the gurobi environment

现在，我们已经熟悉了问题公式并设置了环境，我们可以继续解决问题。但首先，让我们看看我们将要处理的一些示例数据。

问题数据

对于这篇文章，我将使用一个包含 21 位宾客的婚礼活动的简单例子。每位宾客之前都表达过他们与另一位宾客共餐的偏好：如果他们想要共享一张桌子，则标记为+1；如果他们持中立态度，则标记为0；如果他们想要避免那个人，则标记为-1。本例的数据如下表 1 所示。