Tutorial

Understanding Constraint Satisfaction Problems in ProblemReductions

This tutorial explains how to work with constraint satisfaction problems using the ProblemReductions package in Julia.

Basic Setup

First, let's import the required packages and create a simple problem:

julia> using ProblemReductions, Graphs
julia> problem = IndependentSet(smallgraph(:diamond))IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(5, [[2, 3], [1, 3, 4], [1, 2, 4], [2, 3]]), [1, 1, 1, 1])

This creates an Independent Set problem based on a diamond-shaped graph.

Problem Properties

You can query various properties of the problem:

1. Basic properties

julia> num_variables(problem)  # number of variables4
julia> num_flavors(problem)  # number of flavors of each variable2
julia> problem_size(problem)  # size of the problem(num_vertices = 4, num_edges = 5)

2. Weights (for weighted problems)

julia> ProblemReductions.weights(problem)  # weights of the problem4-element UnitWeight:
 1
 1
 1
 1
julia> ProblemReductions.set_weights(problem, [1, 2, 2, -1, -1, -2])  # set the weights of the problemIndependentSet{SimpleGraph{Int64}, Int64, Vector{Int64}}(SimpleGraph{Int64}(5, [[2, 3], [1, 3, 4], [1, 2, 4], [2, 3]]), [1, 2, 2, -1, -1, -2])

3. Objectives and Constraints

julia> ProblemReductions.objectives(problem)   # View the objective functions4-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   │
└───────────────┴──────┘
julia> ProblemReductions.constraints(problem)  # View the constraints5-element Vector{ProblemReductions.LocalConstraint}:
 LocalConstraint on [1, 2]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘

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

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

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

 LocalConstraint on [3, 4]
┌───────────────┬───────┐
│ Configuration │ Valid │
├───────────────┼───────┤
│    [0, 0]     │ true  │
│    [1, 0]     │ true  │
│    [0, 1]     │ true  │
│    [1, 1]     │ false │
└───────────────┴───────┘
julia> ProblemReductions.energy_mode(problem)  # View the energy mode of the problemLargerSizeIsBetter()

Remarks

All ConstraintSatisfactionProblems use objectives and constraints to define the problem.
The constraints returns a vector of local constraints. Each local constraint is a boolean function of the variables. true means the constraint is satisfied by the current assignment to local variables.
The energy is defined as -solution_size if energy_mode(problem) == LargerSizeIsBetter() and solution_size if energy_mode(problem) == SmallerSizeIsBetter(). The energy is infinity if the solution is invalid.

Working with Solutions

You can evaluate different solutions (configurations) using these methods:

1. Single Solution Evaluation

julia> solution_size(problem, [1, 0, 1, 0])  # Calculate solution sizeSolutionSize{Int64}(2, false)
julia> energy(problem, [1, 0, 1, 0])         # Calculate energy3037000500

The solution size is defined as the sum of the sizes of the variables. It returns a SolutionSize object, which has two fields:

size: the size of the solution
is_valid: whether the solution satisfies the constraints

2. Multiple Solutions Evaluation (faster than multiple single evaluations)

julia> solution_size_multiple(problem, [[1, 0, 0, 0], [0, 1, 0, 1]]) # Evaluate multiple configurations2-element Vector{SolutionSize{Int64}}:
 SolutionSize{Int64}(1, true)
 SolutionSize{Int64}(2, false)

3. Finding the Optimal Solution

julia> ProblemReductions.findbest(problem, BruteForce()) # Find the best configuration using brute force1-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]

Remarks

Configuration Format: Solutions are represented as vectors of integers in the range of 0:num_flavors(problem)-1, where each element represents a variable's state.
Optimization: The findbest method allows you to find optimal solutions using different algorithms (like BruteForce in this example). Alternatively, you can use the GTNSolver in the GenericTensorNetworks package to find optimal solutions using tensor network methods.

This API provides a comprehensive toolkit for defining, manipulating, and solving constraint satisfaction problems in Julia.