SeaPearl Internals

Statistics Contains statistics used in the search process:

• infeasibleStatusPerVariable::Dict{String,Int} : maps variable id to the number of infeasible solutions the variable was involved in
• numberOfNodes::Int : number of nodes in the search
• numberOfSolutions::Int : number of solutions found
• numberOfInfeasibleSolutions::Int : number of infeasible solutions found
• numberOfSolutionsBeforeRestart::Int : number of solutions found before the search restart
• numberOfInfeasibleSolutionsBeforeRestart::Int : number of infeasible solutions found before the search restart
• numberOfNodesBeforeRestart::Int : number of nodes in the search tree before the search restart
• AccumulatedRewardBeforeReset::Float32 : reward accumulated before the search reset
• AccumulatedRewardBeforeRestart::Float32 : reward accumulated before the search restart
• solutions::Vector{Union{Nothing,Solution}} : solutions found
• nodevisitedpersolution::Vector{Int} : number of times nodes that were visited in solutions
• objectives::Union{Nothing,Vector{Union{Nothing,Int}}}
• lastPruning::Union{Nothing,Int}
• objectiveDownPruning::Union{Nothing,Float32}
• objectiveUpPruning::Union{Nothing,Float32}
• lastVar::Union{Nothing,AbstractIntVar} : Last variable that the search branched on
• numberOfTimesInvolvedInPropagation::Union{Nothing,Dict{Constraint,Int}} : number of times every constraint was involved in a propagation

Limit(numberOfNodes::Union{Int, Nothing}, numberOfSolutions::Union{Int, Nothing}, searchingTime::Union{Int, Nothing}, searchingMemory::Union{Int, Nothing}) Limits for the search process.

CPModel(trailer::Trailer)
CPModel()

The structure storing all the information needed when solving a given problem, as well as the solutions that were found. The CPModel is at the core of the solving process and evolves over its course. Note: The AbstractStateRepresentation used by the RL Agent is created from the CPModel.

The CPModel is always created empty and is filled eather by hand by the user (or automatically thanks to written files) or filled by an AbstractModelGenerator.

The CPModel struct has the following attributes: - variables::Dict{String,AbstractVar} : dict mapping variable id to variables - branchable::Dict{String,Bool} : dict mapping variable id to a bool indicating whether or not the variables are branchable - branchable_variables::Dict{String, AbstractVar} : dict where the keys are the variable id's of ONLY the branchable variables. Maps variable id's to variables - constraints::Array{Constraint} : Array of all the model's constraints - trailer::Trailer : trailer used for the search and solving - objective::Union{Nothing,AbstractIntVar} : objective function of the model - objectiveBound::Union{Nothing,Int} - statistics::Statistics : statistics, described in details - limit::Limit : model's limits - knownObjective::Union{Nothing,Int64} : optional; contains the known objective of the model. For example, if the goal is to minimize the number of delays, it could be set to 0. - adhocInfo::Any : Any ad-hoc information related to the CPModel - displayXCSP3::Bool : Display XCSP3 requirements during solving - maximizeObjective::Bool : maximize objective variable (useful to display the right objective value)

addVariable!(model::CPModel, x::AbstractVar; branchable=true)

Add a variable to the model, throwing an error if x's id is already in the model. The branchable argument allows you to tell if we will be able to branch on that variable.

addObjective!(model::CPModel, objective::AbstractVar)

Add an Objective variable to the model. This variable is the variable that needs to be minimized suring the solving.

addKnownObjective!(model::CPModel, knownObective::Int64)

Add a known Objective to the model.

addConstraint!(model::CPModel, constraint::Constraint)

Add a constraint to the CPModel.

function is_branchable(model::CPModel, x::AbstractVar)

Tell if the variable was set as branchable or not.

function branchable_variables(model::CPModel)

Return a dict of all branchable variables, mapping from variable id to variable.

solutionFound(model::CPModel)

Return a boolean, checking whether a solution was found, i.e. every variable is bound.

triggerFoundSolution!(model::CPModel)

Add the current solution to model, and set new constraints for the objective if needed.

triggerInfeasible!(constraint::Constraint, model::CPModel)

This function increments by one the statistic infeasibleStatusPerVariable for each variable involved in the constraint. infeasibleStatusPerVariable keeps track for each variable the number of times the variable was involved in a constraint that led to an infeasible state during a fixpoint. This statistic is used by the failure-based variable selection heuristic.

tightenObjective!(model::CPModel)

Set a new constraint to minimize the objective variable.

isempty(dom::IntDomain)

Return true iff dom is an empty set. Done in constant time.

isempty(dom::BoolDomain)

Return true iff dom is an empty set. Done in constant time.

isempty(dom::IntDomainView)

Return true iff dom is an empty set.

isempty(dom::BoolDomainView)

Return true iff dom is an empty set.

Base.isempty(model::CPModel)::Bool

Return a boolean describing if the model is empty or not.

Base.empty!(model::CPModel)

Empty the CPModel.

reset_model!(model::CPModel)

Reset a given CPModel instance. Make it possible to reuse the same instance instead of having to delete the old one and create another one. This is used in launch_experiment! in order to be able to use the same CPModel instance to compare different given heuristics.

restart_search!(model::CPModel)

Restarts the search process. Useful when dealing with restart based search : ILDS or RBS. Resets to zero are useful statistics on the search that can be used to define the restart criteria.

domains_cartesian_product(model::CPModel)

Return the cartesian product of the model variables: |D1|x|D2|x ... x|Dn| Helps providing insights about what is happening during a search.

nb_boundvariables(model::CPModel)

Return the number of variables that have already been assigned to a value (that are bound). Helps providing insights about what is happening during a search.

global_domain_cardinality(model::CPModel)

Returns the sum of the cardinalities of all the variable domains.

updateStatistics!(model::CPModel, pruned)

Called in DFS to update the appropriate statistics used in GeneralReward

search!(model::CPModel, strategy::S, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection=BasicHeuristic(); out_solver::Bool=false) where S <: SearchStrategy Perform a search following a specific strategy in the model using variableHeuristic to choose which domain will be changed at each branching and using valueSelection to choose how the branching will be done.

initroot!(toCall::Stack{Function}, ::DFSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)

Used as a generic function to instantiate the research based on a specific Strategy <: SearchStrategy.

initroot!(toCall::Stack{Function}, ::DFWBSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)

Used as a generic function to instantiate the research based on a specific Strategy <: SearchStrategy.

initroot!(toCall::Stack{Function}, ::ILDSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)

generic function to instantiate the research based on a specific Strategy <: SearchStrategy. The max discrepancy correspond to the number of branchable variables at the beginning of the search. Calls to expandIlds! with a decreasing discrepancy is stacked in the toCall Stack.

initroot!(toCall::Stack{Function}, strategy::S, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection) where {S <: RBSearch}

It fills the toCall Stack in a certains order based on a specific Strategy <: RBSearch with function that expand the search tree. In restart based strategy, we fill the Stack with calls to expandRbs with different nodeLimit. The nodeLimit corresponds to the number of infeasiblesolution that can be reached before restarting the search a the top of the tree with a possibly different nodeLimit. This search strategy requires the use of a stochastic variable/value heuristic, otherwise, at each restart the search will end-up on the exact previous solutions.

initroot!(toCall::Stack{Function}, search::LNSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)

Used as a generic function to instantiate the research based on a specific Strategy <: SearchStrategy.

# Arguments

• toCall: In this search strategy, toCall is not used (an empty stack will be returned)
• search: Object containing the parameters of the search strategy
• model: CPModel to be solved
• variableHeuristic: Variable selection method to be used in the search
• valueSelection: Value selection method to be used in the search

initroot!(toCall::Stack{Function}, ::F, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection) where F <: SearchStrategy

Initialisation function that fill the toCall Stack according to a certain strategy.

expandDfs!(toCall::Stack{Function}, model::CPModel, variableHeuristic::Function, valueSelection::ValueSelection, newConstraints=nothing)

Add procedures to toCall, that, called in the stack order (LIFO) with the model parameter, will perform a DFS in the graph. Some procedures will contain a call to expandDfs! itself. Each expandDfs! call is wrapped around a saveState! and a restoreState! to be able to backtrack thanks to the trailer.

expandDfwbs!(toCall::Stack{Function}, model::CPModel, variableHeuristic::Function, valueSelection::ValueSelection, newConstraints=nothing)

Expands the DFWBS search tree.

expandIlds!(toCall::Stack{Function}, discrepancy::Int64, previousdepth::Int64, direction::Union{Nothing, Symbol} , model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection, newConstraints=nothing)

This function fills the toCall Stack (LIFO) and perform a recursive Limited Discrepancy Search. Some procedures will contain a call to expandIlds! itself. Each expandIlds! call is wrapped around a saveState! and a restoreState! to be able to backtrack thanks to the trailer.

This implementation is based on this paper : Limited Discrepancy Search - 1995 - William D. Harvey and Matthew L. Ginsberg. This method is not efficiant compared to the Korf approach but doesn't need any given max depth of the search tree, which is unknown for CP search tree. We should maybe look at this : https://www.researchgate.net/publication/220639800Limiteddiscrepancysearchrevisited

expandLns!(search::LNSearch, model::CPModel, variableHeuristic::AbstractVariableSelection, valueSelection::ValueSelection)

This function make a Large Neighbourhood Search. As initial solution we use the first feasible solution found by a DFS. Then a destroy and repair loop tries to upgrade the current solution until some stop critiria.

# Arguments

• search: Object containing the parameters of the search strategy
• model: CPModel to be solved
• variableHeuristic: Variable selection method to be used in the search
• valueSelection: Value selection method to be used in the search

expandRbs!(toCall::Stack{Function}, model::CPModel, variableHeuristic::Function, valueSelection::ValueSelection, newConstraints=nothing)

Add procedures to toCall, that, called in the stack order (LIFO) with the model parameter, will perform a RBS in the graph. Some procedures will contain a call to expandRbs! itself. Each expandRbs! call is wrapped around a saveState! and a restoreState! to be able to backtrack thanks to the trailer.

The Search stops as long as the search reached the limit on a given criteria. .