Set Packing

Problem Definition

A packing is a set of sets where each set is pairwise disjoint from each other. The SetPacking problem is to find the maximum packing for a given union and a set of subsets.

Interfaces

To define a SetPacking problem, we need to specify the set of subsets and possibily the weights associated with these subsets. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development. Besides, the elements would be automatically counted by the construction function.

julia> using ProblemReductions
julia> sets = [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]]5-element Vector{Vector{Int64}}:
 [1, 2, 5]
 [1, 3]
 [2, 4]
 [3, 6]
 [2, 3, 6]
julia> SP = SetPacking(sets)SetPacking{Int64, UnitWeight}([1, 2, 5, 3, 4, 6], [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]], [1, 1, 1, 1, 1])

Then, the required functions, variables, flavors, and evaluate, and optional functions, findbest, are implemented for the Set Packing problem.

julia> variables(SP)  # degrees of freedom5-element Vector{Int64}:
 1
 2
 3
 4
 5
julia> flavors(SP)  # flavors of the subsets2-element Vector{Int64}:
 0
 1
julia> evaluate(SP, [1, 0, 0, 1, 0]) # Positive sample: -(size) of a packing-2
julia> evaluate(SP, [1, 0, 1, 1, 0]) # Negative sample: 00
julia> findbest(SP, BruteForce())  # solve the problem with brute force3-element Vector{Vector{Int64}}:
 [0, 1, 1, 0, 0]
 [1, 0, 0, 1, 0]
 [0, 0, 1, 1, 0]