PaCCS version 0.91

All files Copyright (C) 2009-2016 Vasco Pedro
All rights reserved.

* Compiling

Type

make

to build the parallel solver version, and

make -mpi

to build the distributed version (you need an MPI implementation for
this).

Bad things happen if you give make more than one target.

** Compilation options

Use

make EXTRA_DEFINES=...

to add extra definitions to the compilation command, or

make DEFINES=...

to tweak the default compilation options.

Useful options include:

-DCOMPACT_DOMAINS bitmap based representation of the domains (REQUIRED)
-DINLINE_DOMAINS fit domain (which is a bitmap) in a C integer type
-DDOMAIN_BITS=N bitmap size (domains are {0, ..., N-1})
-DDOMAIN_BOUNDS include the domain's current minimum and maximum values
in its representation (DEFAULT)

-DTRACE show what's happening (part of it, anyway)

For other options, take a look at the Makefile, at src/options.c, or
at the full solver source.

The TUNING file says what options to use for the different
applications.

* Executing

Use mpirun to run the distributed versions.

** Runtime options

General:

--workers=N how many workers to use per process (the default is 4)
(may also be set through the FDC_AGENTS environment
variable)
--count-solutions count the solutions of the problem
(does not work for optimisation problems)
(the DEFAULT is to stop as soon as a solution has
been found, or a best solution, in the case of
optimisation problems)

Variable selection heuristics:

--first-var choose variables in order of creation (DEFAULT)
--first-fail choose first variables with the smallest domain
--most-constrained prefer variables involved in the most constraints
--size-degree choose the variable with the least ratio between
the domain size and the number of constraints it
appears in
--most-connected prefer variables which are connected by constraints
with the most variables (approximately implemented)
--random-var select a variable randomly
--min-value select the variable with the least value in its domain
--max-value select the variable with the greatest value in its
domain

Value selection heuristics:

--val-min instantiate the selected variable with the smallest
value from its domain (DEFAULT)
--val-max instantiate the selected variable with the greatest
value from its domain

Problem splitting:

--split-eager problem splitting works like variable labelling:
the variable whose domain is split has a singleton
domain in one subproblem, and the remaining values
in the other (DEFAULT)
--split-even try to divide the search space evenly amongst the
subproblems
--split-even1 same as above, but try to split the domain of just
one variable

--team-split-eager as above, for assigning work to the workers (only
--team-split-even useful if one wishes to have a strategy which is
--team-split-even1 different from the one used when assigning work to
teams)

See the TUNING file for the options to use with the different
problems, and the src/problem.c file for all the available options.

** Arguments

The arguments for some of the benchmark problems are:

costas array-length
golomb n.-of-marks
k-queens [-k n.-of-copies] n.-of-queens
langford n.-of-sets set-size
magic-seq sequence-length
magic-square square-size
partition n.-of-values
qap problem-name (see qap.h, DEFAULT is esc16i)
queens n.-of-queens

Arguments should come at the end of the command line, after any
runtime option.

* Programming

The header file should be included by the program.

** Types

fd_int variable
fd_constraint constraint (not very useful)

** Constants

Integer constants

FD_OK
FD_NOSOLUTION

** Functions

fd_init(int *argc, char **argv[]) initialise the solver
fd_end(void) stop the solver and clean up
fd_solve(void) start the solver (returns FD_OK or
FD_NOSOLUTION, which is only
meaningful when not counting
solutions)

fd_int fd_new(int min, int max) create a new variable with domain
[min, max]
fd_int fd_const(int value) create a new variable with domain
[value, value]
fd_label(fd_int vars[], int nvars) set variables to be labelled (the
DEFAULT is to label all variables)
fd_var_single(fd_int var, int *val) tests whether the variable domain
is a singleton, in which case its
value is stored at the specified
address
fd_var_value(fd_int var) return the variable's value

fd_print(fd_int var) print the variable's domain
fd_println(fd_int var) the same, followed by a newline

** Constraints

Arithmetic constraints

fd_eq(fd_int x, fd_int y) x = y
fd_ne(fd_int x, fd_int y) x != y
fd_lt(fd_int x, fd_int y) x < y
fd_le(fd_int x, fd_int y) x y
fd_ge(fd_int x, fd_int y) x >= y
fd_minus_eq(fd_int x, fd_int y, int k) x - y = k
fd_minus_ne(fd_int x, fd_int y, int k) x - y != k
fd_var_eq_minus(fd_int x, fd_int y, fd_int z) x = y - z
fd_var_eq_times(fd_int x, fd_int y, fd_int z) x = y * z

Global constraints

fd_all_different(fd_int X[], int n)
all n variables in X have different values

fd_fake_all_different(fd_int X[], int n)
all-different implemented with pairwise fd_ne() constraints
between the variables in X

fd_element(fd_int X[], int n, fd_int y, int k) X[y] = k
fd_element_var(fd_int X[], int n, fd_int y, fd_int z) X[y] = z

fd_sum(fd_int X[], int n, int k) sum(X) = k
fd_sum2(fd_int X[], int n, fd_int y) sum(X) = y

fd_sum_prod(fd_int X[], fd_int Y[], int n, int k) X . Y = k

fd_poly_eq(int C[], fd_int Y[], int n, fd_int z) z ' (if available) to find which compilation
options were used for compiling the application.