The CSP Library

The CSP Library can be used to represent and solve Constraint Satisfaction Problems, experiment with new algorithms, do performance measurements, etc.

This is edition @value{EDITION}, for CSP Library version @value{VERSION}.

1. Introduction		An introduction to the CSP Library.
2. Distribution		How to get the latest distribution.

3. Architecture		The architecture of the library.
4. Representation		How to use the library.
5. Tools		Auxiliary tools provided by the library.
6. Examples		Various examples.
7. Miscellaneous coding issues
8. Limitations		Known limitations.
9. Bugs		How to report a bug.

1. Introduction

The CSP Library is a set of classes that can be used to efficiently represent and solve Constraint Satisfaction Problems (CSPs).

This library is not a general purpose solver. It doesn't support many features that are useful in representing real life problems (like continuous domains, intervals, n-ary constraints, composite representations, etc). It is however an useful test-bench for experimenting with new algorithms and ideas (including search parallelization), do performance measurements, etc. In time, some of the missing features might be added, but currently this is a low priority.

2. Distribution

The CSP Library is "free software"; this means that everyone is free to use it and free to redistribute it on certain conditions. The CSP Library is not in the public domain; it is copyrighted and there are restrictions on its distribution, but these restrictions are designed to permit everything that a good cooperating citizen would want to do. What is not allowed is to try to prevent others from further sharing any version of the CSP Library that they might get from you. The precise conditions are found in the GNU General Public License that comes with the CSP Library.

The easiest way to get a copy of the CSP Library is from someone else who has it. You need not ask for our permission to do so, or tell any one else; just copy it. If you have access to the Internet, you can get the latest distribution version of the CSP Library from `http://hulubei.net/tudor/csp'.

You may also receive the CSP Library when you buy a computer. Computer manufacturers are free to distribute copies on the same terms that apply to everyone else. These terms require them to give you the full sources, including whatever changes they may have made, and to permit you to redistribute the CSP Library received from them under the usual terms of the General Public License. In other words, the program must be free for you when you get it, not just free for the manufacturer.

3. Architecture

This section describes the basic concepts behind the implementation of the CSP Library.

3.1 Basic Concepts		Basic concepts - Decompositions and Filters.
3.2 Solving constraint satisfaction problems
3.3 Memory Management		Memory management issues.

3.1 Basic Concepts

The CSP Library implements search algorithms by combining decomposition and filtering algorithms (filters).

We are referring to the decomposition algorithm as that part of the search that decomposes the problem into sub-problems. The filtering algorithm is that part of the search that takes care of consistency propagation or arc consistency restoration. Since conceptually these are completely different classes of operations and since many combinations of decomposition and filtering algorithms yield well known search algorithms, it is worth making the distinction.

This is a partial list of decomposition and filtering algorithms and the result of their combination:

Decomposition algorithms:

- BASIC - NC - MAC - IDC - IDC-MAC

Filters:

- Backward Checking (BC) - Forward Pruning (FP) - Arc Consistency-X (AC-X)

Resulting search algorithms:

- BASIC + BC = backtracking - BASIC + FP = forward checking - NC + AC-X = NC - MAC + AC-X = MAC-X - IDC + AC-X = IDC-X - IDCMAC + AC-X = IDCMAC-X

Although unusual, sometimes search algorithms are based not on one, but two (or maybe more) decomposition algorithms. One such example is IDC-PDS, which based on an estimation of the size of the sub-problem to solve decides whether to continue using an IDC-based decomposition or to further decompose the problem using another decomposition algorithm (BASIC, NC, MAC, etc).

The CSP Library provides a general mechanism for dealing with such requirements. It is possible to create a chain of decomposition algorithms, each of them yielding control to the next one in the chain, when appropriate. The csp::Driver class implements this mechanism. It keeps a list of registered decomposition algorithms, and invokes them at each depth of the search according to the following policy:

• If the current decomposition algorithm yields control voluntarily and it is not the last one in the chain, the next one in the chain is started.
• Otherwise, control goes back to the first decomposition algorithm in the chain.

Note that each decomposition algorithm knows whether or not it is connected to a driver. If it is, instead of simply making recursive calls to solve each of the sub-problems generated at the current depth, it calls the driver and allows it to select another decomposition mechanism (if necessary, i.e. if the current one is willing to yield control).

The csp::Driver class takes care of propagating, mixing, and accumulating statistics computed in different stages of the search by different decomposition algorithms. It offers to the outside world an interface that is similar to the one provided by csp::Decomposition.

The library imposes no restrictions on the ordering heuristics (See section 4.8 Variable and value ordering heuristics.) and filters that a decomposition algorithm can use when it is used through a driver. However, you should be aware that some combinations simply do not make sense. Some filters/heuristics look at the entire problem in the constructor and then work incrementally, by considering only those parts of the problem that have changed. That constructor will only be called once (when the filter/heuristic object is created) and therefore subsequent invocations might present the filter/heuristic with a problem whose modification have not been tracked. The safest thing to do is use the same filter for all the decompositions in the driver's chain. Heuristics are usually less complex and therefore it is possible most of the time to specify different heuristics for each decomposition, but you should keep in mind that when a heuristic tracks changes in the problem, that's no longer possible.

3.2 Solving constraint satisfaction problems

In order to use the CSP Library to solve problems, four major steps need to be accomplished.

The first one is to represent the problem using the data structures provided by the library. That is, defining values, variables, constraints and the encapsulating problem as objects derived from the corresponding basic classes defined by the library in the csp namespace.

The second step is the selection of a decomposition algorithm. The algorithm is not propagating constraints or restoring arc consistency itself - it uses the services of the filtering algorithm (described below) to do that - it just decomposes the problem into sub-problems. The CSP Library comes with a set of decomposition algorithms (csp::decompositions::Basic, csp::decompositions::NC, csp::decompositions::MAC, csp::decompositions::IDC (with a few variations, like csp::decompositions::IDCMAC)), but you can write your own algorithms by deriving from csp::Decomposition. Of course, you need to respect the interface defined by csp::Decomposition as well as the interface with the filtering algorithms derived from csp::Filter.

The third step is the selection of a filtering algorithm (a filter). Depending on its nature, the filter will either propagate constraints (backward checking or forward pruning) or restore arc consistency (csp::filters::ACX). The CSP Library provides a set of filters that you can use (csp::filters::BC, csp::filters::FP, csp::filters::AC1, csp::filters::AC3), but you can write your own filters by deriving from csp::Filter.

Once these steps have been completed, solving the problem is as simple as calling the search() function of the decomposition algorithm. For the Queens problem solved with the csp::decompositions::Basic decomposition and the csp::filters::BC filter, the last two steps look like this:

Queens::Problem p(8); csp::jumpers::Chronological jumper(p); csp::filters::BC filter(p); csp::decompositions::Basic decomposition(p, filter, jumper); // Select value ordering heuristics. See below. // Do the search. if (decomposition.search(Queens::callback) == 0) cout << "No solutions" << endl;

where Queens::callback is the function that is called every time a solution is found. When invoked, Queens::callback should return true if the search should continue (i.e. look for another solution), false otherwise.

The first three steps are mandatory if you want to solve a problem. However, a good heuristic (or set of heuristics) is usually necessary to actually solve the problem efficiently. The last step consists of the selection of a set of variable and value ordering heuristics (See section 4.8 Variable and value ordering heuristics.).

decomposition.registerHeuristic(*new csp::heuristics::variable::MinDomain(p)); decomposition.registerHeuristic(*new Queens::MinValue(p));

3.3 Memory Management

Memory management is pretty straightforward. Values, variables and constraints are allocated in the constructor of the problem you define (by deriving from csp::Problem - see Queens::Problem in the `Queens.h' file for an example). The deallocation is done automatically in csp::~Problem for performance considerations. For everything else, it is your responsibility to deallocate whatever you allocated, as it is customary in C++.

4. Representation

A CSP can be viewed as a collection of values, variables and constraints. Each variable has a domain of values, and a list of constraints in which it is involved. Each constraint has a list of variables that are involved in that constraint (See section 8. Limitations.).

As we will see in the following sections, the library represents values as objects derived from csp::Value, variables as objects derived from csp::Variable, constraints as objects derived from csp::Constraint, and problems as objects derived from csp::Problem. Each value, variable, and constraint has an id that is unique within a problem and can be obtained by calling the appropriate id() function.

4.1 Naming conventions
4.2 Transferring data		Transferring data across machines.
4.3 Representing values
4.4 Representing domains of values
4.5 Representing variables
4.6 Representing constraints
4.7 Representing problems
4.8 Variable and value ordering heuristics
4.9 Writing your own decomposition
4.10 Writing your own filter
4.11 Details about the library internals

4.1 Naming conventions

The CSP Library takes advantage of the namespace support in recent versions of the GNU C++ Compiler. All the definitions provided by the library are inside the csp namespace (or inside other namespaces defined inside it) and therefore you need to explicitly specify the correct namespace whenever you need to access something (base classes, function templates, etc.). Alternatively, you can use the using namespace construct.

A typical user-defined CSP variable (provided you need something more fancy than the usual csp::Int) looks like this:

namespace Queens { class Variable : public csp::Variable { ... }; } // namespace Queens

Note the definition of the Queens namespace. While this can be omitted in a small program, without it you will pollute the global namespace, which is not a good idea. All the examples provided with the CSP Library are defined inside their own namespace.

4.2 Transferring data

4.3 Representing values

Values in the CSP Library are represented as objects derived from csp::Value. The CSP Library comes by default with a set of classes (csp::Int, csp::Long, csp::Float, csp::Double) that are wrappers for the basic C/C++ values (with the exception of the csp::Long class which represents a 64bit value regardless of the machine architecture if --enable-long-long is given to the ./configure script when configuring the library). Using these classes is highly recommended.

In your problem representation, you can either use these predefined value classes, or define your own. Here is the definition of csp::Int, as found in the CSP Library source code. If you need to write your own class to represent the problem's values, you can use it as an example.

class Int : public Value { private: int m_value; public: Int() : m_value(0) {} Int(const int v) : m_value(v) {} // Copy constructor. Int(const Int& v) : Value() { m_value = v.m_value; } // Assignment operator. Int& operator=(const Int& v) { Value::operator=(v); m_value = v.m_value; return *this; } operator int() const { return m_value; } virtual ostream& print(ostream& os) const { return os << m_value; } };

4.4 Representing domains of values

Each csp::Variable contains a domain of values. The values are stored (as pointers) in an object of type csp::Domain, which is derived from the STL container std::list<csp::Value *>. As a result, all the operations provided by the list container are also available in the csp::Domain object, allowing constant time insertion and removal of elements at the beginning or the end, or in the middle.

4.5 Representing variables

Variables in the CSP Library are represented as objects derived from csp::Variable. Each variable contains a domain of values (in fact a pointer to a csp::Domain object), as well as a vector of pointers to constraints (csp::Constraint *) in which the variable is involved.

A variable can be in two states: instantiated and or not instantiated. Instantiation is done explicitly in the decomposition algorithm (when a value is assigned to it), while de-instantiation is done automatically when the algorithm backtracks. Note that while instantiation clearly implies that the domain of the variable contains just one value, the fact that the domain of a variable contains just one value doesn't necessarily mean that the variable is instantiated - it might be that its domain has been reduced to one value. This is an important distinction, if you need to make sure that a variable is instantiated you should use isInstantiated().

By default the CSP Library provides a set of classes (csp::Int, csp::Long, csp::Float, csp::Double) that are wrappers for the basic C/C++ types and implement the stream-based constructor and the write() function. Using these classes is highly recommended.

namespace Queens { typedef csp::Int Variable; } // namespace Queens

If your needs are more sophisticated (as it is the case with the Queens example, or even more so with the Random problem generator example), you can define your own variables:

namespace Queens { class Variable : public csp::Int { private: int m_index; public: Variable(int index); Variable(csp::isstream& iss); csp::osstream& write(csp::osstream& oss) const; int index() const; }; } // namespace Queens

4.6 Representing constraints

Constraints are represented as objects derived from csp::Constraint. Each constraint contains a vector of pointers to variables (csp::Variable *) involved in the constraint (See section 8. Limitations.). It provides functions to add new variables to the constraint, iterate through the set of variables, etc.

The only requirement when you derive from csp::Constraint is that the pure virtual function isSatisfied() be defined. This function is called whenever the propagation algorithm needs to know whether or not the constraint is satisfied by the current instantiations of variables.

This is an example of how to declare a new constraint:

namespace Queens { class Constraint : public csp::Constraint { public: Constraint() : csp::Constraint(); Constraint(csp::isstream& iss) : csp::Constraint(iss); bool isSatisfied() const; }; }

When defining a new constraint, make sure that in the isSatisfied() function you increment m_checks, a 64bit integer that counts the number of constraint checks for that constraint.

4.7 Representing problems

The CSP Library represents problems by deriving from csp::Problem, the superclass of all CSPs.

csp::Problem acts as a database of variables and constraints. Each problem contains two hash tables, one with pointers to variables (csp::Variable *), and one with pointers to constraints (csp::Constraint *). The hashing is based on the object ids.

When a new problem is defined, the constructor should create variables and constraints and register them using the provided add() functions.

4.8 Variable and value ordering heuristics

The library implements ordering heuristics as objects derived from csp::VariableOH and csp::ValueOH.

The decomposition algorithm keeps two lists of pointers, one to objects implementing variable ordering heuristics and the other one to objects implementing value ordering heuristics.

Each ordering heuristic object must provide a select() function that is going to be used by the decomposition algorithm to actually select variables/values according to the heuristics in place. select() receives a list of variables (or domain of values) and returns a list/domain containing only the preferred ones.

Heuristics are called in turn, depending on the order in which they have been registered. The select() function of the first heuristic in the list gets a list containing all the unassigned variables and returns a list of "preferred" variables among those on the list. The resulted list is passed on to the next heuristic, and so on until either the list of "preferred" variables shrinks down to one element or we run out of heuristics, in which case the first variable in the resulting list is selected. A similar algorithm is used for the selection of values.

The CSP Library provides a few general purpose variable and value ordering heuristics:

• csp::heuristics::variable::Lexical - variables are selected in lexical ordering
• csp::heuristics::variable::Random - variables are selected in a random order
• csp::heuristics::variable::MaxDegree - the maximum degree variable is selected
• csp::heuristics::variable::MinDomainDegree - the variable with the minimum domain/degree ratio is selected
• csp::heuristics::variable::MinDomain - the minimum domain variable is selected
• csp::heuristics::value::Lexical - values are selected in lexical ordering
• csp::heuristics::value::Random - values are selected in a random order
• csp::heuristics::value::MinInconsistency - the minimum inconsistency count value is selected

New ordering heuristics can be defined by the user by deriving them from the corresponding base class (csp::VariableOH or csp::ValueOH).

For instance, for the Queens example the best results are obtained by combining two heuristics: csp::heuristics::variable::MinDomain and Queens::MinValue, where Queens::MinValue is defined in the `Queens.h' example since it is specific to the Queens problem.

4.9 Writing your own decomposition

The best thing to do when writing your own decomposition is to start from an existing one, preferably from the csp::decompositions::Basic decomposition which is the simplest one and therefore the easiest to understand. There are however a few things that you need to understand.

4.9.1 The .h file
4.9.2 The .cc file

4.9.1 The .h file

A decomposition object doesn't support copy constructors and assignment operators. Therefore, you need to declare them private, such that any attempt to use them will result in a compiler error. Although this is not mandatory, it is a good practice and very easy to do. Copy these two declarations from `src/decompositions/Basic.h' and change the class name.

private: // Copy constructor & assignment operator. Not supported. Basic(const Basic&); Basic& operator=(const Basic&);

The constructor should get three parameters, a csp::Problem, a csp::Filter, and a csp::Jumper (all references) and pass them to the super class (csp::Decomposition) along with the name of the algorithm (say "NC decomposition").

The implementation should contain one virtual function, called decompose(). This function will be called by the super class' search() function after all the initializations are performed. This includes reseting various counters, initializing the filter, inserting all the variables in the list of uninstantiated variables, etc. If you want to figure out what is going on there you can look at the code in `src/kernel/Decomposition.cc'. Look for the search() function.

4.9.2 The .cc file

Now that we're done with the header file, we can start looking at the actual implementation (the decompose function). Since any decomposition inherits from csp::Decomposition, it is a good idea to take a look at that class first and familiarize yourself with its structure.

First, you will have to select a variable with selectVariable(). After that you're on your own - just decompose the problem in whatever way you want. The things you need to remember are:

The csp::Decomposition super class keeps in m_filter a reference to the filter in use. Whenever you want to filter the problem you need to call the filter's propagate() function. The return value of propagate() is true or false depending on whether or not the filtering succeeded.

There are two ways in which a problem can be filtered. One of them is through propagate(), the other is through propagateAndSearch().

propagate() prunes the domains of the uninstantiated variables and then returns, leaving the domains of the variables modified (if successful). You can then perform some additional processing at the current depth of the search and do some additional propagations if you want. This is suitable for instance for MAC, where each value that has been tried is removed from the domain of the current variable before proceeding with the recursive search, and the effects of those removals are cumulated.

propagateAndSearch() prunes the domains of the uninstantiated variables, performs a recursive search, then restores everything and returns.

The decomposition is usually done around a variable. Your decomposition selects a variable and decides how to decompose a problem based on the domain of that variable or some other information (while that is almost always the case, the CSP Library doesn't restrict you here in any way). You can select a variable by calling selectVariable(). This function will pick an uninstantiated variable based on the current variable ordering heuristics, if any (if there are no variable ordering heuristics, the an arbitrary uninstantiated variable will be selected).

Some decomposition algorithms (Basic, MAC) work by instantiating the selected variable, in turn, to each value in its domain and solving the resulting sub-problem recursively. Other decomposition algorithms (NC) split the domain of a variable in several smaller sub-domains and then solve the resulting sub-problems recursively.

The subtlety here is that in the first case, the selected variable is instantiated and therefore should not be in m_vlist when solving the sub-problems recursively (remember that m_vlist is the list of uninstantiated variables). In the second case, since we only split the domain of the variable, and the resulting parts might contain more than one value, the selected variable will not be instantiated and therefore must be reinserted into m_vlist.

Of course, if you figure that a sub-domain contains just one value, you can instantiate the selected variable to that value before solving the corresponding sub-problem. In that case you should not unselect the variable. Also remember that for a variable to be considered instantiated you have to actually call an instantiate() function for that variable. The simple fact that the domain of a variable shrinks down to one value doesn't mean that the variable will be considered instantiated.

The next thing you need to know is the role of canContinue(). This function should be called before every new recursive search to check whether the search should proceed or not. Reasons for not continuing include timeouts, explicit requests to stop from the callback, etc.

As mentioned before, once a variable is selected, decomposition can be done around its domain, by instantiating the variable, in turn, to each of its values. The order in which the values are tried can have a dramatic effect on the efficiency of the search. You can select a value from the domain of the selected variable by calling selectValue() with the domain of the variable as a parameter (the domain of a variable can be obtain by calling the variable's domain() function). Once a value is selected it is removed from the domain. As with the selection of a variable, the selection of a value is done based on the heuristics in place). When you're done with it, you have to unselect it by calling unselectValue() with the domain and the value as parameters.

When using decomposition chains, the driverSearch() call ends up being a recursive call to decompose(). The reason we're not calling decompose() directly is that the library implements support for chains of decomposition algorithms. driverSearch() implements that, but in the usual case when there is only one decomposition in the chain, driverSearch() calls decompose() for that decomposition.

4.10 Writing your own filter

As with the decomposition algorithms, the filters do not support copy constructors and assignment operators. Therefore they should be made private, to trigger compiler errors when used by mistake.

private: // Copy constructor & assignment operator. Not supported. BC(const BC&); BC& operator=(const BC&);

If the filter doesn't support the constraint activation/deactivation optimizations, then you need to reimplement activateConstraints() and deactivateConstraints() as empty functions.

virtual void deactivateConstraints(Variable&) {} virtual void activateConstraints(Variable&) {}

A good example of a filter that doesn't work with this optimization is backward checking (csp::BC). This filter works by verifying after each instantiation that the instantiation of the currently selected variable is consistent with the instantiations of all the previously instantiated variables. Thus, if we remove the back constraints, csp::BC will not work.

The core of the filter is the propagate() function. Its parameters are the list of the uninstantiated variables (usually csp::Decomposition::m_vlist) and the list of variables that have been modified at the current depth in the decomposition algorithm. The job of the propagate() function is to try to verify that the problem is still consistent, i.e. that each constraint in the problem can still be satisfied. propagate() should return true on success and false on failure.

The most important way to remember when implementing a filter is that you need to call saveDiffs() for all the uninstantiated variables before you do anything that modifies them. If the filtering succeeds (i.e. arc consistency can be restored) you need to call postponeDiffs() for all the uninstantiated variables. The reason for that is that you want the changes performed by the filtering to be effective when you solve the sub-problem in the decomposition. After that, restoreState() will restore the domain of the variables. If the filtering fails, then you need to call restoreDiffs() to restore the domain of all the variables before returning.

Note that if a filter is called and all the variables are instantiated, the filter should be able to say whether or not we have a solution.

4.11 Details about the library internals

4.11.1 How propagation works
4.11.2 Variable types
4.11.3 Variable transitions

4.11.1 How propagation works

There are two ways in which a propagation can occur at a given depth in the decomposition. One is by calling propagateAndSearch(), which will filter the problem, then perform a recursive decomposition/search. After the recursive search, The domains of the variables are restored to what they were before the call. The propagation performed into propagateAndSearch() is what we call a restored propagation.

The second way in which a propagation can occur is by means of a direct call to propagate(). Such a call will filter the problem and, unless unsuccessful, will return *without* restoring the domains of the variables - the modifications performed are permanent for the current depth. We call that an unrestored propagation. The only way to restore the domains of the variables is by returning to the previous depth of the decomposition (which will actually restore the domains of all the variables to what they were at the previous depth, not just before the last successful unrestored propagation). Successive calls to propagate() on a given depth (again, if successful) can perform additional changes to the domains of the current and future variables. All those changes are accumulated and will be restored upon return from decompose(). That is, there is no way you could differentiate between (or have access to) the changes performed by an individual unrestored propagations.

The library considers the changes made by succesful unrestored propagations as being permanent at the current depth, and even though you could in theory implement your own mechanism for keeping track of the changes made by each succesful unrestored propagation, such a thing will confuse the library and result in an undefined behavior.

A final note - unsuccessful propagations always undo whatever changes they made.

4.11.2 Variable types

instantiated variable

A variable whose domain has been reduced to one value and has successfully passed through a propagation.

past variable

A variable that has been modified at a previous depth (but has not necessarily been instantiated).

current variable

A variable that has been modified at the current depth (possibly instantiated). If a variable has been modified at the current depth and a successful unrestored propagation has been executed, then that variable is considered a past variable since its domain cannot be restored to what it originally was at the current depth without backtracking (returning at the previous depth).

future variable

A variable that is not instantiated - i.e. we still have to work on it.

Note that as weird as it might sound, a variable can be at the same time past, current and future. That is because nothing in the library forces you to instantiate a variable the first time you touch it. The Network Consistency decomposition (NC) is a very good example: suppose at depth 0 you choose to decompose around variable X, which has a domain of size 8; you split its domain in half, then decompose recursively on the first half, then on the second; at depth 1, you pick X again - this time its domain is 4; you split it in half, then decompose recursively. As you can see, just before going to depth 2, X is a past variable (it has been modified in the past), it is a current variable (it has been modified at the current depth), and it is a future variable (it will be modified in the future - we're not yet done with it since its domain size will be 2 at depth 2).

One rule that you have to respect when decomposing a problem is that THE SIZE OF THE DOMAIN CAN ONLY DECREASE. I can't emphasize this enough - on a given depth, you cannot add to the domain of a variable a value that was not there at the time decompose() was called for that depth. You are allowed to do whatever you want with the domain of the variable inside decompose(), but at the time you call propagate(), propagateAndSearch() or return from decompose(), the domain of each variable should contain all the values it contained at the time decompose() was called. Moreover, if successful unrestored propagations occurred at that depth, the domains have to be restored to whatever values they had after the last successful unrestored propagation (i.e. you cannot place back into the domain of a variable any value that has been permanently removed from it at the current depth). Permanent changes are just that: PERMANENT.

So, going back to the issue of domain modifications - those modifications are noticed by the library every time you call propagate() of propagateAndSearch(). In-between you can do whatever you want, but once you're ready to return, call propagate(), or call propagateAndSearch() make sure the domains of all the variables respect the above rule. Also, you are not allowed to wipe out the domain of a variable.

4.11.3 Variable transitions

The following algorithm describes all the transitions possible for a variable at a given depth. Again, the library revises the states of the variables before a propagation (be it restored or unrestored).

First, an explanation of terms:

OneValue variables

OneValue refers to a variable whose domain has been reduced to a single value. It also refers to variables whose domain contained one value upon entry in decompose(), either because depth==0 and it so happens that a variable has just one value, or, more often, because the domain of a variable has been reduced to one value in the propagation performed right before decompose().

Modified variables

Modified refers to a variable whose domain has been modified at the current depth, or has been modified since the last successful unrestored propagation, but in either case it has NOT been reduced to a single value.

Unmodified variables

If there have been successful unrestored propagations at the current depth, then Unmodified refers to the state of a variable whose domain has not been modified since the last successful unrestored propagation at this depth, or was restored to what it was immediately after the last such propagation.

If there have been no successful unrestored propagations at the current depth, then Unmodified refers to the state of a variable whose domain has not been modified since decompose() was called at this depth, or has been restored to what it was then.

Since the library revises the variables in this order: OneValue, Modified, Unmodified, it follows that an Unmodified variable has at least to values in its domain (otherwise it would qualify as OneValue).

And now, the transitions and their effects on the past, current and future variable flags when the transition is detected in propagate():

OneValue -> OneValue

past flag: unchanged current flag: on->on future flag: off->off

OneValue -> Modified

past flag: unchanged current flag: on->on future flag: off->on

OneValue -> Unmodified

past flag: unchanged current flag: on->off future flag: off->on

Modified -> OneValue

past flag: unchanged current flag: on->on future flag: on->off

Unmodified -> OneValue

past flag: unchanged current flag: off->on future flag: on->off

Modified -> Modified

past flag: unchanged current flag: on->on future flag: on->on

Unmodified -> Modified

past flag: unchanged current flag: off->on future flag: on->on

Modified -> Unmodified

past flag: unchanged current flag: on->off future flag: on->on

Unmodified -> Unmodified

past flag: unchanged current flag: off->off future flag: on->on

propagate() modifies the state of the problem *without* doing a recursive search (i.e. the changes will remain in place), these flags refer to the variables as viewed from the current depth.

Note that before entering on a new search, if there are future variables whose domains contain a single value (as a result of the propagation performed in propagateAndSearch()) those variables are automatically selected/instantiated and another propagation is executed. This way the library can potentially cut the depth of the search.

When the changes are detected in propagateAndSearch(), the library revises the state of all the variables, filters the problem, and, if successful, it recursively decomposes the problem. When the recursive decomposition/search ends, the state of all the variables is restored and propagateAndSearch() returns. Even though the transitions occur at depth d they are performed in this case for the benefit of depth d+1, and the library marks the variables accordingly (i.e. compared to the transitions described for propagate(), these ones are shifted backward in time). More explicitly, the transition is between the state of the variable at depth d to the state at depth d+1.

Here the transitions are directly from the state the variable was before being revisited to the state the variable needs to be on the next depth. Basically we only care about the left side of the ->, but we show the right side as well, for completeness.

Explanatory rules:

1. Nothing is current, because we are computing the state the variable should be in *before* the decomposition has a chance to select/modify anything.

2. If a variable becomes OneValue at the current depth, it means it has been modified at the current depth and obviously will be a past variable at the next depth. It cannot be future, since we're done with it.

3. If a variable becomes Modified at the current depth, it means it has been modified at the current depth and obviously will be a past variable at the next depth. It will also be future, since it is not OneValue, i.e. we're not done with it.

4. If a variable is Unmodified at the current depth, then its past flag is unchanged. Its future flag stays on (remember that Unmodified implies that the variable has at least two values).

OneValue -> OneValue

past flag: ?->on current flag: on->off future flag: on->off

OneValue -> Modified

past flag: on->on current flag: on->off future flag: off->on

OneValue -> Unmodified

past flag: unchanged current flag: on->off future flag: on->on

Modified -> OneValue

past flag: ?->on current flag: on->off future flag: on->off

Unmodified -> OneValue

past flag: ?->on current flag: off->off future flag: on->off

Modified -> Modified

past flag: ?->on current flag: on->off future flag: on->on

Unmodified -> Modified

past flag: ?->on current flag: off->off future flag: on->on

Modified -> Unmodified

past flag: unchanged current flag: on->off future flag: on->on

Unmodified -> Unmodified

past flag: unchanged current flag: off->off future flag: on->on

Since the transitions occur at the previous depth and are detected just before going to the next depth (before the decomposition has a chance to select and modify any variable), obviously no variable will be marked current initially.

The previous set of transitions is for the case where the propagation succeeds. Unfortunately, we don't know that in advance, and anyway, it is simpler to view this as a two steps process. That is, we first update the state of the variables as if they were to remain at the same depth, do the propagation, and, if successful, complete the work by performing the transitions for the next depth:

All the variables have their current attribute turned off, and those that are OneValue or Modified will become past variables. The OneValue variables have their future variable reset.

OneValue:

past flag: ?->on current flag: on->off future flag: off->off

Modified:

past flag: ?->on current flag: on->off future flag: on->on

Unmodified:

past flag: unchanged current flag: off->off future flag: on->on

5. Tools

5.1 Monitoring resource usage
5.2 Representing arrays of bits

5.1 Monitoring resource usage

The CSP Library provides the csp::Resources class for monitoring resource usage. This class should be used to report the time spent solving the problem, the number of page faults, the amount of memory used, etc.

A typical use of the csp::Resources class would look like this:

csp::Resources r; r.start(); // Do the search. r.stop(); cout << r;

The csp::Resources object computes the difference between the process resource usage at the time stop() was called and the process resource usage at the time start() was called.

5.2 Representing arrays of bits

The csp::BitArray class implements an array of bits. While not really part of the CSP Library, csp::BitArray turned out to be useful in a number of situations where low memory usage was an important factor (See section 6.2 A random problem generator.).

6. Examples

6.1 The Queens problem
6.2 A random problem generator

6.1 The Queens problem

The Queens problem is the simplest example of a problem solved with the CSP Library. By combining the csp::heuristics::variable::MinDomain and Queens::MinValue heuristics with the Basic decomposition and a FP filter the 1000 queens problem can be solved on a PentiumII/233MHz in less than 10 minutes (provided you have the required amount of virtual memory available - about 80Mb). The 100 queens problem is solved in 0.3 seconds. In all fairness, we have to say that for this particular problem commercially available solvers (like the ILog Solver) that support n-ary constraints can do much better by representing the set of queens with an array of integers and using a single specialized constraint (all-different).

6.2 A random problem generator

The random problem generator Random generates problems according to the "fixed parameter value" model. The problem is generated based on a given constraint density and tightness, number of variables, and values per domain.

If you plan to write your own problem generator, please consider improving Random instead, by either adding more features to it or using it as a base class for other problem generators. I would be interested in extending it to be able to generate more fancy random problems.

7. Miscellaneous coding issues

7.1 Compiling code that uses the CSP Library
7.2 Using C++ casts
7.3 Using C++ iterators
7.4 Using C++ namespaces
7.5 Enforcing a predictable library behavior

7.1 Compiling code that uses the CSP Library

In order to use the CSP Library you will have to include the `csp.h' header file. This will automatically include all the other headers required (note that you will need to specify the path to the main CSP source directory). I suggest you place your code into the `examples' directory and extend the `Makefile.am' file there to compile it.

7.2 Using C++ casts

The new C++ standard declares as obsolete the old C-like cast style. The new ways of casting are cleaner and safer, and I have used them throughout the library - it would be best if you do the same. Please see The C++ Programming Language, Third Edition by Bjarne Stroustrup for details.

7.3 Using C++ iterators

Using iterators is a good practice, especially since the CSP Library relies so much on the Standard Template Library. Whenever you do so, keep in mind that for all the iterators it is more efficient to use the prefix increment/decrement operators instead of the postfix ones, because there are no temporaries involved and thus the compiler can generate better code. That is, if i is an iterator, use ++i whenever the difference between ++i and i++ is not important.

7.4 Using C++ namespaces

Polluting the global namespace is bad programming practice, so don't do it. When you want to define a new problem (say XXX) and the associated values, variables, and constraints, create a namespace called XXX and define everything inside it. You can safely name your objects Value, Variable, Constraint, and Problem without interference with the names of the base classes since those are declared inside the csp namespace. You can refer to the base classes by prefixing them with csp::. Outside the XXX namespace your objects can be referred to as XXX::Value, XXX::Variable, XXX::Constraint, etc.

7.5 Enforcing a predictable library behavior

If you want to guarantee a predictable behavior for various algorithms in the library, it is important to preserve the order of the values and variables in their corresponding lists whenever these lists are modified and later restored.

For instance, suppose a variable is involved in 3 constraints (1, 3, and 4, in that order). At some point, the library infers that constraint number 4 will always be satisfied and deactivates it. Later on, the library backtracks and reactivates it. It would be best if we not only restore the list of constraints to contain 1, 3 and 4, but also restore the original order of the constraints in the list. While this is irrelevant from a correctness standpoint, it might be important when comparing results obtained with the CSP Library with results obtained using other implementations of the algorithms, since obscure issues like this will clearly affect your results.

Guaranteeing a predictable behavior is however, inefficient and the library doesn't do it by default. If the PREDICTABLE preprocessor symbol is defined at compile time, then alternate versions of various functions in the library are used such that the predictable behavior is enforced. When PREDICTABLE is not defined (this is the default) all bets are off.

8. Limitations

This is a list of some of the current library limitations:

• No support for n-ary constraints at this time. In fact, the restriction comes from the lack of a n-ary capable filter.
• Restartable search is not implemented. It is not very important from the point of view of algorithm development, is tedious to implement, and it has to be done in each and every "decomposition" algorithm. It is unclear to me whether I should spend time implementing it.
• AC-7 is not implemented yet.

9. Bugs

Any questions, comments, or bug reports should be emailed to `tudor@hulubei.net'. Please include the full description of the problem that you encountered as well as the version number of the library.

Table of Contents

1. Introduction
2. Distribution
3. Architecture

3.1 Basic Concepts
3.2 Solving constraint satisfaction problems
3.3 Memory Management

4. Representation

4.1 Naming conventions
4.2 Transferring data
4.3 Representing values
4.4 Representing domains of values
4.5 Representing variables
4.6 Representing constraints
4.7 Representing problems
4.8 Variable and value ordering heuristics
4.9 Writing your own decomposition

4.9.1 The .h file
4.9.2 The .cc file

4.10 Writing your own filter
4.11 Details about the library internals

4.11.1 How propagation works
4.11.2 Variable types
4.11.3 Variable transitions

5. Tools

5.1 Monitoring resource usage
5.2 Representing arrays of bits

6. Examples

6.1 The Queens problem
6.2 A random problem generator

7. Miscellaneous coding issues

7.1 Compiling code that uses the CSP Library
7.2 Using C++ casts
7.3 Using C++ iterators
7.4 Using C++ namespaces
7.5 Enforcing a predictable library behavior

8. Limitations
9. Bugs

Short Table of Contents

1. Introduction
2. Distribution
3. Architecture
4. Representation
5. Tools
6. Examples
7. Miscellaneous coding issues
8. Limitations
9. Bugs

About this document

• 1. Section One
• 1.1 Subsection One-One
• ...
• 1.2 Subsection One-Two
• 1.2.1 Subsubsection One-Two-One
• 1.2.2 Subsubsection One-Two-Two
• 1.2.3 Subsubsection One-Two-Three     <== Current Position
• 1.2.4 Subsubsection One-Two-Four
• 1.3 Subsection One-Three
• ...
• 1.4 Subsection One-Four