PaCCS version 0.90

All files Copyright (C) 2009-2014 Vasco Pedro <vp@di.uevora.pt>
All rights reserved.

* Compiling

Type

    make <program>

to build the parallel solver version, and

   make <program>-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)

  -DFAST		be quiet (DEFAULT)

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.


* Programming

The <paccs.h> 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_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_gt(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_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 <= C . Y <= z
  fd_poly_eq_k(int C[], fd_int Y[], int n, int k)	C . Y = k
  fd_poly_ne(int C[], fd_int Y[], int n, fd_int z)	C . Y != z
  fd_poly_ne_k(int C[], fd_int Y[], int n, int k)	C . Y != k
  fd_knapsack2(fd_int X[], fd_int Y[], int n, fd_int z)	z <= X . Y <= z

  fd_exactly(fd_int X[], int n, int c, int k)		 #{ i | X[i] = k } = c
  fd_exactly_var(fd_int X[], int n, fd_int y, int k)	 #{ i | X[i] = k } = y
  fd_exactly_vars(fd_int X[], int n, fd_int y, fd_int z) #{ i | X[i] = z } = y

(A . B is the dot product of A and B.)

** Optimisation

  fd_min(fd_int x)	Minimise the value of x
  fd_max(fd_int x)	Maximise the value of x


* Miscellaneous

Use `ident <application>' (if available) to find which compilation
options were used for compiling the application.