Constraint Subsystem CSS

Constraint Subsystem (CSS)

Since its earlier days Mozart was conceived to support multiple programming paradigms and constraint programming (CP) is just one of them. The MVM was developed with this functionality in mind and this was a very good decision. The problem is that CP has continued to evolve in ways that the current implementation can not follow anymore. Specialized libraries providing constraint programming functionality have emerged but they require their users to express models in a very low level language.

The main architects of the constraint system support present in the current implementation of Mozart are Gert Smolka and Christian Schulte. The last one being one of the authors of Gecode, a very efficient and state of the art library for constraint programming. Both, the Gecode design and the current MVM share fundamental design concepts that make it possible for both systems to be integrated. Having Gecode as the Mozart constraint subsystem in the new VM has several advantages:

• Gecode development is decoupled from Mozart. Gecode is a library with its own development team and is highly specialized in providing good constraint programming abstractions. As a consequence, new developments in Gecode will be easy to integrate to Mozart.

Requirements from the new CSS

The new VM must provide support for the following use cases.

• Using propagators, branchers and search engines available in Gecode.
• Search engines and branchers can be written also in Oz.

We have to also take into account:

1. The interface between the CSS and the VM must be simple enough to allow new releases of Gecode to be adopted by Mozart with minimal changes.
2. Parallel search support through the distribution subsystem. At this point we have to make the distinction between two kinds of parallel search. The first one is already supported by Gecode and is the ability to take advantage of multicore CPUS during the search. The second one is at another level and is the use of the DSS to start computations (that perform the search) on other sites. The last one is supported in the current Mozart implementation (version 1.3.1) but is not supported by Gecode.
3. Optionally, it should provide support for combinators. This is not a primary requirement so it does not have a high priority.

Road map

We devise the following tasks that need to be done to obtain the integration between the MVM and Gecode that we desire. These tasks are divided in two main groups, the first one concerns to the development of the layer that will glue the two systems; and the second one is the support that is required in the emulator for them to interact smoothly.

Glue layer

1. Design and implement a generic search engine in Gecode that is aware of the existence of the MVM.
2. Design and implement a generic brancher that is also aware of the MVM.
3. Provide built-ins that can post all the Gecode propagators from Mozart variables.

These three things will provide points of interaction between the MVM and Gecode. The first one for instance is going to handle how search engines are created and how constraint propagation is scheduled with thread execution. This will also provide the support for Oz specified search engines. The second point opens the possibility of provide heuristics to the search engine that will be written in Oz. For the third point we need that the addition of new constraints to Gecode do not involve too much work from the development of Mozart to make them available.

More details can be found here.

MVM support

Progress

So far we have devised a possible integration of the propagators but the branchers and the search engines integrations need to be analyzed. There is already an implementation of this in the Mozart repository. This implementation handles the cases in which Gecode is used for propagation only.

People involved

• AVISPA
• Gustavo Gutierrez
• Yves Jaradin