Constraint Programming model representation in NDL

2018-10-12

Features

NDL is a DSL written in Prolog, compiled to normal Prolog code. To compile a NDL model, one should import noodle module and then use one of predicates ndl/2 or ndl/1 (with default options). The first argument is a SWI-Prolog dictionary with three optional parameters:

• mode (stochastic/exhaustive, default exhaustive) - defines if model should be queried in a deterministic or random manner.
• debug (true/false, default false) - when true temporary facts are not retracted.
• namespace (<module-name>, default user) - swi-prolog namespace where the model facts would be affected. Second argument is a Prolog query, that builds the model.

Every model consists of:

• variables indexed by integers' tuples (mimicking multidimensional arrays) - define_variable/3
  • user can mark variable as fixed to hint the neighborhood generator variable should be left as it is - fix_variable/1
• constraints defined on the pairs of variables - define_explicit_constraint/2 if defined explicitly by list of pairs or define_constant/1 if defined by query
  • (experimental) user can reify constraint, which creates a corresponding 1d-array of boolean variables corresponding to the constraints - reify_constraint/1. Then, he can query corresponding variables by pointing the constrained pair of variables - get_reified_variable/3
• constants:
  • integers: may be used as ranges boundaries - define_constant/2
  • ranges of form <integer>..<integer>: may be used as domains or index sets for variables - define_constant_range/3
  • every constant used in the model creates a new constant, even if it's not named explicitly
  • every use of constant is tracked and stored in the model, so the neighborhood generator knew "type" of the constant and where can it be used. In case constant wasn't used directly in the model, user should enter possible uses manually.

To serialize the model, one should use serialize/1 with argument being the name of the file (without extension.

Limitations

• domains have to be ranges (no holes)

Examples

The SWI-Prolog based prototype is available in the noodle-prolog directory. There is one basic example available for now. To run it, write from the noodle-prolog directory:

./run_example.sh nqueens

Then you can check examples/nqueens.ndl to see ndl model of the basic 8-queens problem.#