OMP - Reduce to a value based on another value

Question

I'm trying to parallelize a simple algorithm for finding decent solutions to the travelling salesman problem.

Let the path be an array of integers corresponding to cities. In each attempt, two random indices to the path array are selected to be switched. This switch affects the distances to the preceding and following nodes for a total of 4 distances. If the sum of them is taken we can deduce whether the switch we performed yields a better or worse path than the old one. In the former case the switch is retained and we can move to the next attempt.

An idea to parallelize this algorithm is to try N different switches concurrently, and perform the one that generates the shortest path. The code I have so far is as follows:

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    #pragma omp parallel for reduction(*need help here*)
    for(int i=0; i<NUM_THREADS; i++){

        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        if(newDist >= oldDist){
            newDist = FLT_MAX;
        }

    }

    //perform the switch
    ....

    return minDist;
}

By setting the invalid switch distances to some large number I can reduce to the minimum of the distances, however I am more interested in the path itself than the distance. Is there a reduction that could be performed so that I end up with the index i that resulted in the minimum distance?

Answer 1

Use a shared vector to hold the information and then have a single thread use that vector to figure out what the best choice was:

float switchCities(){

    int switchCandidates[NUM_THREADS][2];
    float minDist;

    std::vector<std::pair<float,int> > best(omp_get_max_threads(), std::make_pair<float,int>(9e999999, -1));

    #pragma omp parallel for
    for(int i=0; i<NUM_THREADS; i++){
        //selecting 2 random candidates excluding the first and last
        switchCandidates[i][0] = rand() % (N-1) + 1;
        switchCandidates[i][1] = rand() % (N-1) + 1;

        float oldDist = localDist(switchCandidates[i][0], switchCandidates[i][1]);
        float newDist = localSwitchedDist(switchCandidates[i][0], switchCandidates[i][1]);

        auto &my_best = best.at(omp_get_thread_num());
        if(newDist >= my_best.first){
            my_best.first = newDist;
            my_best.second = i;
        }
    }

    //have one thread look at the `best` vector and find the best value here

    return minDist;
}