LocalSearchSolvers.jl
Documentation for LocalSearchSolvers.jl
.
AbstractSolver
Abstract type to encapsulate the different solver types such as Solver
or _SubSolver
.
Constraint{F <: Function}
Structure to store an error function and the variables it constrains.
LeadSolver <: MetaSolver
Solver managed remotely by a MainSolver. Can manage its own set of local sub solvers.
MainSolver <: AbstractSolver
Main solver. Handle the solving of a model, and optional multithreaded and/or distributed subsolvers.
Arguments:
model::Model
: A formal description of the targeted problemstate::_State
: An internal state to store the info necessary to a solving runoptions::Options
: User options for this solversubs::Vector{_SubSolver}
: Optional subsolvers
Abstract type to encapsulate all solver types that manages other solvers.
Objective{F <: Function}
A structure to handle objectives in a solver. `struct Objective{F <: Function} name::String f::F end``
Objective(F, o::Objective{F2}) where {F2 <: Function}
Constructor used in specializing a solver. Should never be called externally.
Options()
Arguments:
dynamic::Bool
: is the model dynamic?iteration::Union{Int, Float64}
: limit on the number of iterationsprint_level::Symbol
: verbosity to choose among:silent
,:minimal
,:partial
,:verbose
solutions::Int
: number of solutions to returnspecialize::Bool
: should the types of the model be specialized or not. Usually yes for static problems. For dynamic in depends if the user intend to introduce new types. The specialized model is about 10% faster.tabu_time::Int
: DESCRIPTIONtabu_local::Int
: DESCRIPTIONtabu_delta::Float64
: DESCRIPTIONthreads::Int
: Number of threads to usetime_limit::Float64
: time limit in seconds`function Options(; dynamic = false, iteration = 10000, print_level = :minimal, solutions = 1, specialize = !dynamic, tabu_time = 0, tabu_local = 0, tabu_delta = 0.0, threads = typemax(0), time_limit = Inf)
# Setting options in JuMP syntax: print_level, time_limit, iteration
model = Model(CBLS.Optimizer)
set_optimizer_attribute(model, "iteration", 100)
set_optimizer_attribute(model, "print_level", :verbose)
set_time_limit_sec(model, 5.0)
Variable{D <: AbstractDomain}
A structure containing the necessary information for a solver's variables: name
, domain
, and constraints
it belongs.
struct Variable{D <: AbstractDomain}
domain::D
constraints::Indices{Int}
end
_Model{V <: Variable{<:AbstractDomain},C <: Constraint{<:Function},O <: Objective{<:Function}}
A struct to model a problem as a set of variables, domains, constraints, and objectives.
struct _Model{V <: Variable{<:AbstractDomain},C <: Constraint{<:Function},O <: Objective{<:Function}}
variables::Dictionary{Int,V}
constraints::Dictionary{Int,C}
objectives::Dictionary{Int,O}
# counter to add new variables: vars, cons, objs
max_vars::Ref{Int}
max_cons::Ref{Int}
max_objs::Ref{Int}
# Bool to indicate if the _Model instance has been specialized (relatively to types)
specialized::Ref{Bool}
# Symbol to indicate the kind of model for specialized methods such as pretty printing
kind::Symbol
end
GeneralState{T <: Number}
A mutable structure to store the general state of a solver. All methods applied to GeneralState
are forwarded to S <: AbstractSolver
.
mutable struct GeneralState{T <: Number} <: AbstractState
configuration::Configuration{T}
cons_costs::Dictionary{Int, Float64}
last_improvement::Int
tabu::Dictionary{Int, Int}
vars_costs::Dictionary{Int, Float64}
end
_SubSolver <: AbstractSolver
An internal solver type called by MetaSolver when multithreading is enabled.
Arguments:
id::Int
: subsolver id for debuggingmodel::Model
: a ref to the model of the main solverstate::_State
: adeepcopy
of the main solver that evolves independentlyoptions::Options
: a ref to the options of the main solver
x::Variable ∈ constraint
value ∈ x::Variable
Check if a variable x
is restricted by a constraint::Int
, or if a value
belongs to the domain of x
.
_add_to_constraint!(x::Variable, id)
Add a constraint id
to the list of constraints of x
.
_check_restart(s)
Check if a restart of s
is necessary. If s
has subsolvers, this check is independent for all of them.
_check_subs(s)
Check if any subsolver of a main solver s
, for
Satisfaction, has a solution, then return it, resume the run otherwise
Optimization, has a better solution, then assign it to its internal state
_compute!(s; o::Int = 1, cons_lst = Indices{Int}())
Compute the objective o
's value if s
is satisfied and return the current error
.
Arguments:
s
: a solvero
: targeted objectivecons_lst
: list of targeted constraints, if empty compute for the whole set
_compute_cost!(s, ind, c)
Compute the cost of constraint c
with index ind
.
_compute_costs!(s; cons_lst::Indices{Int} = Indices{Int}())
Compute the cost of constraints c
in cons_lst
. If cons_lst
is empty, compute the cost for all the constraints in s
.
_compute_objective!(s, o::Objective)
_compute_objective!(s, o = 1)
Compute the objective o
's value.
_cons_cost!(s::S, c, cost) where S <: Union{_State, AbstractSolver}
Set the cost
of constraint c
.
_cons_cost(s::S, c) where S <: Union{_State, AbstractSolver}
Return the cost of constraint c
.
_cons_costs!(s::S, costs) where S <: Union{_State, AbstractSolver}
Set the constraints costs.
_cons_costs(s::S) where S <: Union{_State, AbstractSolver}
Access the constraints costs.
_constriction(x::Variable)
Return the cosntriction
of x
, i.e. the number of constraints restricting x
.
_delete_from_constraint!(x::Variable, id)
Delete a constraint id
from the list of constraints of x
.
_find_rand_argmax(d::DictionaryView)
Compute argmax
of d
and select one element randomly.
_get_constraints(x::Variable)
Access the list of constraints
of x
.
_get_vars(c::Constraint)
Returns the variables constrained by c
.
_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}
Increment the maximum constraint id that has been attributed to m
.
_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}
Increment the maximum objective id that has been attributed to m
.
_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}
Increment the maximum variable id that has been attributed to m
.
_length(c::Constraint)
Return the number of constrained variables by c
.
_max_cons(m::M) where M <: Union{Model, AbstractSolver}
Access the maximum constraint id that has been attributed to m
.
_max_objs(m::M) where M <: Union{Model, AbstractSolver}
Access the maximum objective id that has been attributed to m
.
_max_vars(m::M) where M <: Union{Model, AbstractSolver}
Access the maximum variable id that has been attributed to m
.
_move!(s, x::Int, dim::Int = 0)
Perform an improving move in x
neighbourhood if possible.
Arguments:
s
: a solver of type S <: AbstractSolverx
: selected variable iddim
: describe the dimension of the considered neighbourhood
_neighbours(s, x, dim = 0)
DOCSTRING
Arguments:
s
: DESCRIPTIONx
: DESCRIPTIONdim
: DESCRIPTION
_optimizing!(s::S) where S <: Union{_State, AbstractSolver}
Set the solver optimizing
status to true
.
_optimizing(s::S) where S <: Union{_State, AbstractSolver}
Check if s
is in an optimizing state.
_satisfying!(s::S) where S <: Union{_State, AbstractSolver}
Set the solver optimizing
status to false
.
_select_worse(s::S) where S <: Union{_State, AbstractSolver}
Within the non-tabu variables, select the one with the worse error .
_set!(s::S, x, val) where S <: Union{_State, AbstractSolver}
Set the value of variable x
to val
.
_set_domain!(m::Model, x, values)
DOCSTRING
Arguments:
m
: DESCRIPTIONx
: DESCRIPTIONvalues
: DESCRIPTION
_set!(s::S, x, y) where S <: Union{_State, AbstractSolver}
Swap the values of variables x
and y
.
_to_union(datatype)
Make a minimal Union
type from a collection of data types.
_value!(s::S, x, val) where S <: Union{_State, AbstractSolver}
Set the value of variable x
to val
.
_value(s::S, x) where S <: Union{_State, AbstractSolver}
Return the value of variable x
.
_values!(s::S, values) where S <: Union{_State, AbstractSolver}
Set the variables values.
_vars_costs(s::S) where S <: Union{_State, AbstractSolver}
Access the variables costs.
_var_cost!(s::S, x, cost) where S <: Union{_State, AbstractSolver}
Set the cost
of variable x
.
_var_cost(s::S, x) where S <: Union{_State, AbstractSolver}
Return the cost of variable x
.
_vars_costs!(s::S, costs) where S <: Union{_State, AbstractSolver}
Set the variables costs.
_vars_costs(s::S) where S <: Union{_State, AbstractSolver}
Access the variables costs.
_verbose(settings, str)
Temporary logging function. #TODO: use better log instead (LoggingExtra.jl)
mts = - get_time_stamp(model)
return TimeStamps(mts, mts, mts, mts, mts, mts, mts) end
add!(m::M, x) where M <: Union{Model, AbstractSolver}
add!(m::M, c) where M <: Union{Model, AbstractSolver}
add!(m::M, o) where M <: Union{Model, AbstractSolver}
Add a variable x
, a constraint c
, or an objective o
to m
.
add_value!(m::M, x, val) where M <: Union{Model, AbstractSolver}
Add val
to x
domain.
add_var_to_cons!(m::M, c, x) where M <: Union{Model, AbstractSolver}
Add x
to the constraint c
list of restricted variables.
constraint!(m::M, func, vars) where M <: Union{Model, AbstractSolver}
Add a constraint with an error function func
defined over variables vars
.
constriction(m::M, x) where M <: Union{Model, AbstractSolver}
Return the constriction of variable x
.
_decay_tabu!(s::S) where S <: Union{_State, AbstractSolver}
Decay the tabu list.
_decrease_tabu!(s::S, x) where S <: Union{_State, AbstractSolver}
Decrement the tabu value of variable x
.
_delete_tabu!(s::S, x) where S <: Union{_State, AbstractSolver}
Delete the tabu entry of variable x
.
delete_value(m::M, x, val) where M <: Union{Model, AbstractSolver}
Delete val
from x
domain.
delete_var_from_cons(m::M, c, x) where M <: Union{Model, AbstractSolver}
Delete x
from the constraint c
list of restricted variables.
describe(m::M) where M <: Union{Model, AbstractSolver}
Describe the model.
draw(m::M, x) where M <: Union{Model, AbstractSolver}
Draw a random value of x
domain.
_empty_tabu!(s::S) where S <: Union{_State, AbstractSolver}
Empty the tabu list.
get_cons_from_var(m::M, x) where M <: Union{Model, AbstractSolver}
Access the constraints restricting variable x
.
get_constraint(m::M, c) where M <: Union{Model, AbstractSolver}
Access the constraint c
.
get_constraints(m::M) where M <: Union{Model, AbstractSolver}
Access the constraints of m
.
get_domain(m::M, x) where M <: Union{Model, AbstractSolver}
Access the domain of variable x
.
get_kind(m::M) where M <: Union{Model, AbstractSolver}
Access the kind of m
, such as :sudoku
or :generic
(default).
get_name(m::M, x) where M <: Union{Model, AbstractSolver}
Access the name of variable x
.
get_objective(m::M, o) where M <: Union{Model, AbstractSolver}
Access the objective o
.
get_objectives(m::M) where M <: Union{Model, AbstractSolver}
Access the objectives of m
.
get_time_stamp(m::M) where M <: Union{Model, AbstractSolver}
Access the time (since epoch) when the model was created. This time stamp is for internal performance measurement.
get_variable(m::M, x) where M <: Union{Model, AbstractSolver}
Access the variable x
.
get_variables(m::M) where M <: Union{Model, AbstractSolver}
Access the variables of m
.
get_vars_from_cons(m::M, c) where M <: Union{Model, AbstractSolver}
Access the variables restricted by constraint c
.
_insert_tabu!(s::S, x, tabu_time) where S <: Union{_State, AbstractSolver}
Insert the bariable x
as tabu for tabu_time
.
is_sat(m::M) where M <: Union{Model, AbstractSolver}
Return true
if m
is a satisfaction model.
is_specialized(m::M) where M <: Union{Model, AbstractSolver}
Return true
if the model is already specialized.
length_cons(m::M, c) where M <: Union{Model, AbstractSolver}
Return the length of constraint c
.
length_cons(m::M) where M <: Union{Model, AbstractSolver}
Return the number of constraints in m
.
length_objs(m::M) where M <: Union{Model, AbstractSolver}
Return the number of objectives in m
.
_length_tabu!(s::S) where S <: Union{_State, AbstractSolver}
Return the length of the tabu list.
length_var(m::M, x) where M <: Union{Model, AbstractSolver}
Return the domain length of variable x
.
length_vars(m::M) where M <: Union{Model, AbstractSolver}
Return the number of variables in m
.
max_domains_size(m::Model, vars) = begin
DOCSTRING
model()
Construct a _Model, empty by default. It is recommended to add the constraints, variables, and objectives from an empty _Model. The following keyword arguments are available,
vars=Dictionary{Int,Variable}()
: collection of variablescons=Dictionary{Int,Constraint}()
: collection of constraintsobjs=Dictionary{Int,Objective}()
: collection of objectiveskind=:generic
: the kind of problem modeled (useful for specialized methods such as pretty printing)
dist_extrema(values::T...) where {T <: Number}
Computes the distance between extrema in an ordered set.
o_mincut(graph, values; interdiction = 0)
Compute the capacity of a cut (determined by the state of the solver) with a possible interdiction
on the highest capacited links.
objective!(m::M, func) where M <: Union{Model, AbstractSolver}
Add an objective evaluated by func
.
objective(func, name)
Construct an objective with a function func
that should be applied to a collection of variables.
post_process(s::MainSolver)
Launch a series of tasks to round-up a solving run, for instance, export a run's info.
remote_dispatch!(solver)
Starts the LeadSolver
s attached to the MainSolver
.
remote_stop!!(solver)
Fetch the pool of solutions from LeadSolvers
and merge it into the MainSolver
.
solution(s)
Return the only/best known solution of a satisfaction/optimization model.
solve_for_loop!(solver, stop, sat, iter)
First loop in the solving process that starts LeadSolver
s from the MainSolver
, and _SubSolver
s from each MetaSolver
.
solve_while_loop!(s, )
Search the space of configurations.
specialize!(solver)
Replace the model of solver
by one with specialized types (variables, constraints, objectives).
specialize(m::M) where M <: Union{Model, AbstractSolver}
Specialize the structure of a model to avoid dynamic type attribution at runtime.
stop_while_loop()
Check the stop conditions of the solve!
while inner loop.
_tabu(s::S) where S <: Union{_State, AbstractSolver}
Access the list of tabu variables.
_tabu(s::S, x) where S <: Union{_State, AbstractSolver}
Return the tabu value of variable x
.
variable!(m::M, d) where M <: Union{Model, AbstractSolver}
Add a variable with domain d
to m
.
variable(values::AbstractVector{T}, name::AbstractString; domain = :set) where T <: Number
variable(domain::AbstractDomain, name::AbstractString) where D <: AbstractDomain
Construct a variable with discrete domain. See the domain
method for other options.
d = domain([1,2,3,4], types = :indices)
x1 = variable(d, "x1")
x2 = variable([-89,56,28], "x2", domain = :indices)