集合覆蓋部署

集合覆蓋部署（有時寫作“set-covering deployment”，縮寫為 SCDP，代表“集合覆蓋部署問題”）旨在最佳化在一組區域中駐紮軍隊，以便相對少量的部隊單位可以控制大片地理區域。ReVelle 和 Rosing (2000) 在一項關於君士坦丁大帝的機動野戰軍部署以保衛羅馬帝國的研究中首次描述了這一點。集合覆蓋部署可以用數學方法表示為 (0,1)-整數規劃問題。

為了闡述羅馬統治問題，請考慮如上所示的君士坦丁羅馬帝國的八個省份。每個區域都表示為一個白色圓盤，紅色線條表示區域連線。如果一個或多個野戰軍駐紮在該區域，則稱該區域為已安全區域；如果可以從相鄰區域向該區域部署野戰軍，則稱該區域為可安全區域。此外，假設只有當至少一支軍隊留在原始區域以提供後勤支援時，才能將野戰軍部署到相鄰區域。還假設每個區域最多包含兩支軍隊，因為可用軍隊數量有限，不能集中在任何一個區域。

然後，可以透過將帝國表示為圖 graph ，其中頂點集 ，邊集edge set ，來對這個問題進行數學公式化。然後，我們可以將兩個二元變數 和 與頂點集 中羅馬帝國圖的每個頂點（即每個省份）關聯起來，它們分別指定第一和第二野戰軍是否位於給定的頂點 。在圖論的術語中，羅馬帝國圖是一個在八個頂點上且有 13 條邊的簡單連通圖。

在集合覆蓋部署中，要解決的問題是最大化數量 ，受以下約束：

(1)

這保證了在可以駐紮第二軍團之前，第一軍團駐紮在給定的頂點，

(2)

這保證瞭如果 不包含野戰軍，它有一個擁有兩支野戰軍的鄰居，並且

(3)

這強制執行整數約束（即，當與第一個約束結合使用時，任何給定區域只能放置零個、一個或兩個野戰軍）。然後，可以將這個整數規劃問題轉化為矩陣形式，並使用標準技術求解，以找到保衛君士坦丁羅馬帝國所需的最少野戰軍數量 (ReVelle 和 Rosing 2000, Rubalcaba 2005)。

在電視劇《數字追兇》第 4 季的開篇劇集“信任度量”（2007 年）中，數學天才查理·艾普斯使用集合覆蓋部署作為類比，來最佳化在洛杉磯市中心搜尋逃犯的警察的位置。