核心内容摘要
博雅与榜一大哥：现象级互动的背后，是怎样的情感连接？
原文towardsdatascience.com/mathematics-of-love-optimizing-a-dining-room-seating-arrangement-for-weddings-with-python-f9c57cc5c2cehttps://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/942316a17f62525c32af43ca05b
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/a5b2d52102ec0a52242b9a553dac
png图
Max-Sum RQMKP 的数学公式由作者创建初看上述公式可能显得有些令人畏惧但实际上非常简单。
它使用二进制变量x_{i,k}如果客人i坐在桌子k上则等于 1否则为 0。
目标函数只是所有坐在同一张桌子上的一对个体{i,j}的交互项c_{i,j}的总和。
约束1确保对于每个个体i只有一个二进制变量x_{i,k}等于 1这意味着每个人只能坐在一张桌子上。
约束2确保桌子k上的客人数量不超过其最大容量B_k。
请注意不同的桌子可能有不同的容量这就是为什么每个桌子都有一个特定的参数B_k。
约束3确保集合E中的所有夫妻{i,j}都坐在同一张桌子k上。
最后约束4保证了变量x_{i,k}保持二进制。
Max-Min RQMKPMax-Min RQMKP 问题的数学公式如图 2 所示。
这个公式稍微难一些但仍然容易理解。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4f1465ae4272b50b2254c4e56392ce3b.png图
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 以可视化客人之间的关系以及 gurobipy 以制定和解决问题。
所有库就绪后剩下的唯一任务是初始化 Gurobi 环境。
您可以使用下面的代码轻松完成此操作。
请注意您将需要您的 Gurobi API 凭证才能继续。
我将我的存储在 Google Colab 的 “sec_rets” t_ab 中但如果您愿意您可以直接将 API 访问值复制到变量中。
WLSACCESSIDuserdata.get(gurobi_WLSACCESSID)WLSSECRETuserdata.get(gurobi_WLSSECRET)LICENSEIDint(userdata.get(gurobi_LICENSEID))params{WLSACCESSID:WLSACCESSID,WLSSECRET:WLSSECRET,LICENSEID:LICENSEID,}envgp.Env(paramsparams)#this line initializes the gurobi environment现在我们已经熟悉了问题公式并设置了环境我们可以继续解决问题。
但首先让我们看看我们将要处理的一些示例数据。
问题数据对于这篇文章我将使用一个包含 21 位宾客的婚礼活动的简单例子。
每位宾客之前都表达过他们与另一位宾客共餐的偏好如果他们想要共享一张桌子则标记为1如果他们持中立态度则标记为0如果他们想要避免那个人则标记为-1。
本例的数据如下表 1 所示。