Simulated annealing: too slow with poor results

Question

I'm trying to solve, thanks to the simulated annealing method, the following problem :

Optimization problem

Where I already got the c_i,j,f values stored in a 1D array, so that

c_i,j,f <=> c[i + j * n + f * n * n]

My simulated annealing function looks like this :

int annealing(int n, int k_max, int c[]){
// Initial point (verifying the constraints )
int x[n * n * n];
for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
        for (int f = 0; f < n; f++){
            if (i == j && j == f && f == i){
                x[i + j * n + f * n * n] = 1;
            }else{
                x[i + j * n + f * n * n] = 0;
            }
        }
    }
}
// Drawing y in the local neighbourhood of  x : random permutation by keeping the constraints verified
int k = 0;
double T = 0.01; // initial temperature
double beta = 0.9999999999; // cooling factor
int y[n * n * n];
int permutation_i[n];
int permutation_j[n];
while (k <= k_max){ // k_max = maximum number of iterations allowed
    Permutation(permutation_i, n);
    Permutation(permutation_j, n);
    for (int f = 0; f < n; f++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                y[i + j * n + f * n * n] = x[permutation_i[i] + permutation_j[j] * n + f * n * n];
            }
        }
    }
    if (f(y, c, n) < f(x, c, n) || rand()/(double)(RAND_MAX) <= pow(M_E, -(f(y, c, n)-f(x, c, n))/T)){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int f = 0; f < n; f++){
                    x[i + j * n + f * n * n] = y[i + j * n + f * n * n];
                }
            }
        }
    }
    T *= beta;
    ++k;
}
return f(x, c, n);
}

The procedure Permutation(int permutation[], n) fills in the array permutation with a random permutation of [[0,n-1]] (for example, it would transform [0,1,2,3,4] into [3,0,4,2,1]).

The problem is, it takes too much time with 1000000 iterations, and the values of the objective function oscillate between 78 - 79 whilst I should get 0 as a solution.

I was also thinking I could do better when it comes to complexity... Someone may help me please?

Thanks in advance!

Answer 1

I would use std::vector<int>, instead of arrays (and define a couple of constants):

#include <vector>
#include <algorithm>
#include <random>

int annealing(int n, int k_max, std::vector<int> c) {

    const int N2 = n * n;
    const int N3 = N2 * n;

    std::vector<int> x(N3);
    std::vector<int> y(N3);
    std::vector<int> permutation_i(n);
    std::vector<int> permutation_j(n);

    // ...

The initial nested loops boil down to:

for (int i = 0; i < n; i++){
    x[(i*N2) + (i + (i * n))] = 1;
}

This should be your Permutation function:

void Permutation(std::vector<int> & x)
{
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(x.begin(), x.end(), g);
}

Initialize vectors before use (0 to n-1):

std::iota(permutation_i.begin(), permutation_i.end(), 0);
std::iota(permutation_j.begin(), permutation_j.end(), 0);

I have no idea what your f function is, but you should edit it to accept std::vector as its first two arguments.