GitHub

DAG API

The DAG (Directed Acyclic Graph) API provides the core constraint and objective modeling functionality.

DAG Construction

JuLS.DAG — Type
struct DAG <: MoveEvaluator

Core data structure representing an optimization problem as a Directed Acyclic Graph (DAG). An invariant represents an intermediate relationship between variables. We represent these relationships as a Directed Acyclic Graph (DAG). This representation allows for cheap evaluations of local moves.

Fields

  • _invariants::Vector{Invariant}: Problem invariants (nodes of the DAG)
  • _names::Vector{Union{Nothing,String}}: Optional names for invariants
  • _using_cp::BitVector: Flags for constraint programming usage per invariant
  • _adjacency_matrix::AdjacencyMatrix: Graph structure representation
  • _var_to_first_invariants::Vector{Int}: Maps variables to their first dependent invariants
  • _early_stop_threshold::Float64: Threshold for early termination of move evaluation
  • _helper::AbstractDAGHelper: Problem-specific helper object
  • _is_init::Bool: Initialization status flag
source

Invariants

Invariants are the building blocks of the DAG that represent constraints and computations.

Arithmetic Invariants

Comparison Invariants

JuLS.ComparatorInvariant — Type
ComparatorInvariant <: SummableDeltaInvariant

Invariant that compares a sum of values against a capacity threshold, typically used in constrained optimization problems. y = max(0, ∑ x - C)

Fields

  • current_value::Float64: Current accumulated sum
  • original_capacity::Float64: Threshold value for comparison
source

Boolean Invariants

JuLS.AndInvariant — Type
AndInvariant <: Invariant

Represents an invariant for the logical AND constraint. y = x1 ∩ x2 ∩ ... ∩ x_n

Fields

  • nb_false::Int: Number of variables currently false.
source
JuLS.OrInvariant — Type
OrInvariant <: Invariant

Represents an invariant for the logical OR constraint. y = x1 ∪ x2 ∪ ... ∪ x_n

Fields

  • nb_trues::Int: Number of variables currently true.
source

Specialized Invariants

JuLS.AllDifferentInvariant — Type
struct AllDifferentInvariant <: Invariant

An invariant that enforces all variables to have different values.

Description

Represents the constraint x₁ ≠ x₂ ≠ ... ≠ xₙ where each variable xᵢ takes values in the domain D = {1,...,n}.

Violation Measure

The violation is calculated as: y = ∑ max(0, c(i) - 1) where c(i) is the count of variables taking value i.

Fields

  • current_value_counter::Vector{Int}: Counts occurrences of each value in the current assignment

Constructor

AllDifferentInvariant(n_variables::Int)

Creates an AllDifferentInvariant for n_variables variables, initializing the counter to zeros.

source
JuLS.AmongInvariant — Type
AmongInvariant <: StatelessInvariant

This invariant represents the constraint Among(X, S, n) which enforces y = |{x ∈ X : x.value ∈ S}|

source
JuLS.ElementInvariant — Type
struct ElementInvariant{T} <: StatelessInvariant where {T<:DecisionValue}

Given a message with an IntDecisionValue i, the ElementInvariant returns elements[i] which is a message with a DecisionValue of type T. y = elements[x]

source

DAG Operations

Adding Invariants

# Add an invariant to the DAG
invariant_id = add_invariant!(dag, ScalarProductInvariant(weights); variable_parent_indexes = [1, 2, 3])

Message Passing

The DAG uses message passing for efficient computation:

Message Types

  • FullMessage: Complete state information
  • Delta: Incremental changes only

Example Usage

using JuLS

# Create a DAG for a simple problem
dag = DAG(3)  # 3 decision variables

# Add scalar product invariant
weights = [2.0, 3.0, 1.0]
sum_id = add_invariant!(dag, ScalarProductInvariant(weights); variable_parent_indexes = [1, 2, 3])

# Add comparator for constraint
capacity = 10.0
constraint_id = add_invariant!(dag, ComparatorInvariant(capacity); variable_parent_indexes = [1, 2, 3])

# Connect sum to constraint
connect!(dag, sum_id, constraint_id)

# Set objective
objective_weights = [5.0, 4.0, 3.0]
obj_id = add_invariant!(dag, ScalarProductInvariant(objective_weights); variable_parent_indexes= [1, 2, 3])
add_invariant!(dag, ObjectiveInvariant(); invariant_parent_indexes= [obj_id])

Performance Considerations

Memory Usage

  • DAGs store computation history for efficiency
  • Consider clearing history for long runs
  • Monitor memory usage for large problems

Computation Efficiency

  • Use appropriate invariant types
  • Minimize unnecessary connections
  • Batch updates when possible