JuLS is a Julia Local Search solver that combines Constraint Based Local Search (CBLS) and Constraint Programming (CP) to solve Constraint Optimization Problem (COP). It is to be seen as an open source project that gives the possibility to solve combinatorial and black box optimization problem.
A paper with theoritical foundations accompanying this solver can be found here.
The CBLS part is inspired from the paper LocalSolver 1.x. The CP part is inspired from MiniCP and SeaPearl.jl.
Clone the project and start julia in your terminal at the root using :
julia --threads=auto --project=.
Examples are given for the Knapsack problem, TSP and Graph Coloring Problem in this notebook . To solve a new COP using JuLS, one needs to :
- Create a new experiment to store the instance data :
YourExperiment <: ExperimentAn experiment must implement the functions :
n_decision_variables(e::YourExperiment)
decision_type(e::YourExperiment)These functions define the number of decision variables and the type of decision (BinaryDecisionValue, IntDecisionValue, ...)
- Declare the domain generation function for your decision variables
generate_domains(e::YourExperiment)- Declare an initialization heuristic that must return a vector of decision variables :
(::SimpleInitialization)(e::YourExperiment)- Create a Directed Acyclic Graph (DAG) of invariants representing your COP :
create_dag(e::YourExperiment)- Declare a neighbourhood heuristic
struct YourNeighbourhood <: NeighbourhoodHeuristicOtherwise a default neighbourhood heuristic is given automatically. This one samples randomly two decision variables and generates all the possible move combinations for these variables.
- Declare a move selection heuristic
struct YourPicker <: MoveSelectionHeuristicOtherwise a default move selection heuristic is given automatically. This one picks the most impactful and feasible move among the ones evaluated.
- Initialize a model. To efficiently filter moves with CP, set
using_cp = true
model = init_model(
e;
init = SimpleInitialization(),
neigh = YourNeighbourhood(...),
pick = YourPicker(...),
using_cp = true
)- Optimize over iterations or time
optimize!(model; limit = IterationLimit(100))
optimize!(model; limit = TimeLimit(10))- Generate an output
make_output_folder(model)- model: The Local Search model that will optimize the problem defined
- dag: The Directed Acyclic Graph (DAG) structure to evaluate the constraints and objectives of the problem to optimize. Each DAG component is declared in the invariant section.
- cp: The constraint programming solver to filter efficiently infeasible moves. A builder is provided to convert a DAG into the corresponding CSP (Constraint Satisfaction Problem)
- heuristics: The heuristics to be used during model optimization for initialization, neighbourhood definition and move selection.
- experiments: Optimizes a certain problem based on input data. The place to declare the problem's DAG and the customized heuristics.
If you have any inquiries pertaining to the code or the paper, please do not hesitate to contact the authors cited below. In case you encounter any issues while utilising the code or wish to report a bug, you may open an issue. We kindly request that you provide specific details regarding the problem so that we can offer prompt and efficient assistance.
