Adaptive Search


A Library to Solve CSPs
Edition 1.0, for Adaptive Search version 0.9.0
by Daniel Diaz & Philippe Codognet




Copyright (C) 2002-2003 Daniel Diaz & Philippe Codognet

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111, USA.






1 Introduction

The Adaptive Search library provides a set of functions to solve CSPs by a local search method. For more information consult [1] The current release only works for problems that can be stated as permutation problems. More precisely, all n variables have a same domain x1 .. xn and are subject to an implicit all-different constraint. Several problems fall into this category and some examples are provided with the library.

2 Installation

Please refer to the file called INSTALL located in the src subdirectory.

3 The Adaptive Search API

3.1 Overall usage

The API consists in a set of global variables (decomposed into input variables which have to be set before invoking the resolution procedure and output variables which give information about the resolution) and a set of functions. The user has to set input variables before invoking the resolution function. He also has to define some functions which will be called by the resultion procedure (e.g. to compute the cost of a solution). Some functions are optional meaning that the solver performs an implicit treatment in the absence of such a function. Most of the times, providing an optional function speeds up the execution.

To use the API a C file should include the header file ad_solver.h:

#include "ad_solver.h"
Obviously the C compiler must be invoked with the adequate option to ensure the header file can be found by the preprocessor.

At link time, the library called libad_solver.a must be passed. Here also, some options might have to be passed to the C compiler to allow the linker to locate the library.

If both the include file and the library are in the same directory as the user C file (for instance foo.c), then the following Unix command line (using gcc) suffices:

gcc -o foo foo.c libad_solver.a
If the include file is in /usr/adaptive/include and the library in /usr/adaptive/lib, a possible invocation could be:

gcc -I/usr/adaptive/include -L/usr/adaptive/lib -o foo foo.c -lad_solver
3.2 Input global variables

The following input variables control the basic data and have to be initialised before calling the resolution function. The following input parameters make it possible to tune the solver and should be initialised before calling the resolution function.
3.3 Output global variables

The following variables (counters) are managed by the solver and can be consulted by the user to obtain some information about the resolution.
3.4 Functions

Here is the set of functions provided by the library:
3.5 User functions

The function Ad_Solve() calls some user functions to guide its resolution. Some functions are MANDATORY while others are OPTIONAL. Here is the set of user functions:
4 Other utility functions

To use this functions the user C code should include the file tools.h.
5 Using the default main() function

The user is obviously free to write his own main() function. In order to have a same command-line options for all bechmarks a default main() is included in the library (it is then used if no user main() is found at link-time). The default function act as follows: The use the default main() the user program should include the header file main.h. If a parameter is expected it should declare a variable param_needed initialised to 1.

In addition to the variables described above, the following global variables are available when using the default main(): Here is a fragment of a source file using the default main() function. More information can be obtained studyinh the example provided with the distribution.

#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;
 ...
}
...
References
[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 LATEX by HEVEA.