alns

Unlike many domain-specific implementations, alns provides a problem-agnostic API designed for experimentation and research. Key features include:

• Problem-Agnostic API: Easily apply the algorithm to various combinatorial optimisation problems.
• Built-in Components: Provides many acceptance criteria and operator selection schemes out of the box.
• Diagnostics & Visualization: Includes diagnostic statistics and plotting methods.
• Extensibility: Supports logging and the registration of custom callbacks at various points during the search process.

ALNS (Adaptive Large Neighbourhood Search) is a metaheuristic used to solve difficult combinatorial optimisation problems.

The ALNS process follows these steps:

1. Initialization: Start with an initial solution.
2. Iteration: Repeat the following until a stopping criterion is met:
   • Operator Selection: Select a 'destroy' operator and a 'repair' operator.
   • Transformation: Apply the operators to transform the current solution into a candidate solution.
   • Evaluation: Evaluate the candidate solution using an acceptance criterion.
   • Update: Update the operator selection scheme based on the evaluation outcome.

To use the alns library to solve a combinatorial optimisation problem, you must provide three core components:

1. A solution state: An object representing your problem's state that implements an objective() function to evaluate the quality of a solution.
2. An initial solution: A starting point for the algorithm.
3. Operators: One or more destroy and repair operators specifically tailored to your problem's structure.

The algorithm will then iterate by selecting operators, transforming the solution, and applying acceptance criteria until a stopping criterion is met.

In the alns package, operator selection schemes are used during the Adaptive Large Neighborhood Search (ALNS) process to decide which pair of destroy and repair operators to apply in each iteration.

All selection schemes inherit from the base class alns.select.OperatorSelectionScheme.OperatorSelectionScheme. You can choose from several built-in schemes depending on whether you want random selection, roulette wheel selection, or more advanced multi-armed bandit (MAB) approaches like AlphaUCB.

The alns.accept module provides various acceptance criteria used by the Adaptive Large Neighborhood Search (ALNS) algorithm to decide whether to accept or reject a candidate solution.

All acceptance criteria implement the alns.accept.AcceptanceCriterion.AcceptanceCriterion base class. When configuring an ALNS instance, you can provide one of the built-in criteria to control the search behavior (e.g., accepting only better solutions vs. accepting worse solutions to escape local optima).

The alns.iterate() method requires four main components to drive the search process:

1. Initial State: The starting ProblemState.
2. Selection Scheme (alns.select): Determines which destroy and repair operators to use in each iteration. Example: RandomSelect(num_destroy=1, num_repair=1).
3. Acceptance Criteria (alns.accept): Determines whether a new solution found by the operators should be accepted. Example: HillClimbing().
4. Stopping Criteria (alns.stop): Determines when the algorithm should terminate. Example: MaxRuntime(60) (seconds).

After running alns.iterate(...), the returned object contains the best_state found during the search.

The alns.stop module provides various criteria to automatically stop an ALNS search when specific conditions are met. You can use these to limit the search by time, iteration count, or lack of improvement. All stopping criteria implement the StoppingCriterion interface.

Available built-in criteria include:

• MaxIterations: Stops the search after a fixed number of iterations.
• MaxRuntime: Stops the search after a specified amount of elapsed time.
• NoImprovement: Stops the search if no improvement in the objective function is found for a certain number of iterations.

Install the core alns package using pip. The package requires numpy and matplotlib.

To enable advanced operator selection schemes using multi-armed bandit algorithms, install the optional mabwiser dependency.

# Standard installation
pip install alns

# Installation with optional MABWiser dependency for advanced operator selection
pip install alns[mabwiser]

The documentation requires specific dependencies listed in the docs group of the pyproject.toml file. To install these dependencies using Poetry, use the --with docs or --only docs flag.

poetry install --with docs
# OR
poetry install --only docs

To run the example Jupyter notebooks locally, you need to clone the repository and use poetry to manage a virtual environment with the necessary dependencies. Follow these steps:

1. Clone the repository:

   git clone https://github.com/N-Wouda/ALNS.git

2. Ensure poetry is installed and upgraded:

   pip install --upgrade poetry

3. Navigate to the repository and install dependencies, including the examples group and all extras:

   cd ALNS
   poetry install --with examples --all-extras

4. Launch the Jupyter notebook server:

   poetry run jupyter notebook

Once the server is running, navigate to the examples/ folder in your browser to access the notebooks.