B-Prolog - CLP(FD)

CLP(FD)

Like many Prolog-based finite-domain constraint solvers, B-Prolog's finite-domain solver was heavily influenced by the CHIP system. The first fully-fledged solver was released with B-Prolog version 2.1 in March 1997. That solver was implemented in an early version of AR, called delay clauses. During the past decade, the implementation language AR has been extended to support a rich class of domain events (ins(X),bound(X),dom(X,E), and dom_any(X,E)) for programming constraint propagators and the system has been enriched with new domains (Boolean, trees, and finite sets), global constraints, and specialized fast constraint propagators. Recently, the two built-ins in/2 and notin/2 have been extended to allow positive and negative table (also called extensional) constraints.

Thanks to the employment of AR as the implementation language, the constraint solving part of B-Prolog is relatively small (3800 lines of Prolog code and 6000 lines of C code, including comments and spaces) but its performance is very competitive. The AR language is open to the user for implementing problem-specific propagators. For example, the following defines a propagator for maintaining arc consistency for the constraint X+Y #= C. Whenever an inner element Ey is excluded from the domain of Y, this propagator is triggered to exclude Ex, the counterpart of Ey, from the domain of X. For the constraint X+Y #= C, we need to generate two propagators, namely, 'X_in_C_Y_ac'(X,Y,C) and 'X_in_C_Y_ac'(Y,X,C), to maintain the arc consistency. Note that in addition to these two propagators, we also need to generate propagators for maintaining interval consistency since no dom(Y,Ey) event is posted if the excluded value happens to be a bound. Note also that we need to preprocess the constraint to make it arc consistent before the propagators are generated.

'X_in_C_Y_ac'(X,Y,C),var(X),var(Y), {dom(Y,Ey)} => Ex is C-Ey, domain_set_false(X,Ex). 'X_in_C_Y_ac'(X,Y,C) => true.