#include "ad_solver.h"

gcc -o foo foo.c libad_solver.a

gcc -I/usr/adaptive/include -L/usr/adaptive/lib -o foo foo.c -lad_solver

• int ad_size: size of the problem (number of variables).
  
  
• int *ad_sol: the array of variables.
  
  
• int ad_do_not_init: if set to true (a value != 0) the initial solution used is the one present in ad_sol (else a random solution is computed).
  
  
• int ad_base_value: base offset for the domain of each variable (each vaiable can then take a value in ad_base_value .. ad_base_value + ad_size-1.
  
  
• int ad_break_nl: when the solver displays a solution a new line is inserted every ad_break_nl values (0 if no break is wanted). This makes it possible to display matrix in a more readable form.
  
  
• int ad_debug: debug level (0: none, 1: trace, 2: interactive). This requires the library is compiled with debugging support (see INSTALL).
  
  
• char *ad_log_file: name of the log file (or NULL if none). This requires the library is compiled with log file support (see INSTALL).
  
  
• int ad_reinit_after_if_swap: see the defintion of the user function Cost_If_Swap() for more information.

• int ad_exhaustive: if true the solver always evaluate (the cost of) all possible swaps to chose the best swap. If false a projection of the error on each variable is used to first select the ``worst'' variable ([1] for more information).
  
  
• int ad_prob_select_loc_min: this is a percentage to force a local minimum (i.e. when the 2 selected variables to swap are the same) instead of staying on a plateau (a swap involves 2 different variables but the overall cost will remain the same). If a value > 100 is given, this option is not used.
  
  
• int ad_freeze_loc_min: number of swaps a variable is frozen when a local minimum is encountered (i.e. the 2 variables to swap are the same).
  
  
• int ad_freeze_swap: number of swaps the 2 variables that have been selected (and thus swapped) to improve the solution are frozen.
  
  
• int ad_reset_limit: number of frozen varables before a reset is triggered.
  
  
• int ad_nb_var_to_reset: number of variables to randomly reset.
  
  
• int ad_restart_limit: maximum number of iterations before restarting from scratch (give a big number to avoid a restart).
  
  
• int ad_restart_max: maximal number of restart to perform before giving up.

• int ad_total_cost: cost of the current solution.
  
  
• int ad_nb_restart: number of restart performed.
  
  
• int ad_nb_iter: numberb of iterations performed.
  
  
• int ad_nb_swap: number of swaps performed.
  
  
• int ad_nb_same_var: number of variables with (the same) highest cost.
  
  
• int ad_nb_reset_swap: number of reset swaps performed.
  
  
• int ad_nb_local_min: number of local minimum encountered.

• int Ad_Solve(void): this function invokes the Adaptive solver to find a solution to the problem. This function calls in turn user functions (e.g. to compute the cost of a solution or to project this cost on a given variable). This function returns the ad_total_cost at then end of the resolution (i.e. 0 if a solution has been found).
  
  
• void Ad_Display(int *t, unsigned *mark): this function displays an array t (generally ad_sol) and also displays a 'X' for marked variables (if mark != NULL). This function is generally only used by the solver.

• int Cost_Of_Solution(void): [MANDATORY] this function returns the cost of the current solution (stored in ad_sol).
  
  
• int Cost_On_Variable(int i): [OPTIONAL] this function returns the projection of the current cost on the ith variable (from 0 to ad_size-1). If not present then the resolution must be exhausitive (see ad_exhausitive).
  
  
• int Cost_If_Swap(int i, int j): [OPTIONAL] this function evaluates the cost of a swap (the swap is not performed and should not be performed by the function). If this function is not present a default function is used which:
  • performs the swap,
    
    
  • calls Cost_Of_Solution(),
    
    
  • undoes the swap,
    
    
  • if the variable int ad_reinit_after_if_swap is true then Cost_Of_Solution() is also called another time. This is useful if Cost_Of_Solution() updates some global information to ensure this information is reset.
  
  
  
• void Executed_Swap(int i, int j): [OPTIONAL] this function is called to inform the user code a swap has been done. This is useful if the user code maintains some global information.
  
  
• int Next_I(int i): [OPTIONAL] this function is called in case of an exhaustive search (see ad_exhaustive). It is used to enumerate the first variable. This functions receives the current i (initially it is -1) and returns the next value (or something > ad_size at the end). In case this function is not defined, i takes the values 0 .. ad_size - 1.
  
  
• int Next_J(int i, int j): [OPTIONAL] this function is called in case of an exhaustive search (see ad_exhaustive). It is used to enumerate the second variable. This functions receives the current i and the current j (for each new i it is -1) and returns the next value for j (or something > ad_size at the end). In case this function is not defined, j takes the values i+1 .. ad_size-1 for each new i.
  
  
• void Display_Solution(void): [OPTIONAL] this function is called to display a solution (stored inside ad_size). This allows the user to display something different from the actual values (useful if modelisation of the problem needs a decoding to be understood).

• long User_Time(void): returns the user time since the start of the process.
  
  
• unsigned Randomize_Seed(unsigned seed): intializes the random generator with a given seed.
  
  
• unsigned Randomize(void): randomly initilizes the random generator.
  
  
• unsigned Random(unsigned n): returns a random integer >= 0 and < n.
  
  
• void Random_Permut_Init(unsigned n): this is used to initialise the generation of a random permutation of the values 0 .. n-1 (n is generally ad_size). This function must be called once before the n calls to function Random_Permut_Value() (see below) which returns each time one new value (different from all other previously returned values).
  
  
• unsigned Random_Permut_Value(void): each call to this function returns a random new value inside 0 .. n-1 (where n is the value passed to Random_Permut_Init(n).

• it parses the command-line to retrieve tuning options, the running mode (number of executions,...), and the parameter if it is expected (e.g. the chessboard size in the queens). Each tuning option can be set via a command-line option and the corresponding variable (see input variables) is set. The only exception is for for ad_nb_var_reset which can be specified indirectly as a percentage (instead of an absolute value) inside the variable reset_percent.
  
  
• it invokes a user function void Initializations(void) which must initialises all input variables (e.g. ad_size, ad_sol,...). This function should only initialises tuning variable that are not set via command-line options. In this case the value of the corresponding variable is -1.
  
  
• it invokes the Adaptive solver.
  
  
• it displays the result or a summary of the counters (in benchmark mode).

• int param: the parameter (if param_needed is true).
  
  
• int reset_percent: -1 or the % of variables to reset defined by a command-line option. If it is -1, the Initializations() function should either set it to a percentage or directly set ad_nb_var_reset.
  
  
• int seed: -1 or the seed defined by a command-line option. The main() function initialises the random number generator in both cases so the Initializations() does not need to do it.
  
  
• int read_initial: true if the initial solution must be read from stdin. In this case the main() function reads the initial permutation just before invoking the solver.
  
  
• int check_valid: if true the user function int Check_Solution(void) is invoked and should return true if the solution stored in ad_solver is valid. A Simple definition for this function could be:

  
  int Check_Solution(void)
  {
    return Cost_Of_Solution() == 0;
  }
  
  

  
  
  
• int count: the number of execution required (if > 1 runs in benchmark mode).

#include "ad_solver.h"
#include "main.h"

int param_needed = 1;   /* parameter needed */

int
Cost_Of_Solution(void)
{
 ...
}
...
void
Initializations(void)
{
  ad_size = param;
  ad_sol = malloc(ad_size * sizeof(int));

  ad_base_value = ad_break_nl = 0;
  
  if (ad_prob_select_loc_min == -1)
    ad_prob_select_loc_min = 80;

  ...
  if (reset_percent == -1)
    reset_percent = 5;
 ...
}
...

[1]

P. Codognet and D. Diaz. Yet Another Local Search Method for Constraint Solving. In Proc. SAGA01, 1st International Symposim on Stochastic Algorithms : Foundations and Applications, LNCS 2246, Springer Verlag 2001

This document was translated from L^AT_EX by H^EV^EA.