Set Covering Problem

Overview

The Set Covering Problem is a fundamental optimization challenge: given a collection of sets, find the minimum number of sets needed to cover all elements. This NP-hard problem appears in many real-world applications including facility location, scheduling, and resource allocation.

This example demonstrates:

  • Formulating a set covering problem
  • Converting it to a tensor network
  • Finding minimum set covers
  • Analyzing the solution space

We'll use the camera location and stadium area example from the Cornell University Computational Optimization Open Textbook.

using GenericTensorNetworks, Graphs

Define our sets (each representing a camera's coverage area)

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]

Tensor Network Formulation

Define the set covering problem:

setcover = SetCovering(sets)
SetCovering{Int64, Int64, UnitWeight}([1, 3, 4, 6, 7, 8, 12, 2, 5, 9, 11, 13, 14, 15, 10], [[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]], [1, 1, 1, 1, 1, 1, 1, 1])

The problem consists of:

  1. Coverage constraints: Every element must be covered by at least one set
  2. Optimization objective: Minimize the number of sets used
constraints(setcover)
15-element Vector{ProblemReductions.LocalConstraint}:
 LocalConstraint on [1, 4, 7, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [1, 5]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalConstraint on [1, 2, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ false │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ true  │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ true  │
│   [0, 1, 1]   │ true  │
│   [1, 1, 1]   │ true  │
└───────────────┴───────┘

 LocalConstraint on [1, 5, 7, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [1, 2]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalConstraint on [2, 6, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ false │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ true  │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ true  │
│   [0, 1, 1]   │ true  │
│   [1, 1, 1]   │ true  │
└───────────────┴───────┘

 LocalConstraint on [2, 5, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ false │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ true  │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ true  │
│   [0, 1, 1]   │ true  │
│   [1, 1, 1]   │ true  │
└───────────────┴───────┘

 LocalConstraint on [3, 4, 7, 8]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│ [0, 0, 0, 0]  │ false │
│ [1, 0, 0, 0]  │ true  │
│ [0, 1, 0, 0]  │ true  │
│ [1, 1, 0, 0]  │ true  │
│ [0, 0, 1, 0]  │ true  │
│ [1, 0, 1, 0]  │ true  │
│ [0, 1, 1, 0]  │ true  │
│ [1, 1, 1, 0]  │ true  │
│ [0, 0, 0, 1]  │ true  │
│ [1, 0, 0, 1]  │ true  │
│ [0, 1, 0, 1]  │ true  │
│ [1, 1, 0, 1]  │ true  │
│ [0, 0, 1, 1]  │ true  │
│ [1, 0, 1, 1]  │ true  │
│ [0, 1, 1, 1]  │ true  │
│ [1, 1, 1, 1]  │ true  │
└───────────────┴───────┘

 LocalConstraint on [3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│      [0]      │ false │
│      [1]      │ true  │
└───────────────┴───────┘

 LocalConstraint on [3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│      [0]      │ false │
│      [1]      │ true  │
└───────────────┴───────┘

 LocalConstraint on [3, 7]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalConstraint on [3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│      [0]      │ false │
│      [1]      │ true  │
└───────────────┴───────┘

 LocalConstraint on [4, 5, 6]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│   [0, 0, 0]   │ false │
│   [1, 0, 0]   │ true  │
│   [0, 1, 0]   │ true  │
│   [1, 1, 0]   │ true  │
│   [0, 0, 1]   │ true  │
│   [1, 0, 1]   │ true  │
│   [0, 1, 1]   │ true  │
│   [1, 1, 1]   │ true  │
└───────────────┴───────┘

 LocalConstraint on [4, 6]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ false │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ true  │
└───────────────┴───────┘

 LocalConstraint on [5]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│      [0]      │ false │
│      [1]      │ true  │
└───────────────┴───────┘

objectives(setcover)
8-element Vector{ProblemReductions.LocalSolutionSize{Int64}}:
 LocalSolutionSize{Int64} on [1]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [2]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [3]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [4]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [5]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [6]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [7]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

 LocalSolutionSize{Int64} on [8]
┌───────────────┬──────┐
│ Configuration │ Size │
├───────────────┼──────┤
│      [0]      │  0   │
│      [1]      │  1   │
└───────────────┴──────┘

Convert to tensor network representation:

problem = GenericTensorNetwork(setcover)
GenericTensorNetwork{SetCovering{Int64, Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^8.426, space = 2^4.0, read-write = 2^9.377

Mathematical Background

For each set $s$ with weight $w_s$, we assign a boolean variable $v_s ∈ \{0,1\}$, indicating whether the set is included in the solution.

The network uses two types of tensors:

  1. Set Tensors: For each set $s$:

    \[W(x_s, w_s) = \begin{pmatrix} 1 \\ x_s^{w_s} \end{pmatrix}\]

  2. Element Constraint Tensors: For each element a and its containing sets N(a):

    \[B_{s_1,...,s_{|N(a)|}} = \begin{cases} 0 & \text{if all } s_i = 0 \text{ (element not covered - invalid)} \\ 1 & \text{otherwise (element is covered - valid)} \end{cases}\]

Check the contraction complexity:

contraction_complexity(problem)
Time complexity: 2^8.426264754702098
Space complexity: 2^4.0
Read-write complexity: 2^9.377210530388552

Solution Analysis

1. Set Covering Polynomial

The polynomial $P(S,x) = \sum_i c_i x^i$ counts set covers by size, where $c_i$ is the number of valid covers using $i$ sets

covering_polynomial = solve(problem, GraphPolynomial())[]
2∙x4 + 11∙x5 + 13∙x6 + 6∙x7 + x8

2. Minimum Set Cover Size

Find the minimum number of sets needed:

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

Count minimum set covers:

counting_minimum_setcovering = solve(problem, CountingMin())[]
(4.0, 2.0)ₜ

3. Minimum Set Cover Configurations

Enumerate all minimum set covers:

min_configs = read_config(solve(problem, ConfigsMin())[])
2-element Vector{StaticBitVector{8, 1}}:
 01111000
 10101100

The two optimal solutions are $\{z_1, z_3, z_5, z_6\}$ and $\{z_2, z_3, z_4, z_5\}$, where $z_i$ represents the $i$-th set in our original list.

Verify solutions are valid:

all(c->is_set_covering(problem.problem, c), min_configs)
true

Note: For finding just one minimum set cover, use the SingleConfigMin property

More APIs

The Independent Set Problem chapter has more examples on how to use the APIs.

This page was generated using Literate.jl.