Set packing problem

Problem definition

The set packing problem is generalization of the IndependentSet problem from the simple graph to the multigraph. Suppose one has a finite set $S$ and a list of subsets of $S$. Then, the set packing problem asks if some $k$ subsets in the list are pairwise disjoint. In the following, we will find the solution space properties for the set in the Set covering problem.

using GenericTensorNetworks, Graphs

The packing 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 packing problem with the SetPacking type as

problem = SetPacking(sets)

SetPacking{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 packing problem can be obtained by

problem = GenericTensorNetwork(problem)

GenericTensorNetwork{SetPacking{Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}(SetPacking{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()), 8∘4∘5∘1, 5∘1∘4∘8 -> 
├─ 6∘5∘8∘1, 1∘5∘6∘4 -> 8∘4∘5∘1
│  ├─ 2∘8∘1∘6, 1∘2∘8∘5 -> 6∘5∘8∘1
│  │  ├─ 1∘6∘2, 1∘6∘8 -> 2∘8∘1∘6
│  │  │  ├─ 1∘2, 2∘6 -> 1∘6∘2
│  │  │  │  ├─ 2, 2∘1 -> 1∘2
│  │  │  │  │  ⋮
│  │  │  │  │  
│  │  │  │  └─ 6, 2∘6 -> 2∘6
│  │  │  │     ⋮
│  │  │  │     
│  │  │  └─ 1∘8, 6∘8 -> 1∘6∘8
│  │  │     ├─ 8, 1∘8 -> 1∘8
│  │  │     │  ⋮
│  │  │     │  
│  │  │     └─ 6∘8
│  │  └─ 1∘5, 2∘5∘8 -> 1∘2∘8∘5
│  │     ├─ 5, 1∘5 -> 1∘5
│  │     │  ├─ 5
│  │     │  └─ 1∘5
│  │     └─ 5∘8∘2, 5∘8 -> 2∘5∘8
│  │        ├─ 2∘5, 2∘8 -> 5∘8∘2
│  │        │  ⋮
│  │        │  
│  │        └─ 5∘8
│  └─ 1∘6∘4, 4∘6∘5 -> 1∘5∘6∘4
│     ├─ 1∘4, 4∘6 -> 1∘6∘4
│     │  ├─ 4, 1∘4 -> 1∘4
│     │  │  ├─ 4
│     │  │  └─ 1∘4
│     │  └─ 4∘6
│     └─ 4∘5, 5∘6 -> 4∘6∘5
│        ├─ 4∘5
│        └─ 5∘6
└─ 4∘8∘5∘7, 1∘8∘4∘7 -> 5∘1∘4∘8
   ├─ 4∘8∘3, 3∘5∘7 -> 4∘8∘5∘7
   │  ├─ 4∘3, 3∘8 -> 4∘8∘3
   │  │  ├─ 3, 3∘4 -> 4∘3
   │  │  │  ├─ 3
   │  │  │  └─ 3∘4
   │  │  └─ 3∘8
   │  └─ 3∘7, 5∘7 -> 3∘5∘7
   │     ├─ 3∘7
   │     └─ 5∘7
   └─ 1∘4∘7, 4∘7∘8 -> 1∘8∘4∘7
      ├─ 1∘7, 4∘7 -> 1∘4∘7
      │  ├─ 7, 1∘7 -> 1∘7
      │  │  ├─ 7
      │  │  └─ 1∘7
      │  └─ 4∘7
      └─ 4∘8, 7∘8 -> 4∘7∘8
         ├─ 4∘8
         └─ 7∘8
, Dict{Int64, Int64}())

Theory (can skip)

Let $S$ be the target set packing 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)|} > 1,\\ 1 & \text{otherwise}. \end{cases}\]

This tensor means if in a configuration, two sets contain the element $a$, then this configuration is forbidden, One can check the contraction time space complexity of a SetPacking instance by typing:

contraction_complexity(problem)

Time complexity: 2^8.321928094887362
Space complexity: 2^4.0
Read-write complexity: 2^9.172427508645482

Solving properties

Counting properties

The "graph" polynomial

The graph polynomial for the set packing problem is defined as

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

where $c_k$ is the number of configurations having $k$ sets, and $\alpha(S)$ is the maximum size of the packing.

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

The maximum number of sets that packing the set of elements can be computed with the SizeMax property:

max_packing_size = solve(problem, SizeMax())[]

3.0ₜ

Similarly, we have its counting CountingMax:

counting_maximum_set_packing = solve(problem, CountingMax())[]

(3.0, 1.0)ₜ

Configuration properties

Finding maximum set packing

One can enumerate all maximum set packing with the ConfigsMax property in the program.

max_configs = solve(problem, ConfigsMax())[].c

{10100100}

Hence the only optimal solution is $\{z_1, z_3, z_6\}$ that has size 3. The correctness of this result can be checked with the is_set_packing function.

all(c->is_set_packing(sets, c), max_configs)

true

Similarly, if one is only interested in computing one of the maximum set packing, one can use the graph property SingleConfigMax.

This page was generated using Literate.jl.