mt-simulated-annealing

A multi-threaded Simulated Annealing core in C

DEVELOPED FOR (PLEASE, CITE AS SUCH):
Vales et al., "A parallel optimization approach for controlling allele diversity in conservation schemes,"
Mathematical Biosciences, Volume 183, Issue 2, June 2003, Pages 161-173.

This implementation uses a loose temperature control, where each of the k threads run a number of iterations
with a fixed temperature and then notifies to other threads. Upon notification temperature reduces by
a k-th root factor.

THIS ALGORITHM IS REGARDED AS ONE OF THE ORIGINAL MULTI-THREADING WAYS TO IMPLEMENT SIMULATED ANNEALING

Files provided

• annealing.h: header files for the annealing function
• annealing.c: implementation of the multithreading annealing
• sampleLP.c: example for solving a generic Linear Program
• sampleILP.c: example for solving a generic Integer Linear Program
• sample-runtime.c: example for introducing problem type (LP or ILP) and parameters at run-time

Library contents

The library provides a single function implementing the multi-threading simulated annealing:

tresult annealing(int nthreads, int repetitions, int iterations, void *program);

This function minimizes the given problem/program (SEE NOTES BELOW TO CHANGE TO MAXIMIZATION), whose arguments are:

1. nthreads: Number of simultaneous threads to use. Set it greater or equal than the available number of cores.
2. repetitions: Repetitions at each temperature. Increment for more exhaustive search.
3. iterations: Number of independent problem runs to be performed (in many cases independent runs may help to skip better local optima).
4. program: A struct containing the user-provided functions to allocate, deallocate, initiate, create, evaluate cost, copy, and show program solutions.

Program structure is declared as

struct tprogram {
        double (*cost)(void *);
        void (*allocate)(void **);
        void (*deallocate)(void **);
        void (*initial)(void *);
        void (*show)(void *, FILE *);
        void (*create)(void *, void *);
        void (*copy)(void *, void*);
};

Each of these functions must be user-provided, according to the optimization problem to solve. All arguments passed as void are actually tsolution (see below), and must be casted as such into functions' implementation. Please see below for function definitions and examples, and technical notes for details.

Besides, the annealing function returns a structure:

struct tresult {
        void *solution; // A pointer to the solution
        double elapsedtime;
        double value;
};

which contains:

1. *solution: a tsolution (see below) user-defined structure with solution's variables
2. value: the cost associated to the solution
3. elapsedtime: the time required to find the solution (in seconds)

Optimization problem definition

Please see provided files (sampleLP, sampleILP, sample-runtime) for examples of program definitions.

Optimization program is defined by providing the following structure and functions:

struct tsolution {
        // All the variables required to define the problem come here
};

double cost(void *solution); 

It computes the given solution's cost.

void create(void *currentsolution, void *newsolution) {

        char constraintsfulfilled = 0;

        // Common template for this function
        while (!constraintsfulfilled) {
                copy(currentsolution, newsolution); // Possibly it starts by creating a copy of the current solution
                ...

        }
}

It creates a new solution to be tested for the optimization problem. It receives also the current considered solution of the annealing algorithm, which the function may use to create a modified one. This function is in charge to check solution's conformity to problem's constraints, i.e. it can only submit valid solutions.

void initial(void *newsolution);

It creates the first solution for the problem. As the previous function it can only returns a solution fulfilling all problem's constraints.

void allocate(void **solution);

It must allocate a solution and its components (by issuing all necessary malloc calls). It is internally called by the annealing function.

void deallocate(void **solution);

It must free all the resources allocated by a solution. It is internally called by the annealing function.

void show(void *solution, FILE *F);

It displays solution at the given FILE (e.g. stderr, stdout, ... .

void copy(void *currentsolution, void *newsolution);

It copies all the internal components of a solution strcuture (currensolution) to another solution strcture (newsolution). It is internally called by the annealing function, and can be used by other problem's functions like create as shown above.

Function usage

Typically the optimization must be called by creating a correct tprogram structure and calling annealing function with that argument. For example:

struct tsolution {
        double x[D];
};

typedef struct tsolution tsolution;

double cost(void *solution);
void allocate(void **solution);
void deallocate(void **solution);
void initial(void *newsolution);
void show(void *solution, FILE *F);
void create(void *currentsolution, void *newsolution);
void copy(void *currentsolution, void *newsolution);

int main(int argc, char **argv) {

        tprogram F;
        tresult r;

        F.cost = *cost;
        F.allocate = *allocate;
        F.deallocate = *deallocate;
        F.initial = *initial;
        F.show = *show;
        F.create = *create;
        F.copy = *copy;

        r = annealing(2, 1000, 20, &F);

        printf("Sol: %f, Elapsed time: %f\n", r.value, r.elapsedtime);
        show(r.solution, stdout);
        deallocate(&r.solution);

        return (0);
}

// Program's functions come next...

Notes

Minimization/Maximization

By default annealing seeks problem's minimum. To find maximum, you can either:

• Invert cost's function result, e.g. instead of

  return value;
  

  use

  return -value;
  

  and take into account that problem's final value will be also inverted.
• Change:

  #DEFINE PROBLEMTYPE MIN
  

  to:

  #DEFINE PROBLEMTYPE MAX