集合覆盖部署

集合覆盖部署（有时写作“set-covering deployment”，缩写为 SCDP，代表“集合覆盖部署问题”）旨在优化在一组区域中驻扎军队，以便相对少量的部队单位可以控制大片地理区域。ReVelle 和 Rosing (2000) 在一项关于君士坦丁大帝的机动野战军部署以保卫罗马帝国的研究中首次描述了这一点。集合覆盖部署可以用数学方法表示为 (0,1)-整数规划问题。

为了阐述罗马统治问题，请考虑如上所示的君士坦丁罗马帝国的八个省份。每个区域都表示为一个白色圆盘，红色线条表示区域连接。如果一个或多个野战军驻扎在该区域，则称该区域为已安全区域；如果可以从相邻区域向该区域部署野战军，则称该区域为可安全区域。此外，假设只有当至少一支军队留在原始区域以提供后勤支持时，才能将野战军部署到相邻区域。还假设每个区域最多包含两支军队，因为可用军队数量有限，不能集中在任何一个区域。

然后，可以通过将帝国表示为图 graph ，其中顶点集 ，边集edge set ，来对这个问题进行数学公式化。然后，我们可以将两个二元变量 和 与顶点集 中罗马帝国图的每个顶点（即每个省份）关联起来，它们分别指定第一和第二野战军是否位于给定的顶点 。在图论的术语中，罗马帝国图是一个在八个顶点上且有 13 条边的简单连通图。

在集合覆盖部署中，要解决的问题是最大化数量 ，受以下约束：

(1)

这保证了在可以驻扎第二军团之前，第一军团驻扎在给定的顶点，

(2)

这保证了如果 不包含野战军，它有一个拥有两支野战军的邻居，并且

(3)

这强制执行整数约束（即，当与第一个约束结合使用时，任何给定区域只能放置零个、一个或两个野战军）。然后，可以将这个整数规划问题转化为矩阵形式，并使用标准技术求解，以找到保卫君士坦丁罗马帝国所需的最少野战军数量 (ReVelle 和 Rosing 2000, Rubalcaba 2005)。

在电视剧《数字追凶》第 4 季的开篇剧集“信任度量”（2007 年）中，数学天才查理·艾普斯使用集合覆盖部署作为类比，来优化在洛杉矶市中心搜寻逃犯的警察的位置。