Set Packing Problem

Overview

The Set Packing Problem is a generalization of the Independent Set problem from simple graphs to hypergraphs. Given a collection of sets, the goal is to find the maximum number of mutually disjoint sets (sets that share no common elements).

This example demonstrates:

Formulating a set packing problem
Converting it to a tensor network
Finding maximum set packings
Analyzing the solution space

We'll use the same sets from the Set Covering Problem example for comparison.

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 packing problem:

setpacking = SetPacking(sets)

SetPacking{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:

Packing constraints: No element can be covered by more than one set
Optimization objective: Maximize the number of sets used

constraints(setpacking)

15-element Vector{ProblemReductions.LocalConstraint}:
 LocalConstraint on [3]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│      [0]      │ true  │
│      [1]      │ true  │
└───────────────┴───────┘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

objectives(setpacking)

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(setpacking)

GenericTensorNetwork{SetPacking{Int64, Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^8.209, space = 2^4.0, read-write = 2^9.152

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:

Set Tensors: For each set $s$:
\[W(x_s, w_s) = \begin{pmatrix} 1 \\ x_s^{w_s} \end{pmatrix}\]
Element Constraint Tensors: For each element a and its containing sets N(a):
\[B_{s_1,...,s_{|N(a)|}} = \begin{cases} 0 & \text{if } \sum_i s_i > 1 \text{ (element covered multiple times - invalid)} \\ 1 & \text{otherwise (element covered at most once - valid)} \end{cases}\]

Check the contraction complexity:

contraction_complexity(problem)

Time complexity: 2^8.20945336562895
Space complexity: 2^4.0
Read-write complexity: 2^9.152284842306582

Solution Analysis

1. Set Packing Polynomial

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

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

1 + 8∙x + 8∙x² + x³

2. Maximum Set Packing Size

Find the maximum number of mutually disjoint sets:

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

3.0ₜ

Count maximum set packings:

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

(3.0, 1.0)ₜ

3. Maximum Set Packing Configurations

Enumerate all maximum set packings:

max_configs = read_config(solve(problem, ConfigsMax())[])

1-element Vector{StaticBitVector{8, 1}}:
 10100100

The optimal solution is $\{z_1, z_3, z_6\}$ with size 3, where $z_i$ represents the $i$-th set in our original list.

Verify solutions are valid:

all(c->is_set_packing(problem.problem, c), max_configs)

true

Note: For finding just one maximum set packing, use the SingleConfigMax property

More APIs

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

This page was generated using Literate.jl.