Volume 1, Number 3, October 2005

Constraint Programming News

volume 1, number 3, Oct 2005

Jimmy Lee (events, career news)
Eric Monfroy (profiles, publications)
Toby Walsh (news, reports)


  • news: ACP Awards, ACP EC Elections, Next CP Conferences, CONSTRAINTS Journal Call for Papers
  • CONSTRAINTS journal accepted papers
  • other publications: books, special issues, software
  • events: forthcoming conferences and workshops
  • career news: Young Research programme, and Postdoc and Associate/Visiting Researcher position
  • reports: CP Summer School, and IJCAI'05 Workshop on Modelling and Solving Problems with Constraints
  • profile: CLP Group at CharlesUniversity, Prague


Welcome to CP News, an initiative of the Association for Constraint Programming.

We aim to provide a comprehensive summary of important news in the area of constraint programming. The newsletter is published quarterly in January, April, July, and October. Please email the relevant editor with any news, event, report or profile you want published. To subscribe, please register here.

Association for Constraint Programming (ACP) Award

The Association for CP is pleased to announce that the ACP Award for Research Excellence will be given to Prof. Gene Freuder during the CP 05 conference in recognition of a program of pioneering and sustained research in constraint programming of consistent high quality yielding many substantial and significant results.

Election to the EC of the Association for Constraint Programming (ACP)

Each year, the CP community elects two new members to serve on the executive committe of the ACP. The committee decides the venue of the annual CP conference, program and conference chairs, and supports activities like the doctoral programme, summer schools, this newsletter, etc. Following the election this summer, Francesca Rossi and Barry O'Sullivsn have been elected. The full committee therefore consists of Krzysztof Apt, Fahiem Bacchus, Javier Larrosa, Pedro Meseguer, MichelaMilano, Barry O'Sullivan, Jean Francois Puget, Francesca Rossi, Peter Van Beek and Mark Wallace. Full results are available here.

Summer School on Constraint Programming

The First International Summer School on Constraint Programming was heldSeptember 11-15, 2005 in Hotel Villa del Mare, AcquafreddadiMaratea inItaly.  Two reports, one by the organizers and one by a participant, appearlater in the newsletter. The school was organized and financially supportedby the ACP.

Next CP Conferences

The next CP conference, CP-2005, will beheld in Sitges (near Barcelona) on October 1st to 5th 2005. The conferencewill be co-located with ICLP. CP-2006 will be held in Nantes in 2006. Frederic Benhamou will be the program chair.  The location of CP-2007 will be decided by the EC of the ACP during CP 2005 and announced in the next newsletter.

CONSTRAINTS Journal Call for Papers

The Constraints Journal provides a common forum for the many disciplines interested in constraint programming and constraint satisfaction and optimization, and the many application domains in which constraint technology is employed.

Papers are solicited on topics in all aspects of computing with constraints: theory and practice, algorithms and systems, reasoning and programming, logics and languages.

Submissions must be original work that has not been published or accepted for publication in another journal. Constraints will publish work that has been previously reported in a conference or workshop. However, if the submission has been reported in a conference or workshop whose proceedings are archival, the submission should substantially extend the previously published version.

Submissions will be evaluated on their originality and significance.  Under normal circumstances, submissions will be reviewed and a decision returned within 2-3 months.

Further information can be found here.

Editor-in-Chief: Peter van Beek, University of Waterloo, Canada

CONSTRAINTS Journal Accepted Papers

The Constraints Journal publishes 4 times per year. The contents of the final issue for 2005 and the first issue of 2006 (in progress) are listed below. Links to the authors' final versions of these papers (no subscription required) and to the final published versions (subscription required) can be found at:


Volume 11, Issue 1 (2006, In Progress)

  • Sanjiang Li.  On Topological Consistency and Realization
  • Rolf Backofen and Sebastian Will.  A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models

Volume 10, Issue 4 (2005), Special Issue of the 10th International Conference on Principles and Practice of Constraint Programming

  • Mark Wallace. Introduction to the Special Issue. 10:4, 2005.
  • Nicolas Beldiceanu, Mats Carlsson, RomualdDebruyne, Thierry Petit. Reformulation of Global Constraints Based on Constraint Checkers. 10:4, 2005.
  • Carla Gomes, Cesar Fernandez, Bart Selman, Christian Bessiere.   Statistical Regimes AcrossConstrainedness Regions. 10:4, 2005.
  • Pascal Van Hentenryck, Laurent Michel, Liyuan Liu.   Constraint-Based Combinators for Local Search. 10:4, 2005.
  • John Hooker. A Hybrid Method for Planning and Sceduling.  10:4, 2005.
  • PetrVlim, Roman Bartak, OndrejCepek. Extension of O(n log n) Filtering Algorithms for the Unary Resource Constraint to Optional Activities. 10:4, 2005.



Constraint Satisfaction Techniques for Agent-Based Reasoning Series: Whitestein Series in Software Agent Technologies

Neagu, Nicoleta

2005, X, 157 p., Softcover

ISBN: 3-7643-7217-6

A Birkhäuserbook

PhD theses

Yong Gao, PhD (University of Alberta), Phase transitions and typical-case complexity: Easy (Hard) Aspects of Hard (Easy) Problems, 2005. Suprvised by Dr. Joe Culberson.

Operations research techniques in constraint programming, Willem Jan van Hoeve, Institute for Logic, Language and Computation, Universiteit van Amsterdam, 2005-04-19.  Access it here or here. Keywords: Operations research; mathematical programming; constraints (information science)

Special issues

1.  European Journal of Operational Research, Special Issue on 'Scheduling with Setup Times or Costs'.  Guest editors: Ali Allahverdi and H.M. Soroush.  Paper submission deadline: Dec 31, 2005.

2.   AI Communications, Special Issue on "Constraint Programming for Planning and Scheduling".  Guest editors:

                Chris Beck, University of Toronto, Canada

                Tom Carchrae, 4C, UniversityCollegeCork, Ireland

                Andrew Davenport, IBM TJ Watson, USA

                Emmanuel Hebrard, UNSW, Sydney and NICTA, Australia

                Toby Walsh, UNSW, Sydney and NICTA, Australia

Paper submission deadline: Dec 1, 2005.

3.  Recent Advances in Constraints (to be published by Springer in the Lecture Notes in Artificial Intelligence based on the CSCLP '05 workshop held in Uppsala (Sweden), June 20-22, 2005).

The  annual  workshop  on  Constraint  Solving  and  Constraint  Logic Programming, jointly sponsored by ERCIM and Colognet, has attracted 20 paper presentations.   Many of the papers  are of interest  to a wider audience and  the intention of this  book is to make  them more widely accessible. Authors of papers that have been presented at the workshop are therefore invited to submit  final versions that take into account the discussion at the workshop for this volume.

In addition, we  give an opportunity for other  papers of good quality to appear  in this volume, even  when they have not  been presented at the workshop.

All submissions  will be peer-reviewed; submission of  a paper implies implicit  agreement  to  review   several  other  submissions  by the deadline.

Paper submission deadline: Nov. 15th, 2005.  Please submit papers in .pdf format by e-mail to brahim@4c.ucc.ie


1.   Koalog announces the release of Koalog Constraint Solver v2.6

Koalog Constraint Solver (KCS) is a powerful Java library for ConstraintProgramming. It provides cutting-edge technology for solving satisfactionand optimization problems including: scheduling, planning, routing, time tabling, resource allocation, configuration and many others.  KCSincludes a solver on boolean, integer and set domains, many global constraints such as: AllDifferent, ColoredMatrix, Cycle, Disjunctive, Global Cardinality Constraint, Sort.  KCS allows ANYTIME constraint solving.  It also includes a local search solver useful for solving huge problems when exact methods are too slow.

Visit here for documentation, code examples,KCS release notes.

About Koalog: founded in 2002, headquartered in Paris, Koalog is a software company developing components and applications for problemsolving, configuration, journey planning.

Visit here for additional information.

2.      Alice 1.2 released

      We are happy to announce version 1.2 of the Alice programming system.

Alice ML is a functional programming language that enriches the statically typed, closed functional world of ML with extensive support for type-safe programming of concurrent, distributed and open systems. It also features cutting-edge constraint programming technology in the tradition of Oz/Mozart.

     For a detailed list of changes please see here.

   Alice is open source under a BSD-style license. Source and binary packages are currently available for Linux, Mac OS, and Windows.


Doctoral Programme, Eleventh InternationalConference on Principles and Practice of Constraint Programming (CP 2005).October 1-5 2005, Sitges, Spain. 

CPAI'05, Second International Workshop on Constraint Propagation and Implementation (held in conjunction with CP 2005).  October 1, 2005, Sitges, Spain.  Co-located with ICLP and an annular eclipse. 

Soft 2005, 7th International Workshop on Preferences and Soft Constraints (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

BeyondFD 2005, 1st International Workshop on Constraint Programming Beyond Finite Integer Domains (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

LSCS 2005, Second International Workshop on Local Search Techniques in Constraint Satisfaction (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

The Fourth International Workshop on Modelling and Reformulating Constraint Satisfaction Problems (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

IntCP 2005, Workshop on Interval Analysis and Constraint Propagation for Applications (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

CHANGES'05, International Workshop on Constraint Solving under Change and Uncertainty (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

First International Workshop on Quantification in Constraint Programming (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

DSCP'05, 1st International Workshop on Distributed and Speculative Constraint Processing (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.

CPSec'05, 1st International Workshop on Applications of Constraint Satisfaction and Programming to Computer Security (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.   

First International Workshop on CONSTRAINTS AND DESIGN (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

COSOLV 2005, 5th CP Workshop on Cooperative Solvers in Constraint Programming (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.

SymCon'05, The Fifth International Workshop on Symmetry and Constraint Satisfaction Problems (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

CP 2005, 11th International Conference on Principles and Practice ofConstraint Programming.  October 1-5 2005, Sitges, Spain.Co-located withICLP and an annular eclipse. 

Doctoral Consortium, Twenty first International Conference on Logic Programming.  2-5 October, 2005, Sitges, Spain.Co-located with CP 2005 and an annular eclipse. 

CHR 2005, Second Workshop on Constraint Handling Rules (co-located with ICLP'05).  October 5, 2005, Sitges (Barcelona) Spain. 

CSLP 2005, 2nd International Workshop on Constraint Solving and Language Processing (co-located with ICLP 2005).  5 October 2005, Sitges, Barcelona, Spain. 

CICLOPS 2005, Colloquium on Implementation of Constraint and LOgic Programming Systems (Satellite workshop of ICLP 2005).  October 5, 2005, Sitges (Barcelona), Spain. 

WCB05, Workshop on Constraint Based Methods for Bioinformatics (associated to ICLP 2005).  October 5, 2005, Sitges, Spain.

MoVeLog'05, Mobile Code Safety and Program Verification Using Computational Logic Tools (an ICLP 2005 Workshop).  Sitges, Spain, Oct. 5, 2005. 

WLPE05, The 15th Workshop on Logic-based methods in Programming Environments (Satellite workshop of ICLP 2005).  October 5, 2005, Sitges (Barcelona), Spain. 

ICLP'05, Twenty first International Conference on Logic Programming.  2-5October, 2005, Sitges, Spain.Co-located with CP 2005 and an annulareclipse. 

SAGA 2005, 3rd Symposium on Stochastic Algorithms, Foundations and Applications.  October 20-22, 2005, Moscow, Russia.

INAP2005, 16th International Conference on Applications of Declarative Programming and Knowledge Management.  October 22-24, 2005, WasedaUniversity, Fukuoka, Japan. 

ISCIS'05 The 20th International Symposium on Computer and InformationSciences.  October 26-28, 2005 - Istanbul, Turkey.

Heuristic Methods for Timetabling and Rostering (Special Invited Session ofINFORMS'05).  November 13-16, 2005, New Orleans, USA.  Contact Dario LandaSilva at jds@cs.nott.ac.uk.

INFORMS'05, 2005 INFORMS Annual Meeting.  November 13-16, 2005, NewOrleans, USA. 

ICTAI 2005, 17th IEEE International Conference on Tools with ArtificialIntelligence.  November 14-16, 2005, Hong Kong.   

MICAI 2005, 4th Mexican International Conference on ARTIFICIALINTELLIGENCE.  November 14-18, 2005, Monterrey, Mexico.

MLS+CP, Workshop on Combination of metaheuristic and local search withConstraint Programming techniques.  November 28-29, 2005, University of

Nantes, Nantes - France.  Access the workshop site here too.

LPAR-12, The 12th International Conference on Logic for Programming Artificial Intelligence and Reasoning.  2nd-6th December 2005, Montego Bay, Jamaica. 

PLANSIG 2005, The 24th Workshop of the UK PLANNING AND SCHEDULING Special Interest Group.  December 15-16, 2005, CityUniversity, London, U.K.  Deadline for submissions: 5th October 2005

IICAI-05, The 2nd Indian International Conference on Artificial Intelligence.  December 20-22, 2005, Pune, INDIA.

PADL'06, Eighth International Symposium on Practical Aspects of Declarative Languages 2006 (co-located with ACM POPL'06).  January 9-10, 2006, Charleston, South Carolina, USA. 

Special semester on Gröbner Bases and Related Methods 2006.  February - July, 2006, Linz and Hagenberg, Austria.

WLP 2006, 20th Workshop on Logic Programming.  February 22 - 24, 2006, ViennaUniversity of Technology, Austria.  Paper submission deadline: November 14, 2005.

AAAI-06, Twenty-First National Conference on Artificial Intelligence.  July16-20, 2006, Boston, Massachusetts, USA.  Paper submission deadline: February 21, 2006.

IJCAR 2006, Third International Joint Conference on Automated Reasoning.  August 16-21, 2006, Seattle, USA.  Paper registration deadline: Feb 27, 2006.  Full paper submission deadline: Mar 6, 2006.

PATAT 2006, the 6th International Conference on the Practice and Theory of Automated Timetabling.  August 30 - September 1, 2006, Brno, Czech Republic.  Paper submission deadline: January 27, 2006.

CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Fall 2006, Nantes, France. Program chair: Frederic Benhamou.

Constraint Solving and Programming Track of SAC 2006, The 21st Annual ACM Symposium on Applied Computing. April 23-27, 2006, Dijon, France.

ICAPS-06, The 16th International Conference on Automated Planning and Scheduling.  June 6-10, 2006, The English Lake District, Cumbria, U.K.  Abstract Submission Deadline: November 11, 2005.  Paper Submission Deadline: November 14, 2005. 

PRICAI'06, The Ninth Pacific Rim International Conference on Artificial Intelligence.  7-11th August, 2006, Guilin, China.  Paper submission deadline: 22nd February, 2006. 

FLAIRS 06, Track on Secure Multiparty Computations and Distributed Constraint Reasoning.  May 11-13, 2006, Holiday Inn Melbourne Beach, FL, USA.  Paper submission deadline: November 21, 2005.

AISC-2006, AI and Symbolic Computation, September 20-22, 2006, Beijing, China.  Paper submission deadline: April 7, 2006.

Career news

Young Researcher Position available.  ISAAC Project, ITC-IRST, Trento, Italy

The Automated Reasoning Systems Division (SRA) at ITC-irst is seeking a young researcher to join the team ofthe ISAAC project. The position lasts up to January 2007 and is already open. Monthly salaries vary depending on age, qualification, and experience.

The ISAAC Project

The ISAAC project (AST3-CT-2003-501848)  -- Improvement of Safety Activities on Aeronautical Complex Systems -- is a Specific Targeted Research Project sponsored by the European Commission under the 6th Framework Program. The ISAAC consortiumcomprises aeronautical industries (AleniaAeronautica, Airbus France, Airbus UK, Airbus Germany, Saab AB, Societa' ItalianaAvionica, Dassault Aviation) and research centers leaders in formal verification, safety assessment, and tool development (ITC-irst, ONERA CERT, Kuratorium OFFIS e. V., ProverTechnologyAB).

The goal of the ISAAC project is to define a methodology, based on formal methods, to improve the safety analysis practice for complex systems development in the aeronautic field, to set up a shared environment based on tools supporting the methodology, and to validate the methodology through its application to case-studies. The ISAAC project builds upon the results of the ESACS project.

The role of ITC-irst in the project is manifold. ITC-irst is developing the FSAP/NuSMV-SA safety analysis platform to support the safety analysis of complex systems. This platform is based on the following components: FSAP (Formal Safety Analysis Platform), providing a graphical user interface for easier user interaction, and NuSMV-SA, the core engine providing the safety analysis capabilities, which are implemented on top of the NuSMV model checker. The platform is being evaluated against some case-studies provided by the industrial partners.

Description of Activity

The young researcher will be part of the ISAAC team at ITC-irst. The activity will include, as main responsibility, the design and implementation of new features in FSAP (Formal Safety Analysis Platform), and the preparation of project deliverables and the management of the FSAP/NuSMV-SA web site and the related documentation. Further activities may include modeling of industrial case-studies in the NuSMVlanguage, and involvement in the implementation of the safety analysis algorithms in NuSMV-SA.

Candidate Requirements

The ideal candidate should have a Master in Computer Science, Engineering or related areas, very good programming skills, and be able to work in a collaborative environment, with a strong commitment to achieving assigned objectives and reaching research excellence. The candidate is expected to be knowledgeable of:

- Linux and Windows operating systems

- Cygwin or MinGW platforms

- C/C++ programming languages

- XML language and parser (expat library)

- standard SW maintenance and compilation tools (make, gcc, debugger, automake/autoconf tools)

- FLTK library

Background and/or previous experiences in the areas of safety analysis, formal verification and model checking, though not mandatory, will be considered favourably.


Please send your applications via email to:


using 'ISAAC Researcher: application' as subject, and including a statement of interest and a CV. PostScript, PDF, or plain text formats are strongly encouraged.  Please use the above address also for further inquiries.

National ICT Australia. Knowledge Representation and Reasoning Programme

They are several postdoctoral positions open in the area of constraint programming and scheduling. One position has a deadline of Oct 16th. The other is ongoing.  There are also PhD positions and scholarships available for overseas applicants.  Please contact Toby Walsh for more details.

Associate / Visiting researcher position in Constraint Programming

LIFO - University of Orleans, France

Applications are invited for a renewable one-year research position available in the Constraint and Machine Learning group. Candidates are expected to have a strong background in Constraint Programming. Knowledge in Machine Learning will also be considered favourably.

The associate researcher is expected to join the LIFO Constraint and Machine Learning group and contribute to the development of techniques mixing these two fields like constraint learning or constraint reasoning on data streams.  It is mandatory that the candidate should have significant experience (2/3 years after PhD and more), be able to work in a collaborative environment and combine solid theoretical background and software development skills.  The position is also open to visiting scientists during sabbatical.

Funding is provided by an association called "The Studium" which also provides a wide range of services to the invited researchers.  Monthly salary may vary according to experience starting from Eu 1800 after taxes, plus free furnished appartment according to family needs (worth Eu 800-1000+).

Orleans is an historic city in the middle of the LoireValley, famous by its numerous castles.  Orleans is 1 hour south of Paris by train. The 100 hectares wooden campus is located in the south of town, with an efficient transportation to the city center ensured by a tramway line (30 mn).

Interested candidates should contact Arnaud Lallouet and send their CV, a statement of research and names of references.



1.   The First International Summer School on Constraint Programming (Reported by Krzysztof Apt, MichelaMilano, and Francesca Rossi)

      In spite of a great interest in the subject of constraint programming (CP), as testified by a large number of submissions about CP in many international conferences and journals, the subject is taught only at a limited number of Universities.  So the Executive Committee of the Association of Constraint Programming thought that there is a natural need to organize such a summer school, and asked us to take care of its organization.

      The summer school took place in AcquafreddadiMaratea, in Italy, in the period September 11-15, 2005.  Its program consisted of six courses of four hours each, given by the following speakers:

-          Constraint propagation and backtracking-based search (Roman Bartak, CharlesUniversity, Prague, Czech Republic)

-          Modelling (Barbara Smith, 4C, Ireland)

-          Hybrid algorithms, local search, and Eclipse (Mark Wallace, Monash University, Australia)

-          Global constraints (Jean-Charles Regin, ILOG, France)

-          Scheduling tools and applications (Claude Le Pape, ILOG, France)

-          Soft constraints and over-constrained problems (Thomas Schiex, INRA, France)

      Each speaker  prepared the lecture notes for his/her course, to help the students understand the subject of the course. Such lecture notes are the first ones of this kind to be produced, and could be very useful to beginners as well as experience researchers in the fields above.  The lecture notes and selected sets of slides used by the lecturers at the school can be downloaded from http://www.math.unipd.it/~frossi/cp-school/#Program.

  The school attracted 48 students from 16 countries spread over 5 continents: 13 from Italy, 6 from Spain and France, 3 from Ireland, South Africa, and Portugal, 2 from Australia, Germany, and ChechRepublic, 1 from Romania, Belgium, USA, Japan, Finland, Switzerland, and Turkey.

      In our view the school was a great success and we think that it has served well its main purpose: to disseminate the knowledge of constraint programming. We hope that this school is just the first one of a long series.

      The organizers,

Krzysztof R. Apt

                Michela Milano

                Francesca Rossi.

2.   The First International Summer School on Constraint Programming (Reported by Roland Martin, DarmstadtUniv. of Technology)

      The summer school was located in a very nice place in the south of Italy named AquafreddadiMaratea. This place is very remote but turned out to be an excellent choice for the summer school.  The sea literally before the door and the enchanting surrounding was very relaxing and helped to free your mind.  The whole summer school was well organized and hardly any problems arose. From the registration to the school and the hotel, organising transport and providing material for the lessons and to a very balanced schedule everything was taken into account.

      The lectures itself were very informative and interesting. The range of the lectures covered most of the active research directions in CP and many more very mentioned and shortly introduced to provide soundness of the different fields of CP.  The different topics were presented by expert senior researchers that were "people of the first hour" in this particular topic and have already spent years of successful research in this field. So they were not only able to present the topics in a very structured way but also they were able to give hints on this and that and revealed a lot of insight and expert knowledge the students can prosper from in every days work with constraints.  Perfectly suited for beginners but also very interesting for intermediate constraint programmer the lectures gave insights to the very basic ideas and concepts behind CP and the different research areas.  In difference to conferences or workshops the lecturers could spend a  considerable amount of time for introducing the basic concepts of their topic which was very helpful for beginners but also was perfect for intermediates to close gaps in knowledge. Although the lectures were designed for people without any knowledge in CP could follow the ideas they also provided a deeper insight for intermediate constraint programmer. Even the other lecturers joined the sessions and had interesting questions which showed that the lecturers were not only presenting already known facts but state-of-the-art results from research.

      The possibility to ask questions during the presentations as well as have discussions in the spare time between the lessons and in the evening was very fruitful for the participants. So a lot of interesting questions for the students could be discussed and the lecturers were very willing to assist and give answers to the many questions of the students.

      So the lectures as well as the nice circumstances contributed to one of the major goals of the summer school for the students: Strengthen the contact to other people working in CP and helping making yourself a home in the CP community.

3.  The Fifth Workshop on Modelling and Solving Problems with Constraints, held alongside the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005) (Reported by ZeynepKiziltan)

      The aim of the workshop was to bring together researchers interested in looking for ways to enrich the efficiency, usability and the expressiveness of the constraint programming tools. Following the successful earlier workshops held alongside ECAI 2000, IJCAI 2001, ECAI 2002, and ECAI 2004,  the workshop was run for the fifth time in Edinburgh, Scotland alongside IJCAI 2005.

  The workshop received high interest, with the number of participants around 30. The workshop programme included presentations of 11 contributed papers, discussing research into many aspects of  modelling and solving problems with constraints such as modelling, symmetry breaking, propagation algorithms, applications, hybrid   systems, and extensions to the classical framework. The first paper of the modelling and the symmetry breaking session was by Gent and Lynce showing how to encode the social golfers problem into SAT.   Manlove and O'Malley discussed a new constraint encoding for the stable marriage problem.  The last paper of the session was by Petrie who talked about the interaction between the dynamic symmetry breaking methods and modelling techniques. Two papers on propagation algorithms were presented. Whilst the paper by Brown, Prosser, Beck and Wei Wu introduced a new global constraint enforcing graph connectivity, Unsworth and Prosser discussed an n-ary constraint for the stable matching problem.

      The session on extensions covered issues ranging from a new distributed guided genetic algorithm for constraint optimization problems by Sadok and Khaled, to demonstrating how the notion of generalised arc cosnsitency can be defined for constraint based inference problems by Chang and Mackworth, to studying the relation among open, interactive and dynamic CSPs presented by Macho-Gonzalez and Meseguer. The final session of the workshop focused on applications and hybrid systems. Kalech and Kaminka showed how model-based coordination diagnosis can be formalised using constraint programming. A constraint-based planner was presented by Pang and Golden. The last paper of the session was by Thebault, de Givry, Schiex and Gaspin who explained how constraint programming  and pattern matching techniques can be combined to describe and locate structured motifs in genomic sequences.

      In addition to the paper presentations, the workshop hosted the first constraint modelling challenge organised by Barbara Smith and Ian Gent. It is unfortunate that the invited speaker NarendraJussien could not make the workshop, as otherwise the participants would have learnt more about modelling and solving constraint problems using the open-source constraint programming system Choco.  However, we wish all the best to his new born baby.

     The workshop proceedings are available online at the workshop web site.


CLP Group at CharlesUniversity, Prague

Constraint and Logic Programming Group is an informal research group at Faculty of Mathematics and Physics, CharlesUniversity in Prague (CzechRepublic). Logic programming has a long tradition at CharlesUniversity connected with research of Prof. PetrŠtěpánek. History of the CP part of the group started in mid 90s with the PhD studies of Roman Barták. The CP part of the group now consists of one researcher (Roman Barták) primary devoted to CP technology, one associate researcher (OndřejČepek) contributing theoretical work and six PhD students, two of them (PetrVilím and TomášMüller) are right before defending their thesis.

Despite a small size of the group, its research interests are quite broad. Our work is primarily oriented to applying constraints in planning and scheduling problems and it is driven by real-life problems. We are working on filtering algorithms for extensionally defined constraints and for global constraints modelling resources in scheduling. PetrVilím designed several efficient algorithms for propagating time in unary resources and Roman Barták proposed a concept of dynamic (open) global constraints with a changing set of constrained variables. This work is motivated by solving complex scheduling problems, where the traditional static constraint satisfaction techniques are not applicable. We also pay a special attention to implementing the algorithms in such a way that they can be easily integrated into existing constraint solvers. We designed a constraint-based scheduling engine for VisoptShopFloor system produced by Visopt Ltd. (www.visopt.com). The system uses ideas from planning, because some activities like set-ups must be planned during the scheduling process. Hence a more dynamic approach to constraint satisfaction is required. Currently, we continue our co-operation with a successor to Visopt, a small company called Moyo Tech (www.moyo-tech.com) that produces scheduling software for complex industries. This company participates in the CP Industrial Association. Our research results in constraint-based scheduling will also be applied in a new European FP6 project EMPOSME (Enterprise Modelling and Performance Optimisation ForSMEs), where we focus on enterprise modelling and optimization via constraint satisfaction technology. Using knowledge engineering techniques in automated constraint modelling is one of many challenges in the project.

We are also studying efficient search algorithms applicable in real-life problems. We co-operated with HanaRudová from Masyryk University, Brno on design of Limited Assignment Search algorithm which is an incomplete depth-first search algorithm motivated by human approach to problem solving (after exploring several alternatives, all with a failure, turn attention to other parts of the problem). This algorithm achieved a very good quality/performance ratio when solving structured problems like timetabling problems. We are currently working on its generalization to a wider class of problems. TomášMüller proposed a hybrid Iterative Forward Search algorithm and again in co-operation with HanaRudová, he successfully applied this algorithm to a large scale timetabling problem from Purdue University, USA. In this problem, we paid a special attention to dynamic aspects, in particular to minimization of the number of additional changes in the timetable after changing the problem specification. Dynamic aspects are omnipresent when going to real-life problems and hence we consider them seriously in our research.

In addition to research, the group is also active in education. Constraint Programming is taught at CharlesUniversity as a separate subject since 1998. We designed popular On-line Guides to Prolog Programming and to Constraint Programming and we also gave several courses and tutorials on CP at summer schools and conferences (ESSLLI, NASSLLI, ETAPS, SAC,…). In 2001 we organized an annual workshop of the ERCIM Working Group on Constraints, in 2003 we organized a PLANET Technology Information Day on AI Planning and Scheduling, and in 2005 we hosted a CP-AI-OR conference in Prague.

The group actively participates in the ERCIM Working Group on Constraints and it was a member of PLANET Network of Excellence in AI Planning and CologNet. We closely co-operate especially with MasarykUniversity (CzechRepublic) and with Moyo Tech (Israel).

More information on the CLP Group can be found on web (http://clp.mff.cuni.cz/).

Selected publications:

VisoptShopFloor: On the edge of planning and scheduling
R. Barták. In Principles and Practice of Constraint Programming (CP2002), Springer Verlag, LNCS 2470, 2002, pp. 587-602.

Dynamic Global Constraints in Backtracking Based Environments
R. Barták. Annals of Operations Research (2003), no. 118, p. 101-119.

Unary Resource Constraint with Optional Activities
P. Vilím, R. Barták, O. Čepek.
In Mark Wallace (ed.): Principles and Practice of Constraint Programming (CP 2004). Springer Verlag, LNCS 3258, 2004, pp. 62-76.

Limited Assignments: A New Cutoff Strategy for Incomplete Depth First Search
R. Barták, H. Rudová. In Applied Computing 2005, Volume 1, ACM, 2005, pp. 388-392.

Minimal Perturbation Problem in Course Timetabling

T, Müller, H. Rudová, R. Barták. In Practice and Theory of Automated Timetabling, Selected Revised Papers, Springer Verlag, to appear.