netotz / alpha-neighbor-p-center-problem Goto Github PK

Context

In Solver.move() method, the largest two values of same_neighbors dictionary are updated in the loop to retrieve them in constant time when calculating the objective function (best_out).

Bug

There's a missing condition to replace the second largest value when some value is less than the largest but greater than the second largest.

In this problem, the set of nodes is divided in 2: users and facilities. The TSP Lib format uses 1 set only, so for this problem, it has to be modified by adding an extra column on the coordinates that will indicate if a node is a user or a facility.

Add a class named Solver to wrap an instance with a solution and other related information like:

• Random solution generator
• Objective function vertex (maximum alpha-th)
• Objective function value, so it can be stored
• Move heuristics functions here, being methods instead

Implement the GRASP metaheuristic framework, with the available constructive and local search heuristics.

• Calibrate values for beta
• Experiment with the reactive scheme
• Run 2 or 3 instances with a large number of iterations to see how it behaves and use it as reference for next experiments
• Calibrate number of max iterations
• Plot results

Make a Jupyter notebook to experiment with the performance of the local search heuristics

Add a README with instructions on how to run the code

Currently the local search function only changes one point inside the solution for another outside of it.

This new function should interchange 2 points at the same time, exploring a bigger, different neighborhood.

This heuristic could then be compared too, related to #3

Currently the A-FVS algorithm is the default local search. First it checks if the objective function value can be reduced by "breaking" the critical allocation, then it iterates the closed facilities. If a swap reduces the objective function, the procedure repeats.

The A-FVS should be checked and see if it can be improved by reducing steps, refactoring code or using other data structures.

Update README file describing the problem, the research and its purpose, the methodologies, how the repository is organized, how to navigate it and how to clone it and use the code.

Very impressed with this work. The grasp algorithm performs excellent considering the fact it is single threaded and is written in Python. Learned about anpcp two days ago and obj_func_module.py with its visualisation really helped me to understand what this is about.

May be you can add a "seed" argument to Instance.random so that it can generate repruducible
instances you no longer need to store:

import numpy as np
...
    def random(cls, n: int, m: int, x_max: int = 1000, y_max: int = 1000, seed: int = None) -> "Instance":
        distinct_coords = set()
        total = n + m
        if seed is None: 
            seed = randint(0, sys.maxsize)
        rng = np.random.default_rng(seed)
        while len(distinct_coords) < total:
            distinct_coords |= {
                (rng.integers(0, x_max), rng.integers(0, y_max))

see https://towardsdatascience.com/stop-using-numpy-random-seed-581a9972805f .

More general questions arise how easy this method can be adapted to problem variants.

Example a) Lets assume we are not only interested in the alpha-best distance, but in a (weighted) sum of the alpha best distances. May be the distance to the nearer facilities also matter for some users. Not always the alpha-1 nearer facilities are down.

Example b) May be a user has not yet selected a set of possible facility locations, only their number is known and we want to compute their optimal locations. Finding exact facility location options is deferred to a later stage using the determined optimal locations. This variant is a continuous optimization problem.

How hard is it to adapt your method to these variants?

Progress often is triggered by competition, so I tried to come up with an alternative Python implementation shining for some problem instances were grasp struggles. Main advantages of my implementation are:

• Very easy to code (a few hours).
• Easy to adapt to problem variants.
• Performs good with the TSP sample problems.
• No "swap" implementation required, just a 3 line fitness function.

Disadvantages are:

• Performs less good at extremly large random samples (2000 users, 2000 facilities)
• Requires a modern many-core CPU - tested with a 16 core AMD 5950x
• No "partial" fitness evaluation, fitness needs to be reevaluated for each solution candidate.

Question is how relevant random problem instances are in the real world. May be they are misleading algorithm design in the wrong direction? Very good you already included samples derived from real world TSP instances.

For 'data/rl1323_993_330_4.anpcp.tsp' p=12, alpha=2 my algorithms finds

selection = [114 7 251 296 161 329 252 117 85 26 133 162]
value = 4190.0

In less than a minute. I tried grasp for 5000 iterations, the best it found was 4388. My algo performs about 150000 fitness evaluations / sec, using 32 parallel threads on a AMD 5950x CPU on linux. On windows it is only about 100000 evaluations / sec, because windows has a bad implementation of Python multithreading.

See https://github.com/dietmarwo/fast-cma-es/blob/master/examples/anpcp/anpcp.py for my code. You either can check out the whole repo or do a "pip install fcmaes" to try it out. https://github.com/dietmarwo/fast-cma-es/blob/master/examples/anpcp/anpcpc.py is the continuous variant (b), variant (a) is implemented in both cases but commented out.

Assign a set of potential facilities, and another one for customers.

Some operations could be done in less time by changing some of the data structures.

For example, instead of using an allocation matrix with users rows and facilities columns (in which each cell is the kth level of closeness), one of users rows and closeness columns (each cell being a facility) would allow to get the alpha-neighbors in O(1).

Add a module or class with functions or methods to plot any instance with a solution set

The Fast Swap algorithm is implemented from a paper that uses it for the p-median problem, so the algorithm calculates its objective function, not the ANPCP's.

Quick experiments show that the local search still works, i.e. it improves random solutions. Hopefully it will yield better results by correcting the algorithm to calculate the actual ANPCP objective function.