Abscon 109 - Solving CSP instances

Abscon 109 is the solver that has been submitted to the (second round of the) 2006 Competition of CSP solvers. This solver recognizes the XML format, XCSP 2.0, used to represent CSP instances. You can see the results of the second round here.

To run Abscon (tested under Linux, but not under Windows), you have to:

  1. install J2SE 5.0 (Java 2 Platform Standard Edition 5.0) or later, if not already installed (See http://java.sun.com/)
  2. download and uncompress abscon109.tgz
  3. execute in a terminal:
    • for a single instance: java -jar abscon109.jar <configurationFileName> 1 XSax <instanceFileName>
    • for several instances: java -jar abscon109.jar <configurationFileName> <nbInstances> XSax <directoryFileName>

Here, <configurationFileName> can be:

That is to say, any configuration file that you will find in abscon109.tgz. <instanceFileName> denotes the name of an instance in format XML whereas <directoryFileName> denotes the name of a directory containing instances in format XML (in this case, <nbInstances> denotes the number of instances you want to solve, -1 for all).

Of course, you can use options for the JVM. For example, here are the options used for the competition: -Xms756M -Xmx756M -XX:PermSize=10m -XX:MaxPermSize=10m

WARNING: For some large instances, the program may be out of memory and stops suddenly. Note that you can tune the memory settings for the Java Virtual Machine with arguments Xms and Xmx. However, be careful of not choosing a too large value of Xmx (maximmum heap size) since it may destabilize the operating system. In any case, we shall not be considered as responsible for any potential damages to your computer system that will result from the execution of this program.

XCSP Tools, version 2.1.4 (November 04, 2008)

The format XCSP 2.1 allows us to represent global constraints and constraints defined in extension or in intension. You will find its desciption, as well as many series of instances, here.

The tools that are currently available from this page are:

To obtain these tools, you can download:


Parsing instances

If you want to load and parse CSP and WCSP instances represented in format ``XCSP 2.1'', you can use one of the two following parsers:

For more information about the first parser, see this link . Questions and suggestions are welcome: send an e-mail to Olivier.

The second parser is written in Java using DOM and is mainly based on the class InstanceParser.java that you will find in Tools2008.zip. To integrate your own parser in your constraint library, you can simply adapt the given code (note that you do not need to keep all classes of Tools2008.zip since for example, you can remove the method computeCostOf of the class PConstraint). Of course, questions and suggestions are welcome: send an e-mail to Christophe.


Evaluating Predicate Expressions

One difficulty with the new format is to deal with constraints represented in intension. More precisely, one must be able to evaluate any predicate expression built from the grammar introduced in format 2.1. There are at least two generic alternatives:

Here, we just quickly discuss about the former approach. If you build a postfix expression from the functional one, then it can be scanned from left to right, operands simply placed into a last-in, first-out (LIFO) stack and operators applied to the operands at the top of the stack. This is the principle used for SolutionChecker and InstanceChecker tools. The code is available in Tools2008.zip.

Of course, you can decide to adopt a more specific approach, exploiting the semantics of the operators/constraints to build propagators.

Tool SolutionChecker

This tool allows to compute the number of constraints violated by a complete instantiation of the variables of a CSP instance, or the cost of a complete instantiation of the variables of a WCSP instance. Of course, if the number of violated constraints is equal to 0, it simply means that it is a solution.

To run SolutionChecker:

Then, you obtain the different usages of SolutionChecker. Just choose one of them. The source code is available in Tools2008.zip.

For example, let us consider a file queens_4.xml containing:

	  <?xml version="1.0" encoding="UTF-8"?>
	  <instance>
	    <presentation name="?" format="XCSP 2.1"/>

	    <domains nbDomains="1">
	      <domain name="D0" nbValues="4">1..4</domain>
	    </domains>

	    <variables nbVariables="4">
	      <variable name="V0" domain="D0"/>
	      <variable name="V1" domain="D0"/>
	      <variable name="V2" domain="D0"/>
	      <variable name="V3" domain="D0"/>
	    </variables>

	    <predicates nbPredicates="1">
	      <predicate name="P0">
	        <parameters>int X0 int X1 int X2 int X3 int X4</parameters>
	        <expression> 
	          <functional>and(ne(X0,X1),ne(abs(sub(X2,X3)),X4))</functional>
	        </expression>
	      </predicate>
	    </predicates>

	    <constraints nbConstraints="6">
	      <constraint name="C0" arity="2" scope="V0 V1" reference="P0">
	        <parameters>V0 V1 V0 V1 1</parameters>
	      </constraint>
	      <constraint name="C1" arity="2" scope="V0 V2" reference="P0">
	        <parameters>V0 V2 V0 V2 2</parameters>
	      </constraint>
  	      <constraint name="C2" arity="2" scope="V0 V3" reference="P0">
	        <parameters>V0 V3 V0 V3 3</parameters>
	      </constraint>
	      <constraint name="C3" arity="2" scope="V1 V2" reference="P0">
	        <parameters>V1 V2 V1 V2 1</parameters>
	      </constraint>
	      <constraint name="C4" arity="2" scope="V1 V3" reference="P0">
	        <parameters>V1 V3 V1 V3 2</parameters>
	      </constraint>
	      <constraint name="C5" arity="2" scope="V2 V3" reference="P0">
	        <parameters>V2 V3 V2 V3 1</parameters>
	      </constraint>
	    </constraints>
	  </instance>

Then, if you run: java -cp Tools2008.jar abscon.instance.tools.SolutionChecker queens_4.xml 2 4 1 3
you obtain: nbUnsatisfiedConstraints 0

On the other hand, if you run: java -cp Tools2008.jar abscon.instance.tools.SolutionChecker queens_4.xml 2 4 1 2
you obtain: nbUnsatisfiedConstraints 3 list [C2, C5, C4]

Tool InstanceChecker

The program called InstanceChecker is a tool that allows validating and converting representations of CSP and WCSP instances. To run instanceChecker:

Then, you obtain the different usages of InstanceChecker. Just choose one of them.

For example, to use a graphical user interface, run: java -cp Tools2008.jar abscon.instance.tools.InstanceChecker gui Then, you obtain the following interface:

WARNING: For some large instances, the program may be out of memory and stops suddenly. Note that you can tune the memory settings for the Java Virtual Machine with arguments Xms and Xmx. However, be careful of not choosing a too large value of Xmx (maximmum heap size) since it may destabilize the operating system. In any case, we shall not be considered as responsible for any potential damages to your computer system that will result from the execution of this program.

You also have a simple command line usage: java -cp Tools2008.jar abscon.instance.tools.InstanceChecker <instanceFileName> <mode> {<overwrite>}
The options are the following:

Questions and suggestions about tools SolutionChecker and InstanceChecker are welcome: send an e-mail to Christophe.


Validating CSP instances

To check that some instances are valid wrt the format XCSP 2.1 you have to select one of the two first radio buttons and to select the directory where the files are located (use the Src button). Then, you can start checking by pushing the Start button. As a result, all files with suffix "xml" in the selected directory or one of its subdirectories will be checked. Hence, we advice that you put all files corresponding to the instances whose validity must be checked in a specific directory structure.

For more information about the validity of instances, see this document. The first choice (radio button) of the interface corresponds to checking general validity rules whereas the second choice (radio button) of the interface corresponds to checking general and specific 2008 competition validity rules.


Converting CSP instances

Using the third radio button, you can check the validity of some instances (only using general validity rules) and convert, if necessary, the instances into canonical form. A representation of a CSP instance is said to be canonical when domains, variables, relations, predicates, formal parameters and constraints are given standardized names. Finally, using the fourth button, you can check the validity of some instances (only using general validity rules) and convert, if necessary, the instances into canonical form and predicates into relations.

Note that InstanceChecker does not control (with mode 2) that constraints are sorted by lexicographic order of their normalized scope.

Tool InstanceShuffler

This tool allows to shuffle variables and constraints of a given instance. The interest is that you can check the robustness of your solver. If your solver has roughly the same behaviour on the same instance that has been shuffled a reasonable number of times, it means that it is quite robust.

To run InstanceShuffler:

Here, <instanceFileName> denotes the name of a file representing a CSP or WCSP instance in format XCSP 2.1, and <seed> is an integer used to initialize the pseudo-random number generator. For example, to shuffle scen11.xml using seed 1:

Then, you obtain a file whose name is:

RBGenerator 2.0 - Generating hard random CSP instances

RBGenerator is a program that allows generating random CSP instances following Model RB. For more information about Model RB, see:

RBGenerator generates random CSP instances in the XML format called XCSP 2.0. For more information about this format, see: XML Representation of Constraint Networks: Format XCSP 2.1

To run RBGenerator, you have to:

  1. install J2SE 5.0 (Java 2 Platform Standard Edition 5.0) or later, if not already installed (See http://java.sun.com/)
  2. download RBGenerator.jar
  3. run RBGenerator with the command line: java -jar RBGenerator.jar

Then, you obtain the different usages that can be used with RBGenerator:

Whith Usage 0, you obtain the following information:

Whith Usage 1, you obtain the following information:

Whith Usage 2, you obtain the following information:

With Usage 3, one can generate random instances.

The arguments are the following:

WARNING: For some large instances, the program may be out of memory and stops suddenly. Note that you can tune the memory settings for the Java Virtual Machine with arguments Xms and Xmx. However, be careful of not choosing a too large value of Xmx (maximmum heap size) since it may destabilize the operating system. In any case, we shall not be considered as responsible for any potential damages to your computer system that will result from the execution of this program.