Methods for Constructing and Solving Large Constraint Models (MCM)

A research project (number 122399) funded by Academy of Finland
Jan 1, 2008 - Dec 31, 2011

Project leader: Prof. Ilkka Niemelä

Research Personnel: Tomi Janhunen, Tommi Junttila, Matti Järvisalo, Guohua Liu, Emilia Oikarinen, Tommi Syrjänen, Antti Hyvärinen, Tero Laitinen, Leo Moisio

Visitors

• Dr. Alessandro Cimatti, Fondazione Bruno Kessler, Embedded Systems Unit, Italy, May 25-28, 2008
• Prof. Michael Gelfond, Texas Tech University, USA, October 22-25, 2008
• Prof. Bart Selman, Cornell University, USA, November 27-30, 2008
• Prof. Vladimir Lifschitz, University of Texas at Austin, USA, March 18-21, 2009
• Prof. Hans Tompits, M.Sc. Jörg Pührer, and M.Sc. Johannes Oetsch, Vienna University of Technology, Austria, December 14-19, 2009.
• Prof. Marc Denecker and M.Sc. Broes De Cat, Katholieke Universiteit Leuven, Belgium, Jan 18-22, 2010
• Martin Gebser and Roland Kaminski University of Potsdam, Germany, Feb 1-5, 2010
• Prof. Eugenia Ternovska, Simon Fraser University, School of Computing Science, Canada, Mar 21-23, 2010
• Prof. Hans Tompits, M.Sc. Jörg Pührer, and M.Sc. Johannes Oetsch, Vienna University of Technology, Austria, Oct 31-Nov 6, 2010.
• M.Sc. Robert Manthey, University of Dresden, Germany, March 12-19, 2011.
• Prof. Daniel Kröning, Oxford University, UK, November 17-19, 2011.
• Prof. Toby Walsh, NICTA and University of New South Wales, Sydney, Australia, November 27-30, 2011.
• Prof. Georg Gottlob, University of Oxford, UK, March 22-24, 2012.

Summary: The objective of the project is to develop methodology for domain experts with limited programming skills to construct and solve large constraint models. The idea is to achieve this by devising a declarative high-level constraint-based modelling language in which a problem can be described in a natural and compact way as a constraint model and by developing efficient methods for computing solutions for the model. The aim is to provide advanced search techniques that can handle large and computationally challenging constraint models with little programming effort or user guidance and that can exploit seamlessly grid computing techniques when the problem exceeds the capacity of regular desktop workstations.

In recent years constraint based techniques have been emerging in industrial applications. Despite the success these techniques are relatively hard to use for a domain expert with limited programming experience. However, there is significant potential for the development of a powerful and easy to use constraint-based modelling language by combining the strengths of already successful constraint-based techniques such propositional satisfiability (SAT) checking, constraint programming, linear programming, and answer set programming (ASP).

The project builds on extensive previous work by the research team on theory and implementation techniques of related ASP and SAT techniques, a number of interesting applications of constraint-based methods, and on distributed and grid-based implementation techniques for SAT and ASP developed in the group. The research is divided into four interconnected and cooperating work packages: (i) high-level constraint-based modelling language, (ii) intelligent compilation techniques, (iii) core constraint solving techniques, and (iv) solving constraint models in grids.

Publications of the project

For software and theses see the home page of the computational logic group.

Local Information

• Remember to acknowledge the financial support from the Academy of Finland using the project number 122399.
• Remember to add you publications to the bibdb system and use the flag MCM in the publications related to this project.