The Weber Problem

[josepht...@gmail.com]

Great work! Learnt a lot from the library.

I am implementing algorithms for Weber problem(the continuous version of p-median problem). My first choice is VNS. However, as I read the source code of the Maximum Clique, I find it seems that  the VNS only works for discrete case. Is that true?

If it is true, is it possible to customize the library for the continuous Weber problem? Would it be a lot of work to do that?

Thanks.

[Herman De Beukelaer]

Hi,

JAMES is focused on discrete optimization because local searches are.

There are many kinds of VNS implementations but I have no experience with continuous VNS.

Could you explain the algorithm layout you have in mind in a bit more detail?

How would neighbourhoods be defined for your continuous problem?

Herman

[josepht...@gmail.com]

Could you explain the algorithm layout you have in mind in a bit more detail?

The most parts are the same, except that we don't use local search algorithm to improve the current solution. We use a algorithm called Cooper's algorithm. 

How would neighbourhoods be defined for your continuous problem?

There are two solutions to the question:

1. Discretize the continuous plane. Thus, it is converted to p-median problem implicitly. Then use local searches. (Do you think it is a good idea? I am not sure whether or not to formulate the problem as continuous one or discrete one.)

2. Don't discretize. Use Cooper's algorithm explained below.

The details of VNS for Cooper's problem:

The details of Cooper's algorithm:

Cooper's heuristic generates $p$ subset of fixed points and then solved each one using the exact method for solving a single-facility location problem. The fixed points' set is divided into $p$ subsets. For each of these $p$ subsets, using an initial facility location, the exact location method is applied to find the optimal single facility location. Each fixed point is then reallocated to the nearest facility. After all fixed points have been completely reallocated, the exact location method is applied again to improve the location of those facilities where the set of customers assigned has changed. This process, alternating between the location and the allocation phases, is repeated until no further improvement can be made.

Thanks for your reply. Hope more people would notice this framework. Kudos.

[josepht...@gmail.com]

Actually, I am more inclined to formulate the problem as a discrete one. Then local searches can be applied.

[Herman De Beukelaer]

I do not see any issues with implementing the VNS using Cooper's algorithm in JAMES. In fact, the way I see it, Cooper's algorithm is a kind of local search, since it starts from a given solution which is iteratively improved. In JAMES you could thus implement Cooper's algorithm by extending the abstract LocalSearch class.

In each step you would re-allocate the fixed points to the nearest facility and update the facility locations using the exact method for a single facility per subset. This goes in the method searchStep(). To update the current and best solution you should use updateCurrentAndBestSolution(...). This method returns false if no improvement is made, in which case you may call stop() from within searchStep() to terminate the algorithm. So something like this:

public class CooperAlgorithm extends LocalSearch<WeberSolution> {

  public CooperAlgorithm(Problem<WeberSolution> problem){

    super("Cooper", problem);

  }

  @Override

  protected void searchStep(){

    

    // retrieve and copy current solution

    WeberSolution sol = Solution.checkedCopy(getCurrentSolution());

    

    // re-allocate fixed points to nearest facility

    // ...

    // optimize locations by applying single-facility solution to each subset

    // ...

    // check for improvement

    if(!updateCurrentAndBestSolution(sol)){

      stop();

    }    

  }

 

}

For examples of how to implement your custom solution type (e.g. WeberSolution) and how to define the problem (objective, etc.) you can take a look at the TSP examples on the website (e.g. http://www.jamesframework.org/examples/tsp/).

Once you have implemented Cooper's algorithm it can easily be wrapped in a VNS (see maximum clique example). The only restriction is that (for now) JAMES only allows b = 1, i.e. only a single neighbour will be sampled from the k-neighbourhoud in each step of VNS. We have plans to allow b > 1 (and run the applied local searches in parallel) but currently this is not possible. Is this an important restriction for you?

Good luck!

Herman