Set covering problem

Problem definition

The set covering problem is a significant NP-hard problem in combinatorial optimization. Given a collection of elements, the set covering problem aims to find the minimum number of sets that incorporate (cover) all of these elements. In the following, we will find the solution space properties for the camera location and stadium area example in the Cornell University Computational Optimization Open Textbook.

using GenericTensorNetworks, Graphs

The covering stadium areas of cameras are represented as the following sets.

sets = [[1,3,4,6,7], [4,7,8,12], [2,5,9,11,13],
    [1,2,14,15], [3,6,10,12,14], [8,14,15],
    [1,2,6,11], [1,2,4,6,8,12]]

8-element Vector{Vector{Int64}}:
 [1, 3, 4, 6, 7]
 [4, 7, 8, 12]
 [2, 5, 9, 11, 13]
 [1, 2, 14, 15]
 [3, 6, 10, 12, 14]
 [8, 14, 15]
 [1, 2, 6, 11]
 [1, 2, 4, 6, 8, 12]

Generic tensor network representation

We can define the set covering problem with the SetCovering type as

setcover = SetCovering(sets)

SetCovering{Int64, UnitWeight}([[1, 3, 4, 6, 7], [4, 7, 8, 12], [2, 5, 9, 11, 13], [1, 2, 14, 15], [3, 6, 10, 12, 14], [8, 14, 15], [1, 2, 6, 11], [1, 2, 4, 6, 8, 12]], UnitWeight())

The tensor network representation of the set covering problem can be obtained by

problem = GenericTensorNetwork(setcover)

GenericTensorNetwork{SetCovering{Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}(SetCovering{Int64, UnitWeight}([[1, 3, 4, 6, 7], [4, 7, 8, 12], [2, 5, 9, 11, 13], [1, 2, 14, 15], [3, 6, 10, 12, 14], [8, 14, 15], [1, 2, 6, 11], [1, 2, 4, 6, 8, 12]], UnitWeight()), 1∘4∘7∘8, 1∘4∘7∘8 -> 
├─ 1∘4∘7∘8, 7∘4∘8∘1 -> 1∘4∘7∘8
│  ├─ 1∘4∘7∘8, 1∘4∘7∘8 -> 1∘4∘7∘8
│  │  ├─ 8, 8∘1∘4∘7 -> 1∘4∘7∘8
│  │  │  ├─ 8
│  │  │  └─ 7, 7∘8∘1∘4 -> 8∘1∘4∘7
│  │  │     ├─ 7
│  │  │     └─ 4, 4∘7∘8∘1 -> 7∘8∘1∘4
│  │  │        ⋮
│  │  │        
│  │  └─ 1∘4∘7∘8
│  └─ 7∘8∘1∘5, 1∘4∘5∘8 -> 7∘4∘8∘1
│     ├─ 7∘8∘1∘5, 1∘5∘7∘8 -> 7∘8∘1∘5
│     │  ├─ 1∘5, 1∘5∘7∘8 -> 7∘8∘1∘5
│     │  │  ├─ 1∘5, 1∘5 -> 1∘5
│     │  │  │  ⋮
│     │  │  │  
│     │  │  └─ 1∘5∘7∘8, 1∘5∘7∘8 -> 1∘5∘7∘8
│     │  │     ⋮
│     │  │     
│     │  └─ 1∘5∘7∘8
│     └─ 1∘5∘8∘2, 2∘8∘4∘5 -> 1∘4∘5∘8
│        ├─ 8∘1∘2, 2∘5∘8 -> 1∘5∘8∘2
│        │  ├─ 8∘1∘2, 1∘2∘8 -> 8∘1∘2
│        │  │  ⋮
│        │  │  
│        │  └─ 2∘5∘8, 2∘5∘8 -> 2∘5∘8
│        │     ⋮
│        │     
│        └─ 2∘8∘6, 4∘5∘6 -> 2∘8∘4∘5
│           ├─ 2∘8∘6, 2∘6∘8 -> 2∘8∘6
│           │  ⋮
│           │  
│           └─ 4∘5∘6, 4∘5∘6 -> 4∘5∘6
│              ⋮
│              
└─ 4∘7∘8, 1∘4∘7∘8 -> 1∘4∘7∘8
   ├─ 4∘7∘8∘3, 3∘4∘7∘8 -> 4∘7∘8
   │  ├─ 4∘7∘8∘3, 4∘8∘3∘7 -> 4∘7∘8∘3
   │  │  ├─ 4∘7∘8∘3, 3∘4∘7∘8 -> 4∘7∘8∘3
   │  │  │  ├─ 3, 4∘7∘8∘3 -> 4∘7∘8∘3
   │  │  │  │  ⋮
   │  │  │  │  
   │  │  │  └─ 3∘4∘7∘8
   │  │  └─ 3∘7, 3∘4∘7∘8 -> 4∘8∘3∘7
   │  │     ├─ 3∘7, 3∘7 -> 3∘7
   │  │     │  ⋮
   │  │     │  
   │  │     └─ 3∘4∘7∘8
   │  └─ 3∘4∘7∘8
   └─ 1∘4∘7∘8, 1∘4∘7∘8 -> 1∘4∘7∘8
      ├─ 1∘4∘7∘8
      └─ 1∘4∘7∘8
, Dict{Int64, Int64}())

Theory (can skip)

Let $S$ be the target set covering problem that we want to solve. For each set $s \in S$, we associate it with a weight $w_s$ to it. The tensor network representation map a set $s\in S$ to a boolean degree of freedom $v_s\in\{0, 1\}$. For each set $s$, we defined a parameterized rank-one tensor indexed by $v_s$ as

\[W(x_s^{w_s}) = \left(\begin{matrix} 1 \\ x_s^{w_s} \end{matrix}\right)\]

where $x_s$ is a variable associated with $s$. For each unique element $a$, we defined the constraint over all sets containing it $N(a) = \{s | s \in S \land a\in s\}$:

\[B_{s_1,s_2,\ldots,s_{|N(a)|}} = \begin{cases} 0 & s_1=s_2=\ldots=s_{|N(a)|}=0,\\ 1 & \text{otherwise}. \end{cases}\]

This tensor means if none of the sets containing element $a$ are included, then this configuration is forbidden, One can check the contraction time space complexity of a SetCovering instance by typing:

contraction_complexity(problem)

Time complexity: 2^9.149747119504683
Space complexity: 2^4.0
Read-write complexity: 2^10.384783750093353

Solving properties

Counting properties

The "graph" polynomial

The graph polynomial for the set covering problem is defined as

\[P(S, x) = \sum_{k=0}^{|S|} c_k x^k,\]

where $c_k$ is the number of configurations having $k$ sets.

covering_polynomial = solve(problem, GraphPolynomial())[]

The minimum number of sets that covering the set of elements can be computed with the SizeMin property:

min_cover_size = solve(problem, SizeMin())[]

4.0ₜ

Similarly, we have its counting CountingMin:

counting_minimum_setcovering = solve(problem, CountingMin())[]

(4.0, 2.0)ₜ

Configuration properties

Finding minimum set covering

One can enumerate all minimum set covering with the ConfigsMin property in the program.

min_configs = solve(problem, ConfigsMin())[].c

{10101100, 01111000}

Hence the two optimal solutions are $\{z_1, z_3, z_5, z_6\}$ and $\{z_2, z_3, z_4, z_5\}$. The correctness of this result can be checked with the is_set_covering function.

all(c->is_set_covering(sets, c), min_configs)

true

Similarly, if one is only interested in computing one of the minimum set coverings, one can use the graph property SingleConfigMin.

This page was generated using Literate.jl.