QCNs and Benchmarks

In this page, we present several models to generate random QCN. Before, we present a XML file corresponding to a QCN. Then we give the different models to generate random instances.

As we have noted, each algebra is represented by a XML file which contains the basic relations and the operations over the algebra.

To facilitate the presentation of the XML file corresponding to the QCN, we use an extern DTD (Document type definition) is used to define the legal building blocks of an XML document. It defines the document structure (to express a Constraint Network) with has list of legal elements. Based on this DTD, we can define XML files containing an instance of QCN. These files can be used by the tools of QAT. A QCN XML file is composed from several parts:

• The first part contains the general information about the instance (its name, its variables number, its constraints number, a reference to the used algebra and comments about this instance).
• The second one contains the variables of the instance. Each variable is defined by its unique Id.
• The third part contains the constraints of the instance. In the QCN, the graph corresponding to the instance is complete, then we have nbvariables^arity of the used algebra. Each constraint is defined by:
  • A set of variables.
  • A set of a basic relations.

Now, we will present some models to generate QCNs instances.

last update: 15 jan. 2006.