LocalSearchSolvers.jl

Documentation for LocalSearchSolvers.jl.

LocalSearchSolvers.AbstractSolver Type

AbstractSolver

Abstract type to encapsulate the different solver types such as Solver or _SubSolver.

source

LocalSearchSolvers.Constraint Type

Constraint{F <: Function}

Structure to store an error function and the variables it constrains.

source

LocalSearchSolvers.LeadSolver Type

LeadSolver <: MetaSolver

Solver managed remotely by a MainSolver. Can manage its own set of local sub solvers.

source

LocalSearchSolvers.MainSolver Type

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 problem

• state::_State: An internal state to store the info necessary to a solving run

• options::Options: User options for this solver

• subs::Vector{_SubSolver}: Optional subsolvers

source

LocalSearchSolvers.MetaSolver Type

Abstract type to encapsulate all solver types that manages other solvers.

source

LocalSearchSolvers.Objective Type

Objective{F <: Function}

A structure to handle objectives in a solver. `struct Objective{F <: Function} name::String f::F end``

source

LocalSearchSolvers.Objective Method

Objective(F, o::Objective{F2}) where {F2 <: Function}

Constructor used in specializing a solver. Should never be called externally.

source

LocalSearchSolvers.Options Type

Options()

Arguments:

• dynamic::Bool: is the model dynamic?

• iteration::Union{Int, Float64}: limit on the number of iterations

• print_level::Symbol: verbosity to choose among :silent, :minimal, :partial, :verbose

• solutions::Int: number of solutions to return

• specialize::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: DESCRIPTION

• tabu_local::Int: DESCRIPTION

• tabu_delta::Float64: DESCRIPTION

• threads::Int: Number of threads to use

• time_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)

source

LocalSearchSolvers.Variable Type

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

source

LocalSearchSolvers._Model Type

_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

source

LocalSearchSolvers._State Type

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

source

LocalSearchSolvers._SubSolver Type

_SubSolver <: AbstractSolver

An internal solver type called by MetaSolver when multithreading is enabled.

Arguments:

• id::Int: subsolver id for debugging

• model::Model: a ref to the model of the main solver

• state::_State: a deepcopy of the main solver that evolves independently

• options::Options: a ref to the options of the main solver

source

Base.empty! Method

empty!(s::Solver)

source

Base.empty! Method

empty!(m::Model)

DOCSTRING

source

Base.in Method

var::Int ∈ c::Constraint

source

Base.in Method

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.

source

LocalSearchSolvers._add! Method

_add!(c::Constraint, x)

Add the variable of indice x to c.

source

LocalSearchSolvers._add_to_constraint! Method

_add_to_constraint!(x::Variable, id)

Add a constraint id to the list of constraints of x.

source

LocalSearchSolvers._check_restart Method

_check_restart(s)

Check if a restart of s is necessary. If s has subsolvers, this check is independent for all of them.

source

LocalSearchSolvers._check_subs Method

_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

source

LocalSearchSolvers._compute! Method

_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 solver

• o: targeted objective

• cons_lst: list of targeted constraints, if empty compute for the whole set

source

LocalSearchSolvers._compute_cost! Method

_compute_cost!(s, ind, c)

Compute the cost of constraint c with index ind.

source

LocalSearchSolvers._compute_costs! Method

_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.

source

LocalSearchSolvers._compute_objective! Method

_compute_objective!(s, o::Objective)
_compute_objective!(s, o = 1)

Compute the objective o's value.

source

LocalSearchSolvers._cons_cost! Method

_cons_cost!(s::S, c, cost) where S <: Union{_State, AbstractSolver}

Set the cost of constraint c.

source

LocalSearchSolvers._cons_cost Method

_cons_cost(s::S, c) where S <: Union{_State, AbstractSolver}

Return the cost of constraint c.

source

LocalSearchSolvers._cons_costs! Method

_cons_costs!(s::S, costs) where S <: Union{_State, AbstractSolver}

Set the constraints costs.

source

LocalSearchSolvers._cons_costs Method

_cons_costs(s::S) where S <: Union{_State, AbstractSolver}

Access the constraints costs.

source

LocalSearchSolvers._constriction Method

_constriction(x::Variable)

Return the cosntriction of x, i.e. the number of constraints restricting x.

source

LocalSearchSolvers._delete! Method

_delete!(c::Constraint, x::Int)

Delete x from c.

source

LocalSearchSolvers._delete_from_constraint! Method

_delete_from_constraint!(x::Variable, id)

Delete a constraint id from the list of constraints of x.

source

LocalSearchSolvers._draw! Method

_draw!(s)

Draw a random (re-)starting configuration.

source

LocalSearchSolvers._dynamic! Method

_dynamic!(options, dynamic) = begin

DOCSTRING

source

LocalSearchSolvers._dynamic Method

_dynamic(options) = begin

DOCSTRING

source

LocalSearchSolvers._find_rand_argmax Method

_find_rand_argmax(d::DictionaryView)

Compute argmax of d and select one element randomly.

source

LocalSearchSolvers._get_constraints Method

_get_constraints(x::Variable)

Access the list of constraints of x.

source

LocalSearchSolvers._get_vars Method

_get_vars(c::Constraint)

Returns the variables constrained by c.

source

LocalSearchSolvers._inc_cons! Method

_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}

Increment the maximum constraint id that has been attributed to m.

source

LocalSearchSolvers._inc_objs! Method

_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}

Increment the maximum objective id that has been attributed to m.

source

LocalSearchSolvers._inc_vars! Method

_inc_vars!(m::M) where M <: Union{Model, AbstractSolver}

Increment the maximum variable id that has been attributed to m.

source

LocalSearchSolvers._info_path! Method

_info_path!(options, iterations) = begin

DOCSTRING

source

LocalSearchSolvers._info_path Method

_info_path(options, path)

DOCSTRING

source

LocalSearchSolvers._is_empty Method

_is_empty(m::Model)

DOCSTRING

source

LocalSearchSolvers._iteration! Method

_iteration!(options, iterations) = begin

DOCSTRING

source

LocalSearchSolvers._iteration Method

_iteration(options) = begin

DOCSTRING

source

LocalSearchSolvers._length Method

_length(c::Constraint)

Return the number of constrained variables by c.

source

LocalSearchSolvers._max_cons Method

_max_cons(m::M) where M <: Union{Model, AbstractSolver}

Access the maximum constraint id that has been attributed to m.

source

LocalSearchSolvers._max_objs Method

_max_objs(m::M) where M <: Union{Model, AbstractSolver}

Access the maximum objective id that has been attributed to m.

source

LocalSearchSolvers._max_vars Method

_max_vars(m::M) where M <: Union{Model, AbstractSolver}

Access the maximum variable id that has been attributed to m.

source

LocalSearchSolvers._move! Function

_move!(s, x::Int, dim::Int = 0)

Perform an improving move in x neighbourhood if possible.

Arguments:

• s: a solver of type S <: AbstractSolver

• x: selected variable id

• dim: describe the dimension of the considered neighbourhood

source

LocalSearchSolvers._neighbours Function

_neighbours(s, x, dim = 0)

DOCSTRING

Arguments:

• s: DESCRIPTION

• x: DESCRIPTION

• dim: DESCRIPTION

source

LocalSearchSolvers._optimizing! Method

_optimizing!(s::S) where S <: Union{_State, AbstractSolver}

Set the solver optimizing status to true.

source

LocalSearchSolvers._optimizing Method

_optimizing(s::S) where S <: Union{_State, AbstractSolver}

Check if s is in an optimizing state.

source

LocalSearchSolvers._print_level! Method

_print_level!(options, level) = begin

DOCSTRING

source

LocalSearchSolvers._print_level Method

_print_level(options) = begin

DOCSTRING

source

LocalSearchSolvers._process_threads_map! Method

_process_threads_map!(options, ptm)

TBW

source

LocalSearchSolvers._process_threads_map Method

_process_threads_map(options)

TBW

source

LocalSearchSolvers._restart! Function

_restart!(s, k = 10)

Restart a solver.

source

LocalSearchSolvers._satisfying! Method

_satisfying!(s::S) where S <: Union{_State, AbstractSolver}

Set the solver optimizing status to false.

source

LocalSearchSolvers._select_worse Method

_select_worse(s::S) where S <: Union{_State, AbstractSolver}

Within the non-tabu variables, select the one with the worse error .

source

LocalSearchSolvers._set! Method

_set!(s::S, x, val) where S <: Union{_State, AbstractSolver}

Set the value of variable x to val.

source

LocalSearchSolvers._set_domain! Method

_set_domain!(m::Model, x, values)

DOCSTRING

Arguments:

• m: DESCRIPTION

• x: DESCRIPTION

• values: DESCRIPTION

source

LocalSearchSolvers._solutions! Method

_solutions!(options, solutions) = begin

DOCSTRING

source

LocalSearchSolvers._solutions Method

_solutions(options) = begin

DOCSTRING

source

LocalSearchSolvers._specialize! Method

_specialize!(options, specialize) = begin

DOCSTRING

source

LocalSearchSolvers._specialize Method

_specialize(options) = begin

DOCSTRING

source

LocalSearchSolvers._step! Method

_step!(s)

Iterate a step of the solver run.

source

LocalSearchSolvers._swap_value! Method

_set!(s::S, x, y) where S <: Union{_State, AbstractSolver}

Swap the values of variables x and y.

source

LocalSearchSolvers._tabu_delta! Method

_tabu_delta!(options, time) = begin

DOCSTRING

source

LocalSearchSolvers._tabu_delta Method

_tabu_delta(options) = begin

DOCSTRING

source

LocalSearchSolvers._tabu_local! Method

_tabu_local!(options, time) = begin

DOCSTRING

source

LocalSearchSolvers._tabu_local Method

_tabu_local(options) = begin

DOCSTRING

source

LocalSearchSolvers._tabu_time! Method

_tabu_time!(options, time) = begin

DOCSTRING

source

LocalSearchSolvers._tabu_time Method

_tabu_time(options) = begin

DOCSTRING

source

LocalSearchSolvers._threads Function

_threads(options) = begin

DOCSTRING

source

LocalSearchSolvers._threads! Function

_threads!(options, threads) = begin

DOCSTRING

source

LocalSearchSolvers._time_limit! Method

_time_limit!(options, time::Time) = begin

DOCSTRING

source

LocalSearchSolvers._time_limit Method

_time_limit(options)

DOCSTRING

source

LocalSearchSolvers._to_union Method

_to_union(datatype)

Make a minimal Union type from a collection of data types.

source

LocalSearchSolvers._value! Method

_value!(s::S, x, val) where S <: Union{_State, AbstractSolver}

Set the value of variable x to val.

source

LocalSearchSolvers._value Method

_value(s::S, x) where S <: Union{_State, AbstractSolver}

Return the value of variable x.

source

LocalSearchSolvers._values! Method

_values!(s::S, values) where S <: Union{_State, AbstractSolver}

Set the variables values.

source

LocalSearchSolvers._values Method

_vars_costs(s::S) where S <: Union{_State, AbstractSolver}

Access the variables costs.

source

LocalSearchSolvers._var_cost! Method

_var_cost!(s::S, x, cost) where S <: Union{_State, AbstractSolver}

Set the cost of variable x.

source

LocalSearchSolvers._var_cost Method

_var_cost(s::S, x) where S <: Union{_State, AbstractSolver}

Return the cost of variable x.

source

LocalSearchSolvers._vars_costs! Method

_vars_costs!(s::S, costs) where S <: Union{_State, AbstractSolver}

Set the variables costs.

source

LocalSearchSolvers._vars_costs Method

_vars_costs(s::S) where S <: Union{_State, AbstractSolver}

Access the variables costs.

source

LocalSearchSolvers._verbose Method

_verbose(settings, str)

Temporary logging function. #TODO: use better log instead (LoggingExtra.jl)

source

LocalSearchSolvers.add! Method

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.

source

LocalSearchSolvers.add_value! Method

add_value!(m::M, x, val) where M <: Union{Model, AbstractSolver}

Add val to x domain.

source

LocalSearchSolvers.add_var_to_cons! Method

add_var_to_cons!(m::M, c, x) where M <: Union{Model, AbstractSolver}

Add x to the constraint c list of restricted variables.

source

LocalSearchSolvers.constraint! Method

constraint!(m::M, func, vars) where M <: Union{Model, AbstractSolver}

Add a constraint with an error function func defined over variables vars.

source

LocalSearchSolvers.constraint Method

constraint(f, vars)

DOCSTRING

source

LocalSearchSolvers.constriction Method

constriction(m::M, x) where M <: Union{Model, AbstractSolver}

Return the constriction of variable x.

source

LocalSearchSolvers.decay_tabu! Method

_decay_tabu!(s::S) where S <: Union{_State, AbstractSolver}

Decay the tabu list.

source

LocalSearchSolvers.decrease_tabu! Method

_decrease_tabu!(s::S, x) where S <: Union{_State, AbstractSolver}

Decrement the tabu value of variable x.

source

LocalSearchSolvers.delete_tabu! Method

_delete_tabu!(s::S, x) where S <: Union{_State, AbstractSolver}

Delete the tabu entry of variable x.

source

LocalSearchSolvers.delete_value! Method

delete_value(m::M, x, val) where M <: Union{Model, AbstractSolver}

Delete val from x domain.

source

LocalSearchSolvers.delete_var_from_cons! Method

delete_var_from_cons(m::M, c, x) where M <: Union{Model, AbstractSolver}

Delete x from the constraint c list of restricted variables.

source

LocalSearchSolvers.describe Method

describe(m::M) where M <: Union{Model, AbstractSolver}

Describe the model.

source

LocalSearchSolvers.domain_size Method

domain_size(m::Model, x) = begin

DOCSTRING

source

LocalSearchSolvers.draw Method

draw(m::M, x) where M <: Union{Model, AbstractSolver}

Draw a random value of x domain.

source

LocalSearchSolvers.empty_tabu! Method

_empty_tabu!(s::S) where S <: Union{_State, AbstractSolver}

Empty the tabu list.

source

LocalSearchSolvers.get_cons_from_var Method

get_cons_from_var(m::M, x) where M <: Union{Model, AbstractSolver}

Access the constraints restricting variable x.

source

LocalSearchSolvers.get_constraint Method

get_constraint(m::M, c) where M <: Union{Model, AbstractSolver}

Access the constraint c.

source

LocalSearchSolvers.get_constraints Method

get_constraints(m::M) where M <: Union{Model, AbstractSolver}

Access the constraints of m.

source

LocalSearchSolvers.get_domain Method

get_domain(m::M, x) where M <: Union{Model, AbstractSolver}

Access the domain of variable x.

source

LocalSearchSolvers.get_kind Method

get_kind(m::M) where M <: Union{Model, AbstractSolver}

Access the kind of m, such as :sudoku or :generic (default).

source

LocalSearchSolvers.get_name Method

get_name(m::M, x) where M <: Union{Model, AbstractSolver}

Access the name of variable x.

source

LocalSearchSolvers.get_objective Method

get_objective(m::M, o) where M <: Union{Model, AbstractSolver}

Access the objective o.

source

LocalSearchSolvers.get_objectives Method

get_objectives(m::M) where M <: Union{Model, AbstractSolver}

Access the objectives of m.

source

LocalSearchSolvers.get_time_stamp Method

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.

source

LocalSearchSolvers.get_variable Method

get_variable(m::M, x) where M <: Union{Model, AbstractSolver}

Access the variable x.

source

LocalSearchSolvers.get_variables Method

get_variables(m::M) where M <: Union{Model, AbstractSolver}

Access the variables of m.

source

LocalSearchSolvers.get_vars_from_cons Method

get_vars_from_cons(m::M, c) where M <: Union{Model, AbstractSolver}

Access the variables restricted by constraint c.

source

LocalSearchSolvers.insert_tabu! Method

_insert_tabu!(s::S, x, tabu_time) where S <: Union{_State, AbstractSolver}

Insert the bariable x as tabu for tabu_time.

source

LocalSearchSolvers.is_sat Method

is_sat(m::M) where M <: Union{Model, AbstractSolver}

Return true if m is a satisfaction model.

source

LocalSearchSolvers.is_specialized Method

is_specialized(m::M) where M <: Union{Model, AbstractSolver}

Return true if the model is already specialized.

source

LocalSearchSolvers.length_cons Method

length_cons(m::M, c) where M <: Union{Model, AbstractSolver}

Return the length of constraint c.

source

LocalSearchSolvers.length_cons Method

length_cons(m::M) where M <: Union{Model, AbstractSolver}

Return the number of constraints in m.

source

LocalSearchSolvers.length_objs Method

length_objs(m::M) where M <: Union{Model, AbstractSolver}

Return the number of objectives in m.

source

LocalSearchSolvers.length_tabu Method

_length_tabu!(s::S) where S <: Union{_State, AbstractSolver}

Return the length of the tabu list.

source

LocalSearchSolvers.length_var Method

length_var(m::M, x) where M <: Union{Model, AbstractSolver}

Return the domain length of variable x.

source

LocalSearchSolvers.length_vars Method

length_vars(m::M) where M <: Union{Model, AbstractSolver}

Return the number of variables in m.

source

LocalSearchSolvers.max_domains_size Method

max_domains_size(m::Model, vars) = begin

DOCSTRING

source

LocalSearchSolvers.model Method

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 variables

• cons=Dictionary{Int,Constraint}(): collection of constraints

• objs=Dictionary{Int,Objective}(): collection of objectives

• kind=:generic: the kind of problem modeled (useful for specialized methods such as pretty printing)

source

LocalSearchSolvers.o_dist_extrema Method

dist_extrema(values::T...) where {T <: Number}

Computes the distance between extrema in an ordered set.

source

LocalSearchSolvers.o_mincut Method

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.

source

LocalSearchSolvers.objective! Method

objective!(m::M, func) where M <: Union{Model, AbstractSolver}

Add an objective evaluated by func.

source

LocalSearchSolvers.objective Method

objective(func, name)

Construct an objective with a function func that should be applied to a collection of variables.

source

LocalSearchSolvers.post_process Method

post_process(s::MainSolver)

Launch a series of tasks to round-up a solving run, for instance, export a run's info.

source

LocalSearchSolvers.remote_dispatch! Method

remote_dispatch!(solver)

Starts the LeadSolvers attached to the MainSolver.

source

LocalSearchSolvers.remote_stop! Method

remote_stop!!(solver)

Fetch the pool of solutions from LeadSolvers and merge it into the MainSolver.

source

LocalSearchSolvers.solution Method

solution(s)

Return the only/best known solution of a satisfaction/optimization model.

source

LocalSearchSolvers.solve_for_loop! Method

solve_for_loop!(solver, stop, sat, iter)

First loop in the solving process that starts LeadSolvers from the MainSolver, and _SubSolvers from each MetaSolver.

source

LocalSearchSolvers.solve_while_loop! Method

solve_while_loop!(s, )

Search the space of configurations.

source

LocalSearchSolvers.specialize! Method

specialize!(solver)

Replace the model of solver by one with specialized types (variables, constraints, objectives).

source

LocalSearchSolvers.specialize Method

specialize(m::M) where M <: Union{Model, AbstractSolver}

Specialize the structure of a model to avoid dynamic type attribution at runtime.

source

LocalSearchSolvers.status Method

status(solver)

Return the status of a MainSolver.

source

LocalSearchSolvers.stop_while_loop Method

stop_while_loop()

Check the stop conditions of the solve! while inner loop.

source

LocalSearchSolvers.tabu_list Method

_tabu(s::S) where S <: Union{_State, AbstractSolver}

Access the list of tabu variables.

source

LocalSearchSolvers.tabu_value Method

_tabu(s::S, x) where S <: Union{_State, AbstractSolver}

Return the tabu value of variable x.

source

LocalSearchSolvers.variable! Function

variable!(m::M, d) where M <: Union{Model, AbstractSolver}

Add a variable with domain d to m.

source

LocalSearchSolvers.variable Method

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)

source