LocalSearchSolvers

Constraint-Based Local Search Framework

The LocalSearchSolvers.jl framework proposes sets of technical components of Constraint-Based Local Search (CBLS) solvers and combine them in various ways. Make your own CBLS solver!

A higher-level JuMP interface is available as CBLS.jl and is the recommended way to use this package. A set of examples is available within ConstraintModels.jl.

Dependencies

This package makes use of several dependencies from the JuliaConstraints GitHub org:

• ConstraintDomains.jl: a domains back-end package for all JuliaConstraints front packages
• Constraints.jl: a constraints back-end package for all JuliaConstraints front packages
• CompositionalNetworks.jl: a module to learn error functions automatically given a concept
• Garamon.jl (incoming): geometrical constraints

It also relies on great packages from the julialang ecosystem, among others,

• ModernGraphs.jl (incoming): a dynamic multilayer framework for complex graphs which allows a fine exploration of entangled neighborhoods

Related packages

• JuMP.jl: a rich interface for optimization solvers
• CBLS.jl: the actual interface with JuMP for LocalSearchSolvers.jl
• ConstraintModels.jl: a dataset of models for Constraint Programming
• COPInstances.jl (incoming): a package to store, download, and generate combinatorial optimization instances

Features

Wanted features list:

• Strategies
  • Move: local move, permutation between n variables
  • Neighbor: simple or multiplexed neighborhood, dimension/depth
  • Objective(s): single/multiple objectives, Pareto, etc.
  • Parallel: distributed and multi-threaded, HPC clusters
  • Perturbation: dynamic, restart, pool of solutions
  • Portfolio: portfolio of solvers, partition in sub-problems
  • Restart
    • restart sequence
    • partial/probabilistic restart (in coordination with perturbation strategies)
  • Selection of variables: roulette selection, multi-variables, meta-variables (cf subproblem)
  • Solution(s): management of pool, best versus diverse
  • Tabu
    • No Tabu
    • Weak-tabu
    • Keen-tabu
  • Termination: when, why, how, interactive, results storage (remote)
• Featured strategies
  • Adaptive search
  • Extremal optimization
• Others
  • Resolution of problems
    • SATisfaction
    • OPTimisation (single-objective)
    • OPTimisation (multiple-objective)
    • Dynamic problems
  • Domains
    • Discrete domains (any type of numbers)
    • Continuous domains
    • Arbitrary Objects such as physical ones
  • Domain Specific Languages (DSL)
    • Straight Julia :raw
    • JuMPish | MathOptInterface.jl
    • MiniZinc
    • OR-tools ?
  • Learning settings (To be incorporated in MetaStrategist.jl)
    • Compositional Networks (error functions, cost functions)
    • Reinforcement learning for above mentioned learning features
    • Automatic benchmarking and learning from all the possible parameter combination (instance, model, solver, size, restart, hardware, etc.)

Contributing

Contributions to this package are more than welcome and can be arbitrarily, and not exhaustively, split as follows:

• All features mentioned above
• Adding new constraints and symmetries
• Adding new problems and instances
• Adding new ICNs to learn error of existing constraints
• Creating other compositional networks which target other kind of constraints
• Just making stuff better, faster, user-friendlier, etc.

Contact

Do not hesitate to contact me (@azzaare) or other members of JuliaConstraints on GitHub (file an issue), the julialang Discourse forum, the julialang Slack workspace, the julialang Zulip server (Constraint Programming stream), or the Humans of Julia Humans-of-Julia discord server(julia-constraint channel).