解决离散优化问题的强大算法
分支界定法是许多混合整数规划（MIP）求解器的核心算法。它是数学优化工具包的重要组成部分，特别适用于较小的问题或问题包含大量约束的情况。此外，它的直观性使其易于理解，无需复杂的数学公式。
在本实践文章中，我们将深入探讨一个数学优化问题。我们将使用分支界定法解决它，这是解决此类问题的一种优秀技术。我们的重点将放在一个以猫为主题的问题上——因为面对现实吧，谁不喜欢猫？然而，如果你更喜欢狗，可以在我们的讨论中每次遇到“猫”时心里替换成“狗”。原理和方法完全相同！
问题介绍
想象一下，你是一家猫收容所的主人。每天，宠物主人可以带着他们的猫来到你这里，你负责照顾它们。很多人在疫情期间领养了猫，但现在每个人都需要回到办公室。因此，你的公司运营得很好。
事实上，有点太好了。你在给你的建筑物的房间安排所有猫的时候遇到了一些困难。有时候你不得不拒绝人们的请求，因为请求太多。这就是为什么你决定创建一个优化算法来帮助你找到为所有猫登记提供最少房间数量的方法。
让我们来看一个例子。假设有3只猫请求留在你的收容所。它们的名字是Lily、Charlie和Meowster。我们如何把这三只猫分在不同的房间里呢？我们最多只需要三个房间，以下是分组猫的所有可能解：
分组与贝尔数
如您所见，有5种将这3只猫分组的方式。在数学中，将集合的元素分组的方式称为分组。贝尔数对应着分组的总数…