DECorum stands for Deduction-based constraint relaxation management ¹ . It is an explanation-based constraint solver i.e. a constraint solver that can provide and use explanations (as defined in the introduction page. DECorum is actually a set of solvers written in different languages (see the table below). The point was to demonstration the realisability of an explanation-based solver. It has been developped by Narendra Jussien during its PhD thesis in order to illustrate his work.

DECorum is an event-based constraint solver. That part (constraint solving) is not sophisticated: no delaying of costly propagations, no collapsing of similar events, no optimisation, no sophisticated search ... The point in DECorum is to make use of explanations.

DECorum handles three kinds of variables (all parameterized by the concrete type of stored values):

• DECcompactVar<Type>: variables that are managed through their lower and upper bound.
• DECdiscreteVar<Type>: variables that are managed through their enumerated domain (classical variables for CSP).
• DECdiscreteOrderedVar<Type>: DECdiscreteVar with the hypothesis that there exists a complete order on the stored values.

DECorum handles different constraints (all providing explanations while solving):

• all the basic arithmetic constraints (C++ operators being redefined in order to ease code writting) including a linerar sum of variables.
• binary constraints expressed with the list of allowed tuples (à la CSP). Two constraints are provided: one for each of the associated propagation algorithms AC4 [Mohr and Henderson, 1986] and AC6 [Bessière, 1994].
• Two generalized allDifferent constraints [Régin, 1994] (with fixed or not numbers of occurrences for each value)
• Some scheduling-related constraints:
  • precedence constraints
  • unary resource handling constraints (the propagation here is done using [Carlier and Pinson, 1989] algorithms).

#include <DECorum.h> // DECorum is a C++ library 
#include <GCC\DECgcc.h> // Access to the alldiff constraint 

int main() {
   DECinit(); // Initializing DECorum
   DECcredits(); // Copyright information
   
   DECdiscreteOrderedVar<int> a(1, 26, "a"); // Variable declaration (min, max, name)
   ...
   DECdiscreteOrderedVar<int> z(1, 26, "z"); 

   vector<DECdiscreteOrderedVar<int>*> alpha; 
   alpha.push_back(&a), alpha.push_back(&b), ..., alpha.push_back(&z);
   
   DECstartTimer(); // starting a timer
   DECpost( DECallDiff(alpha) ); // posting an alldifferent constraint
   
   DECpost(b + a + l + l + e + t          ==  45); 
   DECpost(c + e + l + l + o              ==  43); 
   DECpost(c + o + n + c + e + r + t      ==  74);
   ...
   DECpost(v + i + o + l + i n            == 100);
   DECpost(w + a + l + t + z              ==  34)

   // Enumerating the alpha list using the minDomDeg heuristic
   DECenumeration(alpha, DECminDomDeg); 
   DECstopTimer(); // stopping the timer !
   
   DECout() << "Solution ... " << endl;
   DECout() << a << b << c << ... << z << endl; 
   
   DECout() <<  "Solve needed " << DECgetStat(DECcpu) << " ms " << endl;

   DECbye(); // Clean DECorum shutdown
   return 0; 
}

Finally, of course, DECorum handles explanations:

• providing the DECexplain for handling and storing explanations
• providing contradiction management tools
• providing constraint posting tools (normal constraints, weighted constraint - subject to relaxation and indirect constraint).

As you can see in example 1, DECorum makes an heavy use of the Standard Template Library.

The constraint solver is very simply coded using a propagation queue (with no event abstraction or reduction). Each event is propagated to all the related constraints seeking for new events.

Here is the overall architecture of DECorum:

Variables and constraints are organized as follows:

DECorum has been used for internal developments at the École des Mines de Nantes. First versions of MAC-DBT and Path-Repair were tested with DECorum.

A software tool exists that demonstrates DECorum capabilities: dynSPS which has it own dedicated page on this site. It is available for download but beware it is in French !

go to the dynSPS page

DECorum is not anymore supported nor available. It was a great tool to test ideas but it suffered from several drawbacks:

• A too simple constraint solver was used: no delaying of costly propagation algorithms, no event-related propagation functions, ...
• A too simple search mechanism: no possible definition of new strategies, ...
• A too heavy use of STL leading to poor overall performance.