n-wouda / alns Goto Github PK

The CI runner takes an increasing amount of time to resolve package dependencies. This has resulted in build times running up to 10min for the Python 3.10 build. We should cache the dependencies for a while on the CI runner, so as to avoid these very long runtimes.

EDIT: I'm pretty sure scipy/statsmodels solved this in some way, so their CI scipts would be a good place to start.

Currently, we nowhere show how to use the callbacks. We should provide at least one example somewhere, and I think a good case would be to do 2-opt in TSP.

[partially based on https://doi.org/10.1016/j.cor.2022.105903, thanks @leonlan]

• Less parameters/tuning. Can we learn some of these? See also #73.
• Does adaptive anything even make sense? What about regular LNS?
• How to select which operators work well together/which operators to keep? Can we use that to guide the actual heuristic? Or even just offer that as statistics after iterating?

I am reproducing the TSP example in a Jupyter Notebook and in the following line:
initial_solution = greedy_repair(state, random_state)

I get the following error:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-181-62f3c5d57681> in <module>
----> 1 initial_solution = greedy_repair(state, random_state)


<ipython-input-178-f634089afd1a> in greedy_repair(current, random_state)
     12 
     13     while len(current.edges) != len(current.nodes):
---> 14         node = next(node for node in nodes 
     15                     if node not in current.edges)
     16 

<ipython-input-178-f634089afd1a> in <genexpr>(.0)
     13     while len(current.edges) != len(current.nodes):
     14         node = next(node for node in nodes 
---> 15                     if node not in current.edges)
     16 
     17         # Computes all nodes that have not currently been visited,

TypeError: unhashable type: 'list'

I fixed the previous with the following in line 15:

node = next(node for node in nodes if node not in current.edges.values())

But the type error keeps propagating:

TypeError                                 Traceback (most recent call last)
<ipython-input-190-62f3c5d57681> in <module>
----> 1 initial_solution = greedy_repair(state, random_state)

<ipython-input-188-fd3fe98c19d8> in greedy_repair(current, random_state)
     21             # not result in a subcycle, as that would violate the TSP
     22             # constraints.
---> 23         unvisited = {other for other in current.nodes
     24 
     25                          if other != node

<ipython-input-188-fd3fe98c19d8> in <setcomp>(.0)
     24 
     25                          if other != node
---> 26                          if other not in visited
     27                          if not would_form_subcycle(node, other, current)}
     28 

TypeError: unhashable type: 'list'

because visited is a set. If I transform the set into a list so the previous works I will have the same type of error in the next line. It would help me to have an input on the intended behavior.

Thank you in advance!

Hi, if the problem is to optimize a problem with binary variables x_i, and the objective function F(x), then is the ALNS applicable for such problems. BTW, how to define the dimensions and variable type? Thanks for your time.

This is completely absent in the library, but should really be added.

My newer projects use pyproject.toml (and poetry) for dependency management. ALNS should do the same.

It would be nice to have a callback function to be called at moments other than when a new best solution is found. As fair as I know, the most frequent alternatives are:

• after_repair: After the repair step, before acceptance. Rationale: "explore with destroy/repair, exploit with local search"
• on_accept: When accepted, before best. Rationale: "good enough" to be spend additional resources improving the solution

Ideally, the callback functions should all be different. For example, a callback function to be called after the repair step should only explore small neighborhoods since it will be called frequently, whereas we may want to spend more resources when we accepted the solution.

I also know of one paper that performs local search between the destroy and repair step, but it is quite niche and I haven't read an ALNS paper so far describing the same method.

See also #85. Most ALNS heuristics have a ton of (hyper)parameters. This happens more or less naturally, as may things can be tweaked - in operators, call-backs, but also in the core accept/stop/operator selection classes.

We can help users with tuning. The ML community has a lot of this already, with e.g. keras-tuner, ray.tune, etc. Those are used by a lot of people, apparently with some success. We could have a look at how these work, and take some of the good ideas for our own.

In this repository, I saw a stopping criterion that runs until the percentage difference between a new best solution and the old best solution is lower than some threshold. They called it an "on convergence" stopping criterion.

It might be difficult to have this stand on its own, but could perhaps be combined with other stopping criteria. The repository I link to do that as well. So then we would also have to think a bit about how to compose different stopping criteria in a straightforward manner. A simple container class that implements the StoppingCriterion interface should suffice, but we might want to show in an example how to do that.

Currently, there are two required dependencies: numpy, and matplotlib. Numpy is used in many places, in fact our entire algorithm is built around it.

Matplotlib, however, only finds use in the Result class, for plotting statistics. These plots are not required to use the algorithm, although they do provide insight and are valuable in developing heuristics. I do not think, however, we should force users to install matplotlib just for this facility. A better way is to make matplotlib optional, and only request the user install matplotlib when using the plotting facilities of the Result class.

Hello N-Wouda
This is the first time that I want to solve a model with metaheuristics. I want to use ALNS for my VRP-TW model. Could you explain how should I use these files and which file should be changed and adapted with my model?
Thank you.

See here for Github instructions on this.

Something to do once we have a JOSS publication.

This should probably be a toggle - for longer iteration lengths, the list may become prohibitive. Also think about what kind of statistics. At the very least:

• Objective value at each iteration;

For operator evaluation, perhaps:

• Counts of chosen destroy/repair operators;
• [Operator weights?]

All these ALNS papers look alike in their basic structure. They discuss an initial solution, their operators, acceptance criteria, possibly a local search procedure, and their weight updating scheme. There's very little new under the sun in how all that is organised.

It might be nice if the implementation can take function docstrings, and built-in descriptions for core library functions, to generate a standard Latex stub of such a metaheuristic description.

For every operator (destroy and repair), it seems that the returned state must be a (modified) deep copy of the current state passed as a parameter of the operator.
When profiling my implementation, it turns out that copying the state at every operator call takes a lot of time, and slow the algorithm.

Is it possible to do otherwise to make the algorithm faster ?

See e.g. here. PALNS is sometimes used instead of ALNS itself, to parallelise some parts of the search.

E.g. a readthedocs-like website? Currently, the central gist is explained by the examples, but more could be done to document the API.

Weight scheme is perhaps a poor choice. These schemes are responsible for adaptive operator selection. A better name might be adaptive scheme, since one need not use weights (or similar) to determine how to select operators.

Further:

• SimpleWeights -> RouletteWheel (cite some paper using this)
• SegmentedWeights -> SegmentedRouletteWheel (default for many papers)

Maybe also look around for other simple adaptive schemes in the literature. In particular, I saw one paper that did $w \coloneqq (1 - \theta) w + \theta r$, with $\theta \in (0, 1)$ and $r$ equal to the objective gain divided by the iteration runtime. This is similar to the SimpleWeights method, but more complex in the weights used.

This might include a simple test case for the TSP, in a carefully curated example to showcase the use of this library.

I was tuning updating weights for the PL heuristic, and encountered no weights can be set to zero. This should be allowed: all we require is that they are non-negative, which includes zero.

Some time ago I wrote a notebook demonstrating how to use ALNS for CVRP here. I'll rewrite it a bit soon and make a pull request for it when I'm done.

state = TspState(customers, {}) initial_solution = greedy_repair(state, random_state)
I change the cities into customers with VRPTW problems, and I see ur greedy_repair function only directly considered about nearest path. If i want to consider the window time as a factor to greedly initialize a init_solution, how to set ur greedy_repair function? thx!!!

We have type annotations (almost) everywhere. Those are OK as well, at least according to mypy.

Can we use this to test whether ALNS compiles with mypyc?

Santini et al. (2018) present a lot of them in their paper. I implemented three that seemed promising, but to be thorough we should probably also get the rest in.

The updating scheme currently used is overly restrictive: it updates the weights using a convex combination of the current weight, and whatever outcome the operator resulted in. That is how it was done (more or less) in the original ALNS paper, but does not reflect recent use of the ALNS metaheuristic in literature. We should also accommodate those cases.

In particular, we need to allow finer control over the weight updating scheme:

• Allow resets after a certain number of iterations;
• Allow specification of the initial weights, and those after resets;
• Allow for different updating mechanisms: aside from the convex combination scheme we currently use, a simple addition rule (new_weight = old_weight + <performance outcome>) is also commonly used.
• Track statistics on operator weights over iterations.

Hi,

Is is possible to combine with milp solver? such as comercial solver gurobi,cplex or open source solver scip,cbc and so on.
I see your project OR-Analysis which are solving VRPSPDMS-H problem with ALNS and compare with Cplex , and is it possible combine of them?

Thanks,

I saw your example of the Traveling Salesman Problem to understand the solution and implementation of the ALNS.
I was wandering if there was another example of TSP where the input is a distance matrix for nodes. The example TSP file is https://people.sc.fsu.edu/~jburkardt/datasets/tsp/gr17_d.txt

Thank you.

Getting the follow error on import after pip install

from alns import ALNS, State

results in,
ModuleNotFoundError: No module named 'alns.tools'`

'tools' folder missing inside 'alns' folder.
Manually copying tools folder fixes the issue.
Can this be fixed with pip install?

Introduce a selection scheme that selects destroy and repair operators with uniform probability. To be done after introducing the new selection interface.

As the title

Eventually I want to get a JOSS (journal of open source software) publication out of this package. See JOSS, and the submission guidelines. See here for a list of currently open reviews, to get a feel for the review process.

There are a few papers that have repair operators that work only with a specific set of destroy operators, that is, operators that destroy and repair different aspects of a solution can often only work together on that aspect. In e.g. inventory routing one might have operators for the routing, and others for the inventory. Those need not understand each other.

I thus want to add the option to indicate with which destroy operators a repair operator can be used. For example, as an only_after keyword-only argument to ALNS.add_repair_operator. The default should remain that every repair operator works with every destroy operator.

I am not a fan of acceptance criteria or weight schemes requiring inheritance to pass type checks. I would much rather use protocols (this PEP), but those are not available in Py3.7.

So we have to wait until EOL of 3.7, which will happen in July 2023.

pre-commit is a library for managing pre-commit git hooks. Since we already have black, mypy, flake8, etc., it's just a matter of installing and configuring pre-commit to make sure all linters/type checkers are run before committing. We can also add many other useful hooks, e.g. any of the flake8 extensions, so that we have more consistent style and minimize the unimportant discussions in code reviews.

I use pre-commit in my local environment, not the least because I sometimes forget to run one of the hooks manually. What do you think of adding this to the library?

Or similar. I think the project is now at a point where we need a dedicated documentation website, where we can also put some cookbooks up (e.g., the example notebooks - compare scipy cookbooks).

In the TSP example the solution only shows the minimum distance value, Is it possible to display the route as an array which results in minimum distance ?

Into two parts:

examples/
api/

Then we only have a top-level index.rst file, that lists everything in these folders.

E.g. when not plotting all possible outcome types, the axes are still fixed as if one did. Like so:

Thanks for the recent release on collecting runtimes!

What do you think of adding a feature to iterate using a maximum time value as stopping condition? It's something I come across a lot in the literature, e.g., François et al. (2019).

I implemented something for myself like this:

def iterate(self,
            initial_solution: State,
            weight_scheme: WeightScheme,
            crit: AcceptanceCriterion,
            max_value: float = 10_000, # originally: iterations
            condition: str = 'iterations' # new
            **kwargs) -> Result:
    """
    ...
    """
    ...

    while not self._stop(max_value, criterion):
        ...

    return Result(best, stats)


def _stop(self, max_value: float, condition: str) -> bool:
    """
    Check whether the stopping condition holds in the current iteration.
    """
    if max_value < 0:
        raise ValueError("Max value must be non-negative.")

    if not hasattr(self, "_start_time"):
        self._start_time = perf_counter()

    if not hasattr(self, "_current_iteration"):
        self._current_iteration = 0

    # Update the current values
    self._current_iteration += 1

    if condition == "iterations":
        return self._current_iteration >= max_value

    elif condition == "time":
        return perf_counter() - self._start_time >= max_value

    else:
        raise ValueError(
            "Stopping condition is invalid. Choose 'time' or 'iterations'."
        )

The _stop method is implemented such that time and iterations are always tracked so that I could collect runtimes (this was before the recent release).

Fairly often I see things like

The starting temperature of the simulated annealing procedure is set such that, in the first iteration, a solution with an objective up to 5% worse than the current solution is accepted with probability 0.5, and the cooling rate is set such that the temperature in the last iteration is 0.2 percent of the start temperature. - Hornstra et al, 2020, in a paper on the VRPSPD-H.

This sort of 'autofit' is interesting to add, and not too hard to do either.

Our current weight schemes are all very simple. I feel more can be learned, perhaps using some sort of multi-armed bandit.

I have some old code lying around where I solve the permutation flow shop problem with large neighborhood search / iterated greedy. This example also covers iterated local search, because the heuristic applies the relocate neighborhood after greedily repairing the solution.

Some todos:

• Update code to ALNS V5
• Include 3 destroy operators with different destruction rates
• Include 2 greedy repair operators
• Use the alpha UCB selection mechanism
• Choose an instance. Instances are very easy to parse (using numpy) because it's a single processing times matrix.

ALNS currently supports a callback function to be called when ALNS finds a new global best solution state:

Since we use the notion of outcomes in ALNS, we can generalize this hook to work for other outcomes such as better, accepted, and rejected as well.

A simple proposal is to replace on_best with a new method:

def on_best(self, func: _OperatorType, outcome: Outcome):
     self._on_outcome[outcome] = func

I am not aware of any papers that do this. Maybe it's just a redundant addition.

The usual stuff for open source projects. I think we can do with a lot of standard texts for this, but we should add them in soon.

As listed in e.g. Santini, A., Ropke, S. & Hvattum, L.M. Journal of Heuristics (2018) 24: 783. https://link.springer.com/article/10.1007%2Fs10732-018-9377-x. Following the results of said paper, I suggest to implement the following:

• Simulated annealing (SA). The general temperature-based annealing scheme. This will need to be moved into a separate acceptance criterion, instead of in the current ALNS class.
• Hill climbing (HC). This criterion only accepts better solutions.
• Record-to-record travel (RRT). Uses a threshold and relative improvement against the best solution to accept a new candidate.

TODO:

• Update notebooks
• Update README
• Update license to "Niels Wouda and contributors"
• Write style file, add linter to CI pipeline
• Write changelogs (#64, #67)

See also the AlgorithmVisitor used by Santini, here. Some of these ideas are really good, especially regarding the restarts/reset.

Santini implements:

• on_algorithm_start, called before iterating.
• on_prerun_end, called when the calibration run ends.
• on_iteration_end, called at the end of each iteration.
• on_many_iters_without_improvement, called when no new best solution has been found for a number of iterations (parameter).