Set Covering

Problem Definition

The SetCovering problem is a combinatorial optimization problem that arises in many practical applications. It's in the class of NP-Complete and heuristic or approximation algorithms are often used to find solutions.

Interfaces

Initialize a SetCovering instance needs to specify the subsets and the weights of the subsets.

julia> using ProblemReductions
julia> subsets = [[1, 2, 3], [2, 4], [1, 4]]3-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [2, 4]
 [1, 4]
julia> weights = [1, 2, 3]3-element Vector{Int64}:
 1
 2
 3
julia> setcovering = SetCovering(subsets, weights)SetCovering{Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])

Use 2-dimensional vector to represent the subsets.

The required functions, variables, evaluate, and optional functions:set_parameters are implemented for the set covering problem.

julia> variables(setcovering)  # degrees of freedom3-element Vector{Int64}:
 1
 2
 3
julia> evaluate(setcovering, [1, 0, 1])  # cost of a configuration4
julia> evaluate(setcovering, [0, 1, 1])9223372036854775807
julia> sc = set_parameters(setcovering, [1, 2, 3])  # set the weights of the subsetsSetCovering{Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])