Problems zoo

AbstractProblem

The abstract base type of computational problems.

Required interfaces

• num_variables, the number of variables in the computational problem.
• num_flavors, the number of flavors (domain) of a degree of freedom.
• solution_size, the size (the lower the better) of the input configuration.
• problem_size, the size of the computational problem. e.g. for a graph, it could be (n_vertices=?, n_edges=?).
• energy_mode, the definition of the energy function, which can be LargerSizeIsBetter or SmallerSizeIsBetter.

Derived interfaces

• variables, the degrees of freedoms in the computational problem.
• flavors, the flavors (domain) of a degree of freedom.
• findbest, find the best configurations of the input problem.

AbstractSatisfiabilityProblem{S, T} <: ConstraintSatisfactionProblem{T}

The abstract type for Satisfiability and KSatisfiability.

struct BicliqueCover{Int64} <: ConstraintSatisfactionProblem{Int64}

BicliqueCover{K}(graph::SimpleGraph{Int64}, k::Int64,weights::WT)

The Biclique Cover problem is defined on a bipartite simple graph. Given a bipartite graph, the goal is to find a set of bicliques that cover all the edges in the graph. A biclique is a complete bipartite subgraph, denoted by G = (U ∪ V, E), where U and V are the two disjoint sets of vertices, and all pairs of vertices from U and V are connected by an edge, i.e., (u, v) ∈ E for all u ∈ U and v ∈ V. What's more, each bipartite simple graph could be identified by an adjacent matrix, where the rows and columns are the vertices in U and V, respectively.

struct BinaryMatrixFactorization <: AbstractProblem

BinaryMatrixFactorization{K}(A::AbstractMatrix{Bool}, k::Int)

The Boolean Matrix Factorization (BMF) problem is defined on a binary matrix A in m x n size. Given a positive integer k, we need to determine whether we can factorize the matrix A into two binary matrices U and V such that the boolean product of U and V is equal to A, and the dimensions of U and V are (m x k) and (k x n) respectively. Refer to Recent developments in boolean matrix factorization.(Miettinen, P., & Neumann, S,2020) for details.

Required interfaces

• variables, the degrees of freedoms in the computational problem.
• flavors, the flavors (domain) of a degree of freedom.
• solution_size, the size (the lower the better) of the input configuration.
• problem_size, the size of the computational problem. e.g. for a graph, it could be (n_vertices=?, n_edges=?).

Optional interfaces

• num_variables, the number of variables in the computational problem.
• num_flavors, the number of flavors (domain) of a degree of freedom.
• findbest, find the best configurations of the input problem.

struct CircuitSAT{T, WT<:AbstractArray{T, 1}, OBJ} <: ConstraintSatisfactionProblem{T}

CircuitSAT(circuit::Circuit; use_constraints::Bool=false)

Circuit satisfiability problem, where the goal is to find an assignment that satisfies the circuit. The objective is to maximize the number of satisfied assignments if use_constraints is false, otherwise, the objective is to find one assignments that can satisfy the circuit.

Fields

• circuit::Circuit: The circuit expression in simplified form.
• symbols::Vector{Symbol}: The variables in the circuit.
• weights::AbstractVector: The weights of the assignments. The solution size is the weighted sum of the number of satisfied assignments.

Example

A circuit can be defined with the @circuit macro as follows:

julia> using ProblemReductions

julia> circuit = @circuit begin
           c = x ∧ y
           d = x ∨ (c ∧ ¬z)
       end
Circuit:
| c = ∧(x, y)
| d = ∨(x, ∧(c, ¬(z)))

julia> sat = CircuitSAT(circuit)
CircuitSAT{Int64, UnitWeight, ProblemReductions.EXTREMA}:
| c = ∧(x, y)
| ##var#236 = ¬(z)
| ##var#235 = ∧(c, ##var#236)
| d = ∨(x, ##var#235)
Symbols: [:c, :x, :y, Symbol("##var#236"), :z, Symbol("##var#235"), :d]

julia> sat.symbols
7-element Vector{Symbol}:
 :c
 :x
 :y
 Symbol("##var#354")
 :z
 Symbol("##var#353")
 :d

julia> flavors(sat)
(0, 1)

julia> solution_size(sat, [true, false, true, true, false, false, true])
SolutionSize{Int64}(1, true)

julia> findbest(sat, BruteForce())
8-element Vector{Vector{Int64}}:
 [0, 0, 0, 1, 0, 0, 0]
 [0, 0, 1, 1, 0, 0, 0]
 [0, 0, 0, 0, 1, 0, 0]
 [0, 0, 1, 0, 1, 0, 0]
 [0, 1, 0, 1, 0, 0, 1]
 [0, 1, 0, 0, 1, 0, 1]
 [1, 1, 1, 0, 1, 0, 1]
 [1, 1, 1, 1, 0, 1, 1]

struct Coloring{K, T, WT<:AbstractArray{T, 1}, OBJ} <: ConstraintSatisfactionProblem{T}

Coloring{K}(graph; weights=UnitWeight(nv(graph)), use_constraints::Bool=false)

The Vertex Coloring (Coloring) problem is defined on a simple graph. Given k kinds of colors, we need to determine whether we can color all vertices on the graph such that no two adjacent vertices share the same color.

Fields

• graph is the problem graph.
• weights are associated with the edges of the graph, default to UnitWeight(ne(graph)).

Example

To initialize a Coloring problem, we need to first define a graph and decide the number of colors.

julia> using ProblemReductions, Graphs

julia> g = smallgraph(:petersen) # define a simple graph, petersen as example
{10, 15} undirected simple Int64 graph

julia> coloring = Coloring{3}(g)  # 3 colors
Coloring{3, Int64, UnitWeight, ProblemReductions.EXTREMA}(SimpleGraph{Int64}(15, [[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [1, 4, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8]]), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

julia> variables(coloring)
1:10

julia> flavors(coloring)
(0, 1, 2)

julia> is_vertex_coloring(coloring.graph,[1,2,3,1,3,2,1,2,3,1]) #random assignment
false

ConstraintSatisfactionProblem{T} <: AbstractProblem

The abstract base type of constraint satisfaction problems. T is the type of the local size of the constraints.

Required interfaces

• constraints, the specification of the constraints. Once the constraints are violated, the size goes to infinity.
• objectives, the specification of the size terms as soft constraints, which is associated with weights.

Optional interfaces

• weights: The weights of the soft constraints.
• set_weights: Change the weights for the problem and return a new problem instance.

Derived interfaces

• is_satisfied, check if the constraints are satisfied.

struct DominatingSet{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

DominatingSet(graph::AbstractGraph, weights::AbstractVector=UnitWeight(ne(graph))) -> DominatingSet

Dominaing Set is a subset of vertices in a undirected graph such that all the vertices in the set are either in the dominating set or in its first-order neighborhood. The DominatingSet problem is to find the dominating set with minimum number of vertices.

Fields

• graph is the problem graph.
• weights::AbstractVector: Weights associated with the vertices of the graph. Defaults to UnitWeight(nv(graph)).

Example

In the following example, we define a dominating set problem on a path graph with five vertices. To define a DominatingSet problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development.

julia> using ProblemReductions, Graphs

julia> graph = path_graph(5)
{5, 4} undirected simple Int64 graph

julia> DS = DominatingSet(graph)
DominatingSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(4, [[2], [1, 3], [2, 4], [3, 5], [4]]), [1, 1, 1, 1, 1])

julia> variables(DS)  # degrees of freedom
1:5

julia> flavors(DS)  # flavors of the vertices
(0, 1)

julia> solution_size(DS, [0, 1, 0, 1, 0]) # Positive sample: (size) of a dominating set
SolutionSize{Int64}(2, true)

julia> solution_size(DS, [0, 1, 1, 0, 0]) # Negative sample: number of vertices
SolutionSize{Int64}(2, false)

julia> findbest(DS, BruteForce())  # solve the problem with brute force
3-element Vector{Vector{Int64}}:
 [1, 0, 0, 1, 0]
 [0, 1, 0, 1, 0]
 [0, 1, 0, 0, 1]

struct Factoring{T} <: AbstractProblem

Prime Factorization (Factoring) is to decompose a number $m$ into its prime factors $p$ and $q$, denoted as $m = p × q$.

Fields

• m::Int: number of bits for the first number
• n::Int: number of bits for the second number
• input::T: the number to factorize

Example

In the following example, the two 2 is the factors' bit size and 6 is the number to be factored. 6 is 110 in binary so its factors should be 2-bits number.

julia> using ProblemReductions

julia> factoring = Factoring(2,2,6)
Factoring{Int64}(2, 2, 6)

julia> variables(factoring) # return the sum of factors' bit size
1:4

julia> flavors(factoring)
(0, 1)

julia> solution_size(factoring,[0,1,1,1]) # 01 -> 2, 11 -> 3
SolutionSize{Int64}(0, true)

struct IndependentSet{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

IndependentSet(graph::AbstractGraph, weights::AbstractVector=UnitWeight(nv(graph))) -> IndependentSet

Independent Set is a subset of vertices in a undirected graph such that all the vertices in the set are not connected by edges (or called not adjacent). The maximum IndependentSet problem is to find the independent set with maximum number of vertices, which is a NP-complete problem. Let $G=(V, E)$ be a graph, and $w_v$ be the weight of vertex $v$. The energy based model of the independent set problem is:

\[H(G, \mathbf{n}) = - \sum_{v \in V} w_v n_v + \sum_{(u, v) \in E} n_u n_v\]

where $n_v$ is the number of vertices in the independent set, i.e. $n_v = 1$ if $v$ is in the independent set, and $n_v = 0$ otherwise. The larger the size of the independent set, the lower the energy.

Fields

• graph::AbstractGraph: The problem graph.
• weights::AbstractVector: Weights associated with the vertices of the graph. Defaults to UnitWeight(nv(graph)).

Example

In the following example, we define an independent set problem on a graph with four vertices. To define an IndependentSet problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights.

julia> using ProblemReductions, Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3)]))
{4, 4} undirected simple Int64 graph

julia> IS = IndependentSet(graph)
IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 1, 1, 1])

julia> num_variables(IS)  # degrees of freedom
4

julia> flavors(IS)  # flavors of the vertices
(0, 1)

julia> solution_size(IS, [1, 0, 0, 1]) # Positive sample: -(size) of an independent set
SolutionSize{Int64}(2, true)

julia> solution_size(IS, [0, 1, 1, 0]) # Negative sample: 0
SolutionSize{Int64}(2, false)

julia> findbest(IS, BruteForce())  # solve the problem with brute force
2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]

struct KSatisfiability{K, S, T, WT<:(AbstractArray{T}), OBJ} <: AbstractSatisfiabilityProblem{S, T, OBJ}

KSatisfiability{K}(cnf::CNF{S}, weights::WT=UnitWeight(length(cnf.clauses)); allow_less::Bool=false, use_constraints::Bool=false)

The satisfiability problem for k-SAT. The goal is to find an assignment that maximizes the number of satisfied clauses if use_constraints is false, otherwise, the goal is to find one assignment that can satisfy the CNF.

Fields

• symbols::Vector{T}: The symbols in the CNF.
• cnf::CNF{T}: The CNF expression.
• weights: the weights associated with clauses.
• allow_less::Bool: whether to allow less than k literals in a clause.

struct Matching{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

The Vertex matching problem.

Positional arguments

• graph is the problem graph.
• weights are associated with the edges of the graph.

struct MaxCut{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

Max Cut problem is defined on weighted graphs. The goal is to find a partition of the vertices into two sets such that the sum of the weights of the edges between the two sets is maximized.

Positional arguments

• graph is the problem graph.
• weights are associated with the edges of the graph. We have ensure that the weights are in the same order as the edges in edges(graph).

Example

In the following example, we solve a Max Cut problem on a complete graph with 3 vertices and edge weights [1,2,3].

julia> using ProblemReductions, Graphs

julia> g = complete_graph(3)
{3, 3} undirected simple Int64 graph

julia> maxcut = MaxCut(g,[1,2,3]) # specify the weights of the edges
MaxCut{Int64, Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [1, 2, 3])

julia> mc = set_weights(maxcut, [2,1,3]) # set the weights and get a new instance
MaxCut{Int64, Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [2, 1, 3])


julia> num_variables(maxcut) # return the number of vertices
3

julia> flavors(maxcut) # return the flavors of the vertices
(0, 1)

julia> solution_size(maxcut, [0,1,0]) # return the size of the configuration
SolutionSize{Int64}(4, true)

julia> findbest(maxcut, BruteForce()) # find the best configuration
2-element Vector{Vector{Int64}}:
 [1, 1, 0]
 [0, 0, 1]

struct MaximalIS{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

Maximal independent set is a problem that very similar to the IndependentSet problem. The difference is that the solution space of a maximal indepdent set problem does not include the independent sets that can be extended by adding one more vertex.

Fields

• graph is the problem graph.
• weights are associated with the vertices of the graph.

Example

In the following example, we define a maximal independent set problem on a graph with four vertices. To define a MaximalIS problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development.

julia> using ProblemReductions, Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3), (1, 4)]))
{4, 5} undirected simple Int64 graph

julia> problem = MaximalIS(graph)
MaximalIS{Int64, UnitWeight}(SimpleGraph{Int64}(5, [[2, 3, 4], [1, 3], [1, 2, 4], [1, 3]]), [1, 1, 1, 1])

julia> num_variables(problem)  # degrees of freedom
4

julia> flavors(problem)
(0, 1)

julia> solution_size(problem, [0, 1, 0, 0])  # unlike the independent set, this configuration is not a valid solution
SolutionSize{Int64}(1, false)

julia> findbest(problem, BruteForce())
1-element Vector{Vector{Int64}}:
 [0, 1, 0, 1]

struct PaintShop{LT} <: ConstraintSatisfactionProblem{Int64}

The binary paint shop problem is defined as follows: we are given a $2m$ length sequence containing $m$ cars, where each car appears twice. Each car need to be colored red in one occurrence, and blue in the other. We need to choose which occurrence for each car to color with which color — the goal is to minimize the number of times we need to change the current color.

Fields

• sequence is a vector of symbols, each symbol is associated with a color.
• isfirst is a vector of boolean numbers, indicating whether the symbol is the first appearance in the sequence.

Example

In the following example, we define a paint shop problem with 6 cars.

julia> using ProblemReductions

julia> problem = PaintShop(["a","b","a","c","c","b"])
PaintShop{String}(["a", "b", "a", "c", "c", "b"], Bool[1, 1, 0, 1, 0, 0])

julia> num_variables(problem)
3

julia> flavors(problem)
(0, 1)

julia> solution_size(problem, [0, 1, 0])
SolutionSize{Int64}(4, true)

julia> findbest(problem, BruteForce())
2-element Vector{Vector{Int64}}:
 [1, 0, 0]
 [0, 1, 1]

struct QUBO{T<:Real} <: ConstraintSatisfactionProblem{T<:Real}

The quadratic unconstrained binary optimization.

\[E = \sum_{i,j} Q_{ij} x_i x_j\]

where $x_i \in \{0, 1\}$.

Arguments

• matrix::AbstractMatrix: the matrix Q of the QUBO problem.

julia> using ProblemReductions, Graphs
       # Matrix method

julia> Q = [1. 0 0; 0 1 0; 0 0 1]
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

julia> QUBO01 = QUBO(Q)
       # Graph method
QUBO{Float64}([1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])

julia> graph = SimpleGraph(3)
{3, 0} undirected simple Int64 graph

julia> QUBO02 = QUBO(graph, Float64[], [1., 1., 1.])
QUBO{Float64}([1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])

julia> num_variables(QUBO01)  # degrees of freedom
3

julia> flavors(QUBO01)  # flavors of the vertices
(0, 1)

julia> solution_size(QUBO01, [0, 1, 0])
SolutionSize{Float64}(1.0, true)

julia> solution_size(QUBO02, [0, 1, 0])
SolutionSize{Float64}(1.0, true)

julia> findbest(QUBO01, BruteForce())  # solve the problem with brute force
1-element Vector{Vector{Int64}}:
 [0, 0, 0]

julia> findbest(QUBO02, BruteForce())
1-element Vector{Vector{Int64}}:
 [0, 0, 0]

struct Satisfiability{S, T, WT<:(AbstractArray{T}), OBJ} <: AbstractSatisfiabilityProblem{S, T, OBJ}

Satisfiability(cnf::CNF{S}, weights::AbstractVector=UnitWeight(length(cnf.clauses)); use_constraints::Bool=false) where {S}

Satisfiability (also called SAT) problem is to find the boolean assignment that satisfies a Conjunctive Normal Form (CNF). A tipical CNF would look like:

\[\left(l_{11} \vee \ldots \vee l_{1 n_1}\right) \wedge \ldots \wedge\left(l_{m 1} \vee \ldots \vee l_{m n_m}\right)\]

where literals are joint by $\vee$ to for $m$ clauses and clauses are joint by $\wedge$ to form a CNF. The satisfiability problem is to find the assignment that maximizes the number of satisfied clauses if use_constraints is false, otherwise, the goal is to find one assignment that can satisfy the CNF.

We should note that all the SAT problem problem can be reduced to the 3-SAT problem and it can be proved that 3-SAT is NP-complete.

Fields

• cnf is a conjunctive normal form (CNF) for specifying the satisfiability problems.
• weights are associated with clauses. The solution size is the weighted sum of the number of satisfied assignments.

Example

In the following example, we define a satisfiability problem with two clauses.

julia> using ProblemReductions

julia> bv1, bv2, bv3 = BoolVar.(["x", "y", "z"])
3-element Vector{BoolVar{String}}:
 x
 y
 z

julia> clause1 = CNFClause([bv1, bv2, bv3])
x ∨ y ∨ z

julia> clause2 = CNFClause([BoolVar("w"), bv1, BoolVar("x", true)])
w ∨ x ∨ ¬x

julia> cnf_test = CNF([clause1, clause2])
(x ∨ y ∨ z) ∧ (w ∨ x ∨ ¬x)

julia> sat_test = Satisfiability(cnf_test)
Satisfiability{String, Int64, UnitWeight, ProblemReductions.EXTREMA}(["x", "y", "z", "w"], [1, 1], (x ∨ y ∨ z) ∧ (w ∨ x ∨ ¬x))

struct SetCovering{ET, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

The Set Covering problem is defined as follow: given a universe of elements and a collection of subsets of the universe, each set is associated with a weight. The goal is to find a subset of sets that covers all the elements with the minimum total weight.

Positional arguments

• elements is a vector of elements in the universe.
• sets is a vector of vectors, a collection of subsets of universe , each set is associated with a weight specified in weights.
• weights are associated with sets.

Example

In the following example, we solve a Set Covering problem with 3 subsets and weights [1,2,3].

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, Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])

julia> num_variables(setcovering)  # degrees of freedom
3

julia> solution_size(setcovering, [1, 0, 1])  # size of a configuration
SolutionSize{Int64}(4, true)

julia> solution_size(setcovering, [0, 1, 1])
SolutionSize{Int64}(5, false)

julia> sc = set_weights(setcovering, [1, 2, 3])  # set the weights of the subsets
SetCovering{Int64, Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])

struct SetPacking{ET, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

SetPacking(elements::AbstractVector, sets::AbstractVector, weights::AbstractVector=UnitWeight(length(sets))) -> SetPacking

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

Fields

• elements is a vector of elements in the universe.
• sets is a vector of vectors, each set is associated with a weight specified in weights.
• weights are associated with sets. Defaults to UnitWeight(length(sets)).

Example

In the following example, we define a set packing problem with five subsets. 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, 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])

julia> num_variables(SP)  # degrees of freedom
5

julia> flavors(SP)  # flavors of the subsets
(0, 1)

julia> solution_size(SP, [1, 0, 0, 1, 0]) # Positive sample: -(size) of a packing
SolutionSize{Int64}(2, true)

julia> solution_size(SP, [1, 0, 1, 1, 0]) # Negative sample: 0
SolutionSize{Int64}(3, false)

julia> findbest(SP, BruteForce())  # solve the problem with brute force
3-element Vector{Vector{Int64}}:
 [0, 1, 1, 0, 0]
 [1, 0, 0, 1, 0]
 [0, 0, 1, 1, 0]

struct SpinGlass{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

SpinGlass(graph::AbstractGraph, weights::AbstractVector)
SpinGlass(graph::SimpleGraph, J, h=zeros(nv(graph)))

Spin Glass is a type of disordered magnetic system that exhibits a glassy behavior. The Hamiltonian of the system on a simple graph $G=(V, E)$ is given by

\[H(G, \sigma) = \sum_{(i,j) \in E} J_{ij} \sigma_i \sigma_j + \sum_{i \in V} h_i \sigma_i\]

where $J_{ij} \in \mathbb{R}$ is the coupling strength between spins $i$ and $j$, $h_i \in \mathbb{R}$ is the external field on spin $i$, and $\sigma_i \in \{-1, 1\}$ is the spin variable. The configuration of a solution is specified by a binary variable in (0, 1), where 0 and 1 are mapped to spins -1 and 1, respectively.

This definition naturally extends to the case of a HyperGraph:

\[H(G, \sigma) = \sum_{e \in E} J_{e} \prod_k\sigma_k + \sum_{i \in V} h_i \sigma_i,\]

where $J_e$ is the coupling strength associated with hyperedge $e$, and the product is over all spins in the hyperedge.

Fields

• graph is a graph object.
• J are the coupling strengths associated with the edges.
• h are the external fields associated with the vertices.

Example

In the following example, we define a spin glass problem on a 4-vertex graph with given coupling strengths on edges and external fields on vertices.

julia> using ProblemReductions, ProblemReductions.Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3)]))
{4, 4} undirected simple Int64 graph

julia> J = [1, -1, 1, -1]  # coupling strength
4-element Vector{Int64}:
  1
 -1
  1
 -1

julia> h = [1, -1, -1, 1]  # external field
4-element Vector{Int64}:
  1
 -1
 -1
  1

julia> spinglass = SpinGlass(graph, J, h)  # Define a spin glass problem
SpinGlass{SimpleGraph{Int64}, Int64, Vector{Int64}}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, -1, 1, -1], [1, -1, -1, 1])

julia> num_variables(spinglass)  # degrees of freedom
4

julia> flavors(spinglass)  # flavors of the spins, 0 for up (+1), 1 for down (-1)
(0, 1)

julia> solution_size(spinglass, [1, 0, 0, 1])  # size of a configuration
SolutionSize{Int64}(-2, true)

julia> findbest(spinglass, BruteForce())  # solve the problem with brute force
1-element Vector{Vector{Int64}}:
 [1, 0, 1, 1]

struct VertexCovering{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

A Vertex Cover is a subset of vertices in a graph, such that for an arbitrary edge, the subset includes at least one of the endpoints. The minimum vertex covering problem is to find the minimum vertex cover for a given graph, which is a NP-complete problem.

Fields

• graph is a graph object.
• weights are associated with the vertices of the graph, default to UnitWeight(nv(graph)).

Example

In the following example, we define a vertex covering problem on a graph with four vertices. To define a VertexCovering problem, we need to specify the graph and the weights associated with edges. The weights are by default set as unit.

julia> using ProblemReductions, Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1,2), (1,3), (3,4), (2,3), (1,4)]))
{4, 5} undirected simple Int64 graph

julia> weights = [1, 3, 1, 4]
4-element Vector{Int64}:
 1
 3
 1
 4

julia> VC= VertexCovering(graph, weights)
VertexCovering{Int64, Vector{Int64}}(SimpleGraph{Int64}(5, [[2, 3, 4], [1, 3], [1, 2, 4], [1, 3]]), [1, 3, 1, 4])

julia> num_variables(VC)  # degrees of freedom
4

julia> solution_size(VC, [1, 0, 0, 1]) # Negative sample
SolutionSize{Int64}(5, false)

julia> solution_size(VC, [0, 1, 1, 0]) # Positive sample
SolutionSize{Int64}(4, false)

julia> findbest(VC, BruteForce())  # solve the problem with brute force
1-element Vector{Vector{Int64}}:
 [1, 0, 1, 0]

julia> VC02 = set_weights(VC, [1, 2, 3, 4])  # set the weights of the subsets
VertexCovering{Int64, Vector{Int64}}(SimpleGraph{Int64}(5, [[2, 3, 4], [1, 3], [1, 2, 4], [1, 3]]), [1, 2, 3, 4])