集合被覆問題#

読み: しゅうごうひふくもんだい
英名: Set Cover Problem

集合をその部分集合で被覆するとき，その費用を最小化（または最大化）する問題．具体的には，集合 \(X\) とその部分集合の族 \(\coprod = \{V_i\}_{i \in I}\) であって，

(55)#\[X = \bigcup_{i \in I}{V_i}\]

となるもの（\(X\) の被覆という），および関数

(56)#\[c \colon \coprod \to (-\infty,+\infty)\]

が与えられたときに構成される，以下の問題のことを言う．

(57)#\[\begin{split}\begin{array}{ll} \min(\max) & \sum_{j \in J}{c(V_j)} \\ \mathrm{s.t.} & J \subseteq I \\ & X = \bigcup_{j \in J}{V_j} \end{array}\end{split}\]

集合被覆問題は，0-1 整数変数を用いた整数線形計画問題として定式化できる．すなわち，\(\{x(i)\}_{i \in I}\) を 0-1 整数変数の集合として，以下のように定式化できる．

(58)#\[\begin{split}\begin{array}{ll} \min(\max) & \sum_{i \in I}{c(V_i) \cdot x(i)} \\ \mathrm{s.t.} & X = \bigcup_{i \in I, x(i)=1}{V_i} \end{array}\end{split}\]

集合被覆問題は，施設配置問題や割当問題など，様々な問題の中に現れる，基本的な構造である．