Volume 2, Number 1, April 2006

Constraint Programming News

      <h3 style="text-align: center;" align="center"><span class="GramE"><span lang="EN-US">volume</span></span><span lang="EN-US"> </span><span lang="EN-US">2</span><span lang="EN-US">, number </span><span lang="EN-US">0</span><span lang="EN-US">, </span><span lang="EN-US">Jan,</span><span lang="EN-US"> 200</span><span lang="EN-US">6</span></h3>

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



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)

ACP EC news: January 1st, 2006 to March 31, 2006

·        After a call for bids for the CP 2006 summer school, the EC received two bids. The accepted bid was from Kostas Stergiou and Toby Walsh, who will organize the 2006 CP summer school in Samos, Greece, on June 18-23, 2006. As decided by the EC after the 2005 school, general and advanced summer schools will alternate. This school will be an advanced school on global constraints. The school web site is at the URL http://www.cse.unsw.edu.au/%7Etw/school.html

·        The travel grant scheme that was announced in Sitges is still on hold. In the meantime, the EC considered, and accepted, the following requests for sponsorship:

o       1000 euros to the International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic and Graph Theory, that has been held on March 20-24, at St Anne's College, University of Oxford. The workshop web site, containg all presentation slides, is at the URL http://www.cs.rhul.ac.uk/home/green/mathscsp/

o       1000 euros to the Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming (CSCLP 2006) to be held on June 26-28, 2006, at the Universidade Nova de Lisboa, Caparica, Portugal. Web site: http://centria.di.fct.unl.pt/conferences/csclp06

o       3000 euros to the 2006 CP summer school (see above for details about the school).

o       CP 2005 had a nice surplus. Many thanks to Pedro, Javier, and Peter for a wonderful organization and program! The EC hopes that this money will be useful to support many interesting CP activities in the future.

·        Frederic Benhamou, the program chair of CP 2006, wanted to know the ACP EC opinion about the possibility of eliminating doctoral program abstracts from the CP proceedings. The AC EC has discussed this issue, and it is in favour of the following:

o       removing the 1-page DP abstracts from the Springer proceedings

o       putting the DP abstracts and/or longer versions in the DP web site and in Corr

o       distributing the DP abstracts to the CP participants by printing a separare booklet, like a workshop proceedings

o       use Corr also for the workshop proceedings

However, full responsability for the program and the proceedings of the CP conference remains in the hands of the program chair and the program committee.

·        To encourage discussion on ACP-related matters, the ACP EC has started a Yahoo! discussion group on constraints, where anybody can join or leave at any time, by following the simple instructions at the URL http://groups.yahoo.com/group/constraints/ On March 23, 2006, this discussion group has 145 members.

·        To follow the discussion which took place at the ACP general assembly at CP 2005, the EC is creating a task force on CP applications, that will be led by Barry O'Sullivan. The role if this task force is to identify mechanisms to attract practitioners and industrial people to CP conferences, and in general to strenghten the link between academia and industry in the CP field. People interested in joining this task force should contact Barry.

·        After the 2005 ACP research award, given to Eugene Freuder at CP 2005, there has been an ongoing discussion about an annual versus a two-yearly ACP research award. We will hopefully finalize this discussion soon and post the result on the ACP web site and the CP newsletter. In any case, the receipient of the next award will be chosen by the EC among a set of candidates proposed by the CP community through an open call.

·        The ACP EC will be happy to receive proposals for initiating new activities, or for improving the current ones. Any member of the CP community who wants to make any of such proposals should send a detailed message describing his/her proposal to the address proposals@a4cp.org, with subject "ACP EC proposals: [a specific subject]".

Second International Summer School of the Association for Constraint Programming

Second International Summer School of the Association for Constraint Programming

  Advanced School and International Workshop on Global Constraints

  Doryssa Bay Hotel, Samos, Greece

  Organizers: Kostas Stergiou and Toby Walsh

  June 18-23, 2006

  The Second International Summer School on Constraint Programming is an advanced school and associated workshop on global constraints. The school and workshop are aimed at PhD students, researchers, and practitioners of all levels who wish to learn about this key area in depth. Lecturers include: Philippe Baptisite, Nicolas Beldiceanu, Christian Bessiere, Mats Carlsson, Willem-Jan van Hoeve, Irit Katriel, Michela Milano, and Jean-Charles Regin. The school and workshop will take place in the Doryssa Bay hotel on the Aegean island of Samos in Greece. The hotel is next to the fishing village of Pythagorion, the birth place of the Greek philosopher Pythagoras. To participate in the advanced school and workshop, please email Toby Walsh (tw@cse.unsw.edu.au) as soon as possible.

CP 2006 Call For Papers:

                            CP 2006

              Twelfth International Conference on

       Principles and Practice of Constraint Programming

                    September 25 - 29, 2006

                         Nantes, France


The CP conference is the annual international conference on constraint programming and related areas. It is concerned with all aspects of computing with constraints, including: theory, algorithms, applications, environments, languages, models and systems. CP 2006 includes a technical programme, where presentations of theoretical and application papers, as well as invited talks, tutorials, posters and system demos aim at describing the best results and techniques in the state-of-the-art of constraint programming. Moreover, CP 2006 continues the tradition of the CP doctoral programme, in which PhD students can present their work, listen to tutorials on career and ethical issues, and discuss their work with senior researchers via a mentoring scheme. Finally, there will also be a number of workshops, where researchers will be able to meet in an informal setting and discuss their most recent ideas with their peers.

Papers are solicited from all disciplines concerned with constraints and any application domain using constraints. Example topics include problem modelling, problem solving, efficiency and usability. Papers which report on successful applications of constraint technology are also solicited.

Submitted papers must be original and must not be simultaneously submitted for publication in a journal or another conference. Authors are required to prepare their papers by following the Springer instructions found at: http://www.springer.de/comp/lncs/authors.html.

A page limit of 15 will be strictly enforced. The proceedings will be published by Springer Verlag, in the Lecture Notes in Computer Science series.


  * April 21, 2006: Deadline for submissions

  *  June 14, 2006: Notifications

  *  July  5, 2006: Camera-ready copy


Conference Chairs

Frédéric Benhamou, U of Nantes, France

Narendra Jussien, EMN, France

Program Chair

Frédéric Benhamou, U of Nantes, France

Doctoral Program Chairs

Zeynep Kiziltan, U of Bologna, Italy

Brahim Hnich, 4C, Ireland

Workshop/Tutorial Chair

Barry O'Sullivan, 4C, Ireland

Poster/Demo Chair

Laurent Michel, U of Connecticut, USA

Publicity Chairs

Christian Schulte, KTH, Sweden

Mikael Lagerkvist, KTH, Sweden

Program Committee

Pedro Barahona, New U of Lisbon, Portugal Nicolas Beldiceanu, EMN, France Christian Bessiere, LIRMM-CNRS, France David Cohen, Royal Holloway, UK Andrew Davenport, IBM, USA Boi Faltings, EPFL, Switzerland Carla Gomes, Cornell, USA Laurent Granvilliers, U Nantes, France John Hooker, CMU, USA Peter Jonsson, Linköping U, Sweden Irit Katriel, U of Aarhus, Denmark Zeynep Kiziltan, U of Bologna, Italy Luc Jaulin, ENSIETA Brest, France Jimmy Lee, CUHK, Hong Kong Michael Maher, NICTA, Australia Pedro Meseguer, IIIA-CSIC, Spain Laurent Michel, U of Connecticut, USA Michela Milano, U of Bologna, Italy Barry O'Sullivan, 4C, Ireland Gilles Pesant, Polytech Montréal, Canada Jean-François Puget, ILOG, France Jean-Charles Régin, ILOG, France Francesca Rossi, U of Padova, Italy Louis-Martin Rousseau, Polytech Montréal, Canada Michel Rueher, U of Nice, France Thomas Schiex, INRA Toulouse, France Christian Schulte, KTH, Sweden Helmut Simonis, CrossCore Optimization, UK Barbara Smith, 4C, Ireland Peter Stuckey, U of Melbourne, Australia Peter van Beek, U Waterloo, Canada Pascal Van Hentenryck, Brown U, USA Mark Wallace, Monash U, Australia Toby Walsh, NICTA and UNSW, Australia Roland Yap, NUS, Singapore Makoto Yokoo, Kyushu U, Japan Weixiong Zhang, Washington U, USA

CP 2007:

  * Location: Providence, RI, USA

  * Dates: fall 2007.

  * Conference chairs: Meinolf Sellmann and Laurent Michel

  * Program chair: Christian Bessiere

 * Co-located with ICAPS 2007 (International Conference on Automated Planning and Scheduling)

CP-AI-OR  Call For Participation

                   C A L L  F O R  P A R T I C I P A T I O N

                     The Third International Conference on

         Integration of AI and OR Techniques in Constraint Programming

                    for Combinatorial Optimization Problems


                  May 31-June 2, 2006, Cork, Ireland



After a successful series of five international workshops (Ferrara, Paderborn, Ashford, Le Croisic, and Montreal) and two international conferences (Nice, Prague), the third international conference devoted to integration of Constraint Programming, Artificial Intelligence, and Operations Research techniques will be held in Cork, Ireland, in 2006.

The aim of the conference is to bring together interested researchers  from AI and OR, and to give them the opportunity to show how the integration of techniques from AI and OR can lead to interesting results on large scale and complex problems. We explicitly welcome new ideas and methods for integrating OR and AI techniques that have arisen from real-world applications.

CP-AI-OR is intended primarily as a forum to focus on the integration and hybridization of the approaches of CP, AI, and OR technologies. A secondary aim is to provide an opportunity for researchers in one area to learn about techniques in others. 20 hiqh-quality papers have been accepted that either actively combine, integrate or contrast approaches from some of these areas, or focus on a single area of interest to all the communities involved. For details see:


As in previous years, CP-AI-OR'06 will be preceded by a Master Class where leading researchers give introductory and overview talks in a given area. This year, the topic of the Master Class will be "Modelling and Solving for Uncertainty and Change." The Master Class is intended for PhD students, researchers, and practitioners. For details see:





 Deadline for Early Registration    April 28,      2006

 Master Class                       May 30,        2006

 CP-AI-OR'06                        May 31-June 2, 2006


 Chris Beck, University of Toronto, Canada Barbara Smith, Cork

 Constraint Computation Centre, Ireland


 Barry O'Sullivan, Cork Constraint Computation Centre, Ireland


 Ken Brown, Cork Constraint Computation Centre, Ireland Armagan Tarim,

 Cork Constraint Computation Centre, Ireland


 Ian Miguel, University of St. Andrews, Scotland


 Michela Milano, Universita di Bologna, Italy


 Gautamkumar Appa, London School of Economics, UK Philippe Baptiste,

 Ecole Polytechnique, France Roman Bartak, Charles University, Czech

 Republic Mats Carlsson, SICS, Sweden Ondrej Cepek, Charles University,

 Czech Republic Hani El Sakkout, CISCO Systems Inc.

 Bernard Gendron, CRT and Univ. of Montreal, CanadaCarmen Gervet,

 Brown University USA/Imperial College UK Carla Gomes, Cornell

 University, USANarendra Jussien, Ecole des Mines de Nantes, France

 Stefan Karisch, Carmen Systems, Canada Francois Laburthe, Bouygues,

 France Andrea Lodi, Univ. of Bologna, ItalyMichela Milano, Univ. of

 Bologna, Italy Gilles Pesant, CRT and Ecole Polytechnique de Montreal,

 Canada Jean-Francois Puget, ILOG, France Jean-Charles Regin, ILOG,

 France Michel Rueher, Univ. of Nice-Sophia Antipolis, France Meinolf

 Sellmann, Brown University, USA Helmut Simonis, CrossCore

 Optimization, UK Gilles Trombettoni, Univ. of Nice-Sophia Antipolis,

 France Michael Trick, Carnegie Mellon University, USA Pascal van

 Hentenryck, Brown University, USAMark Wallace, Monash University,

 AustraliaWeixiong Zhang, Washington University, USA

ERCIM Workshop on Constraints

                      Call For Papers

                  11th ERCIM Workshop on

    Constraint Solving and Constraint Logic Programming

                       (CSCLP 2006)


                     June 26-28, 2006

             FCT, Universidade Nova de Lisboa

                    Caparica, Portugal



This workshop is organized as the 11th meeting  of the ERCIM

Working Group on Constraints, co-ordinated by Francois Fages.

Call for paper submissions


The workshop will cover all aspects of constraint and logic

programming,   including   various   foundational   issues,

implementation  techniques,  new  applications  as well  as

teaching issues.  Particular emphasis  is on assessing  the

current state of the art and identifying future directions.

We would  like  to invite authors  to submit papers  on all

aspects of  research on  constraint and  logic programming.

Standard research papers, position papers and work-in-progress

papers describing current projects are all welcome.

To submit a paper to the workshop, please email a postscript

or  PDF file,  preferably in  Springer  LNCS format  to  the

workshop chairs at ercim06@di.fct.unl.pt.

Papers can be of any length but should not exceed 15 pages.

All submissions must be received by 5th May 2006.



A printed volume  of the  workshop papers  will be given  to the

participants,  free of charge.  Note that the proceedings of the

workshop will also be available online here as a single pdf file.

After the workshop,  we will decide  whether to publish a subset

of papers in a Springer Lecture Notes on Artificial Intelligence

(LNAI) volume, as was done for previous editions of this workshop.

In this case,  all the papers  will have  to go  through  a new

peer-review  and  selection process. Further details about this

possibility will be given during the workshop.

Important Dates


Paper submission deadline:       May  5th

Notification of authors:         May  16th

Camera ready version deadline:   June 7th

Registration deadline:           June 9th

Financial support applications:  June 2nd

CSCLP 2006 Workshop:             June 26-28th

Registration and Scholarships


The workshop  is open to all  and is not restricted  to ERCIM

members.  There is no registration fee. However, participants

wishing  to attend  the workshop Banquet  are kindly asked to

contribute with 30 Euros to be paid on site.

Participants  are kindly asked  to register  for the workshop

before the registration deadline - 9th June 2006 - by sending

a message  to the workshop chairs  at  ercim06@di.fct.unl.pt.

(Registration form available in the workshop web site).

Some  limited scholarships  may also  be available  to help

students with  travel expenses.  Students  who need support

should ask their primary advisor to send a reference letter

to the workshop chairs at ercim06@di.fct.unl.pt before 2nd June.

To submit  the camera-ready version,  please send a PDF file,

preferably in Springer LNCS format  to the workshop chairs at

ercim06@di.fct.unl.pt. Papers can be of any length but should

not exceed 15 pages.



Francisco Azevedo  (CENTRIA, FCT/UNL, Portugal)

Pedro Barahona     (CENTRIA, FCT/UNL, Portugal)

Francois Fages     (INRIA, France)

Francesca Rossi    (University of Padova, Italy)

Yahoo! Discussion Group on Constraints

A Yahoo! Group dedicated to constraints has been established. The purpose of this group is to encourage discussion amongst the community, in particular in order to highlight issues that should be addressed by the ACP EC, as well as providing an online archive for general discussions.

To visit and join the group go to:


The advantage of a Yahoo! Group is that it is an easy way to manage discussions over a period of time. No email needs to come to your mailbox, but is instead archived so you can read it whenever you want. The access to the groups is limited to members of the group, but anyone can become a member by following a simple sign-up procedure.

There are many nice facilities available through the group.

For example, there is a feature for setting up online polls.

You can setup databases of various kinds and creating links to various web-sites that are of interest: I have already included links to CSPLib, CP-Online, the CP Conference Series, the Editor's page at the Constraint Journal, CORR and several other things. Please extend this as you wish.

We look forward to seeing this resource being used by the CP community.

CONSTRAINTS Journal Accepted Papers

The Constraints Journal publishes 4 times per year. The contents of the current issue and forthcoming papers 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 here.

Constraints, Forthcoming Papers

·        Constraint Models for the Covering Test Problem

Brahim Hnich, Steven D. Prestwich, Evgeny Selensky, and Barbara M. Smith

·        Symmetry Breaking Constraints for Value Symmetries in Constraint         Satisfaction

Y.C. Law and J.H.M. Lee

·        Cardinal: A Finite Sets Constraint Solver

Francisco Azevedo

·        Asynchronous Forward-Checking for DisCSPs

Amnon Meisels and Roie Zivan

Constraints, Volume 11, Issue 2&3 (2006)

Special Issue of the 11th International Conference on Principles and Practice of Constraint Programming,

Dedicated to Eugene C. Freuder on the occasion of his 60th birthday

  • Introduction to the Special Issue

Barry O'Sullivan and Peter van Beek

  • A Tribute to Eugene Freuder

Alan K. Mackworth

  • Gene Freuder and the Roots of Constraint Propagation

David L. Waltz

  • Applying Ad-hoc Global Constraints with the case Constraint to Still-Life

Kenil C. K. Cheng and Roland H. C. Yap

  • Symmetry Definitions for Constraint Satisfaction Problems

David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, and     Barbara M. Smith

  • An Integrated Method for Planning and Scheduling to Minimize Tardiness  John N. Hooker
  • The Impact of Search Heuristics on Heavy-Tailed Behaviour

Tudor Hulubei and Barry O'Sullivan

  • Dynamic Ordering for Asynchronous Backtracking on DisCSPs

Roie Zivan and Amnon Meisels


PhD theses


Florian Letombe. De la validité des formules booléennes quantifiées : étude de complexité et exploitation de classes traitables au sein d'un prouveur QBF (in french). Université d'Artois (UFR Lens)

Supervisors : Pierre Marquis, Sylvie Coste-Marquis, Daniel Le Berre

Abstract :

This thesis is centered on QBF, the validity problem for quantified Boolean formulae.

Since QBF is computationally hard (PSPACE-complete), it is important to point out some specific cases for which the practical solving of QBF could be achieved. In this thesis, we have considered some restrictions of QBF based on the matrices of instances. Our main purpose was (1) to identify the complexity of QBF for some restrictions not considered so far and (2) to explore how to take advantage of polynomial classes for QBF within a general QBF solver in order to increase its efficiency."


Julien Bidot. A General Framework Integrating Techniques for Scheduling under Uncertainty. ILOG S.A. in collaboration with Laboratoire Génie de Production de l'Ecole Nationale d'Ingénieurs de Tarbes.

Supervisors: Bernard Grabot, Thierry Vidal, Philippe Laborie


For last years, a number of research investigations on task planning and scheduling under uncertainty have been conducted. This research domain comprises a large number of models, resolution techniques, and systems, and it is difficult to compare them since the existing terminologies are incomplete. However, we identified general families of approaches that can be used to structure the literature given three perpendicular axes. This new classification of the state of the art is based on the way decisions are taken.

In addition, we propose a generation and execution model for scheduling under uncertainty that combines these three families of approaches. This model is an automaton that develops when the current schedule is no longer executable or when some particular conditions are met.

The third part of this thesis concerns our experimental study. On top of ILOG Solver and Scheduler, we implemented a software prototype in C++ directly instantiated from our generation and execution model. We present new probabilistic scheduling problems and a constraint-based approach combined with simulation to solve some instances thereof.



400 updated slides about constraint programming at http://www.informatik.uni-ulm.de/pm/mitarbeiter/fruehwirth/pisa/ based on the book Essentials of Constraint Programming.


Special issue

Constraints Journal, Special Issue on Local Search Techniques in Constraint Satisfaction. 


Yehuda Naveh, IBM Research, Haifa, Israel

Andrea Roli, Universita' "G.D'Annunzio", Chieti-Pescara, Italy



Tentative partial abstract: April 30, 2006

Submission of papers: July 14, 2006

Notification of acceptance: November 2006

Publication of the Special Issue: early 2007


Special issue homepage:


Constraints Journal homepage:


Guidelines for authors: http://ai.uwaterloo.ca/~vanbeek/Constraints/Instructions_for_Authors.html



·        FRODO: a FRamework for Open/Distributed Optimization

Dear all,

I would like to take this opportunity to announce the public release of our simulation platform for distributed constraint satisfaction/optimization problems.  

It's name is FRODO: a FRamework for Open/Distributed Optimization. The framework is implemented in Java, and simulates a multiagent environment in a single Java virtual machine. Each agent in the environment is executed asynchronously in a separate execution thread, and communicates with its peers through message exchange. The framework is highly customizable, allowing the user to implement and experiment with any distributed optimization algorithm. Support for synchronous/asynchronous message passing, monitoring and statistics, as well as problem visualization tools are provided. A number of distributed algorithms are already implemented in this framework, like the Distributed Breakout Algorithm, and the DPOP Algorithm. A number of random evaluation problems are also provided, from two distinct domains: meeting scheduling and resource allocation in a sensor network.

This is the first release (obviously not perfect, nor commercial-grade ;-) ), so we would greatly benefit from your feedback, comments, ideas for improvement, etc.

If you have any questions, no not hesitate to ask me.

For more details, downloads, etc: http://liawww.epfl.ch/frodo/

Thank you for your time, and your valuable feedback!

Best regards,

Adrian Petcu.


·        Koalog Newsletter

Dear Koalog friend or user,


We are very pleased to send you this fourth newsletter.

Its goal is to keep you informed about Koalog and its activities.

We plan to send one newsletter each quarter or semester depending on the news (fresh news are still available from http://www.koalog.com/php/news.php

and we have a RSS feed at http://www.koalog.com/php/rss.php).

Don't hesitate to reply to this email to request more information.


The content of this newsletter is as follows:

  1/ Sudokus

  2/ Software releases

  3/ Koalog is growing

  4/ Talks


1/ Sudokus


You probably know Sudokus .... but do you know that Sudokus can be easily solved using Constraint Programming? We recently published an article about  this topic on http://www.java.net:



We also decided to use Koalog Constraint Solver to generate and explain Sudokus. You will find Sudokus generated by Koalog on:

  - http://sudoku.koalog.com,

  - Phosphore,

  - Le Monde (since January, 3rd),

  - Le Monde 2 (starting this week),

  - http://www.lemonde.fr (starting this week).


2/ Software releases


We are very proud to announce the release of the long awaited Koalog Constraint Solver v3.0.

KCS includes

  - new constraints,

  - methods for shaving variables,

  - various optimizations leading to a 25% performance improvement.


More info on http://www.koalog.com/php/jcs.php.

3/ Koalog is growing

In 2006, 3 sales persons will be joining Koalog.

4/ Talks


On 2005/11/04, we were invited by Narendra Jussien at the Ecole des Mines de Nantes (http://www.emn.fr) to give a talk about Koalog Constraint Solver.


This talk is available from http://www.koalog.com/php/talks.php.


Best regards,

The Koalog team



·        Koalog announces the release of Koalog Configurator v1.1

Paris, France - February 2006


Koalog Configurator is a powerful Java configuration software based on Koalog constraint programming technology. This technological choice broadens the functional possibilities of configuration: interactive configuration in any order, selection prioritization, complex pricing rules, unambiguous XML modelization, features that cannot be accurately implemented in common rule-based configurators. 


Koalog Configurator comes with an intuitive Swing maintenance tool and efficient web components. A car configurator example built with Koalog Configurator web components can be seen at http://democonfig.koalog.com.


Visit http://www.koalog.com/php/jcf.php for documentation, release notes.

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

Visit http://www.koalog.com for additional information about Koalog.


·        Gecode 1.0.0

We would like to announce the release of Gecode 1.0.0



Gecode is an open, free, portable, accessible, and efficient environment for developing constraint-based systems and applications:



Gecode is radically open for programming: it can be easily interfaced to other systems. It supports the programming of new propagators (as implementations of constraints), branching strategies, and search engines. New variable domains can be programmed with the same efficiency as the finite domain and integer set variables that come predefined with Gecode.



Gecode is distributed under a BSD-style license. All of its parts including documentation, implementations of global constraints, and examples are available as source code.



Gecode is implemented in C++ that carefully follows the C++ standard. It can be compiled with modern C++ compilers and runs on a wide range of machines (including 64bit machines).



Gecode comes with extensive reference documentation that allows to focus on different programming tasks like modelling, implementing propagators, and implementing variable domains.



Gecode offers competitive performance with respect to both runtime and memory usage.


allows contributions

Gecode is designed to facilitate contributions on top of it.  CP(Graph) and CP(Map) providing graph and map variables for constraint programming is available as a first contribution built on top of Gecode.


Gecode and contributions built on top of it are available from http://www.gecode.org/


·        New opensource constraint solver

The jOpt open source optimization project has just released the beta version 1.0 of its CSP constraint solver.

Here's a quick summary of features

  - Finite integer numeric variables

  - Floating point numeric variables

  - Integer set variables

  - Numeric, boolean, trigonometric, and set constraints, etc.

  - Generic constraints such as summations, indexed variables (similar to having subscripts on a variable), all-different, etc.


Lots of searching capabilities:

  - DFS, BFS

  - Different memory models for tracking the data during searches

  - Ability to define actions that will produce a search tree that are navigated by search techniques such as the order variables are selected for generation and how values are assigned

  - Local Neighborhood Search techniques


  For more information please visit: http://jopt.sourceforge.net


·        New releases of the Parma Polyhedra Library


We are very happy to announce the availability of PPL 0.9, the latest release of the Parma Polyhedra Library, a modern library for the manipulation of convex polyhedra and other numerical abstractions especially targeted at static analysis and verification of complex software and hardware systems.


Besides improving upon almost all of the functionality available since the release of PPL 0.7 in December 2004, the two recent releases of PPL 0.8 and PPL 0.9 have expanded the usefulness of the library by providing new features that should be of great interest to people working in the research fields mentioned above.  In particular, the latest release includes support for:


The Domain of Relational Rational Grids


The class Grid can represent and manipulate the set of solutions of a finite conjunction of congruence relations.  Elements of this domain can thus be used to encode information about the patterns of distribution of the values that program variables can take. Operations provided include everything that is needed in the field of static analysis and verification, including affine images, preimages and their generalizations, grid-difference and widening operators. This is the first time that one of the most precise variants of the domain initially proposed by P. Granger is made freely available to the community.  Moreover, as the PPL provides several polyhedral domains as well as full support for lifting any domain to the powerset of that domain, a user of the library can now experiment with the extra precision provided by abstract domain constructions and combinations including not only Z-polyhedra, but also grid-polyhedra, grid-bounded-differences and their powersets.


The Domain of Bounded Difference Shapes


This is a subdomain of the domain of convex polyhedra providing coarse but efficient-to-compute approximations for large analysis problems. The domain can be instantiated to use a wide range of different data types, including exact arithmetic rationals or integers, bounded precision floating point data types with controlled rounding and bounded integer data types with systematic yet efficient overflow detection.  The full set of operations needed for static analysis and verification are supported, here included the semantic widening operator defined in our SAS 2005 paper.


A Linear Programming Solver Based on Exact Arithmetic


The class LP_Problem can be used to represent, check the satisfiability and optimize linear programming problems.  The solver is based on a primal simplex algorithm using exact arithmetic.


Other enhancements include a new configuration program and Autoconf function making library usage even easier; several new operations useful for static analyzers; new output methods for debugging;  improvements to the C and Prolog interfaces; several important portability improvements; and (only) a handful of bug fixes.      


For more information, visit the PPL web site at




The PPL core development team:


         Roberto Bagnara  <bagnara@cs.unipr.it>

         Patricia M. Hill <hill@comp.leeds.ac.uk>

         Enea Zaffanella  <zaffanella@cs.unipr.it>




2006 Special Programme on Logic and Algorithms (6 Workshops).  16 January - 7 July 2006, Isaac Newton Institute for Mathematical Sciences at Cambridge, UK


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


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


DALT 2006, 4th International Workshop on Declarative Agent Languages and Technologies (held in conjunction with AAMAS 2006).  8 May 2006, Future University Hakodate, Japan


CLIMA VII, Seventh International Workshop on Computational Logic in Multi-Agent Systems (held in conjunction with AAMAS 2006).  May 8,9 2006, Future University, Hakodate, Japan


FLAIRS 06, Track on Secure Multiparty Computations and Distributed Constraint Reasoning.  May 11-13, 2006, Holiday Inn Melbourne Beach, FL, USA


INCOM06, 12th IFAC Symposium on Information Control Problems in anufacturing (a Series of Special Sessions on Value-Chain Optimisation using Constraint Programming).  May 17 - 19, 2006, Saint-Etienne, France.


CP-AI-OR'06, The Third International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems.  May 31-June 2, 2006, Cork, Ireland.


ICAPS-06, The 16th International Conference on Automated Planning and Scheduling.  June 6-10, 2006, The English Lake District, Cumbria, U.K.


PPSWR @ ESWC 06, 4th Workshop on Principles and Practice of Semantic Web Reasoning (Co-located with ESWC'06).  10-11 June, 2006, Budva, Montenegro.


CSCLP 2006, 11th ERCIM Workshop on Constraint Solving and Constraint Logic Programming.  June 26-28, 2006, Caparica, Portugal.  Paper submission deadline: May 5th, 2006. 


AITOCP 2006, "Artificial Intelligence Techniques for Optimization and Constrained Problems" at the International Conference on Artificial Intelligence IC-AI 2006.  June 26-29, 2006, Monte Carlo Resort, Las Vegas, USA.  Emails: mtounsi@cis.psu.edu.sa (Dr. Mohamed Tounsi) and souis@ccis.imamu.edu.sa (Dr. Samir Ouis)

AMAST 2006, 11th International Conference on Algebraic Methodology and Software Technology (co-located with MPC'06).  5-8 July 2006, Kuressaare, Estonia.


Calculemus'06, 13th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning 2006 (Co-located with ISSAC 2006).  July 7-8, 2006, Genova, Italy.  Submission of title and abstract: April 8, 2006.

Submission of papers: April 15, 2006.


CHR 2006, Third Workshop on Constraint Handling Rules (Co-located with ICALP 2006).  July 9, 2006, S. Servolo, Venice, Italy

Paper submission deadline: May 7, 2006.  http://www.cs.kuleuven.be/~toms/CHR2006/

ISSAC 2006, International Symposium on Symbolic and Algebraic Computation.

July 9 - 12, 2006, Genoa, Italy


ACM PPDP 2006, 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming.  July 10-12, 2006, Venice, Italy.


The AAAI-06 Workshop on Learning for Search.  July 16/17, 2006, Boston, Massachusetts. 


AAAI-06, Twenty-First National Conference on Artificial Intelligence.  July 16-20, 2006, Boston, Massachusetts, USA.


ISMP 2006, 19th International Symposium on Mathematical Programming.  July 30 to August 04, 2006, Rio de Janeiro, Brazil

Abstract submission deadline: June 10, 2006. 


PRICAI'06, The Ninth Pacific Rim International Conference on Artificial Intelligence.  7-11th August, 2006, Guilin, China.


WRS06, The Sixth International Workshop on Reduction Strategies in Rewriting and Programming.  August 11, 2006, Seattle, Washington. 

Abstract Submission: May 8, 2006. 

Paper Submission: May 15, 2006.


SAT 2006, 9th International Conference on Theory and Applications of Satisfiability Testing.  August 12 - 15, Seattle, Washington, USA.


WST 2006, Eighth International Workshop on Termination (Part of FLoC 2006).

15-16 August, 2006, Seattle, Washington. 

Paper submission deadline: May 19, 2006. 


IJCAR 2006, Third International Joint Conference on Automated Reasoning. August 16-21, 2006, Seattle, USA


ALPSWS2006, International Workshop on Applications of Logic Programming in the Semantic Web and Semantic Web Services (co-located with ICLP06).  16 August, 2006, Seattle, Washington, USA

Paper submission deadline: 12 May 2006.  http://www.deri.at/events/workshops/alpsws2006

International Workshop on Preferences and Their Applications in Logic Programming Systems (held in conjunction with ICLP06).  August 16, 2006, Seattle, Washington.  Paper Submission Deadline: May 15th, 2006.


ICLP'06 Doctoral Consortium, 22nd International Conference on Logic Programming (Part of Fourth Federated Logic Conference, FLoC 2006).  17-20 August, 2006, Seattle, Washington, USA

Submission deadline: April 1, 2006. 


Search and Logic: Answer Set Programming and SAT (A Workshop affiliated with ICLP-06 and FLoC-06).  August 16, 2006, Seattle, Washington, USA.

Paper Submission: May 22, 2006. 


ICLP'06, 22nd International Conference on Logic Programming (Part of Fourth Federated Logic Conference, FLoC 2006).  17-20 August, 2006, Seattle, Washington, USA


Workshop on Modelling and Solving Problems with Constraints 2006 (Co-located with ECAI 2006).  29th August 2006, Riva del Garda, Italy.

Paper submission deadline: 15 April 2006.


INFERENCE METHODS BASED ON GRAPHICAL STRUCTURES OF KNOWLEDGE (a one day ECAI workshop).  29th August 2006, Riva del Garda, Italy

Paper submission deadline: April 15, 2006. 


Multidisciplinary ECAI-06 Workshop on ADVANCES IN PREFERENCE HANDLING.  Aug 28th - Aug 29th, 2006, Riva del Garda, Italy

Paper submission deadline: April 15, 2006. 


ECAI 2006 Workshop on Configuration.  August 28 - 29, 2006, Riva del Garda, Italy

Paper submission deadline: April 15th, 2006.


ECAI 2006, 17th European Conference on Artificial Intelligence.  August 28th - September 1st 2006, RIVA DEL GARDA, Italy


SAS'06, The 13th International Static Analysis Symposium.  29-31 August 2006, Seoul, Korea

Paper submission deadline: 7 April 2006.


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


OR 2006, International Conference Operations Research, special interest section "logistics and transport".  September 6th to 8th, 2006, University of Karlsruhe, Germany

Abstract submission deadline: April 30th, 2006.

Full paper submission deadline: July 31st, 2006. 


AIMSA 2006, The 12th International Conference on Artificial Intelligence: Methodology, Systems, Applications.  13-15th September, 2006, Varna, Bulgaria.  Paper submission deadline: April 15, 2006.


CP 2006 CALL FOR WORKSHOP AND TUTORIAL PROPOSALS.  September 25th-29th, 2006, Nantes, France

Workshop Proposal submission deadline: March 31, 2006. 

Tutorial Proposal submission deadline: May 19, 2006.


CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Sept 25-29, 2006, Nantes, France

Paper submission deadline: Apr 21, 2006. 


AISC-2006, AI and Symbolic Computation, September 20-22, 2006, Beijing, China

Paper submission deadline: April 7, 2006.


CSL'06, Annual Conference of the European Association for Computer Science

Logic.  September 25 -- 29, 2006, Szeged, Hungary

Title & Abstract Submission deadline: 24 April, 2006. 

Full Paper Submission deadline: 1May, 2006. 


ADVIS 2006, Fourth Biennial International Conference on Advances in Information Systems, 18-20 October, 2006, Izmir, Turkey

Paper submission deadline: April 1, 2006. 


LPAR-13, The 13th  International Conference on Logic for Programming Artificial Intelligence and Reasoning.  13th-17th November, 2006, Phnom Penh, Cambodia.  Submission of full paper abstracts: 2nd May, 2006.

Submission of full papers: 9th May, 2006.


MICAI 2006, 5th Mexican International Conference on ARTIFICIAL INTELLIGENCE.  November 13-17, 2006, Mexico

Paper submission deadline: June 2, 2006. 


AI 2006, the 19th ACS Australian Joint Conference on Artificial Intelligence.  December 4 - 8, 2006, Hobart, Tasmania, Australia

Paper submission deadline: June 30, 2006. 


AI-2006, Twenty-sixth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence.  December 11th - 13th, 2006, Cambridge, UK.  Paper/Poster Submission: 5th June, 2006.


IJCAI-07, Twentieth International Joint Conference on Artificial Intelligence.  January 6-12, 2007, Hyderabad, India

Paper submission deadline: June 30th, 2006. 


CP 2007, 13th International Conference on Principles and Practice of Constraint Programming (co-located with ICAPS 2007).  Fall, 2007, Providence, RI, USA.  Conference chairs: Meinolf Sellmann and Laurent Michel. 

Program chair: Christian Bessiere.



Career news


·        Post-Doc position WEIGHTED CONSTRAINT PROCESSING Applied mathematics and computer science department Toulouse INRA FRANCE


A 2 years postdoc position is available in our lab. in the Applied Mathematics and Computer sciences dept. at INRA in the frame of a ANR (french NSF) founded project. The project is aimed at the development, implementation and experimentation of algorithms for solving weighted constraint networks by mixing local consistency enforcing and dynamic programming like approaches. It involves three teams with a nice research record in graph decomposition, weighted constraint processing and the use of decomposition for solving weighted constraint networks and with active relations with other teams in France, Italy, Spain...


The project offers a nice spectrum of research from graph theory, development of new algorithms for weighted constraint processing, their implementation in a new platform and application to problems in biology (pedigree analysis, RNA gene finding...) using recent hardware with a large memory.


The ideal applicant will have a good knowledge of constraint processing and a taste for algorithmic development from theory to practice. Programming skills are essential. Additional knowledge in weighted constraint processing, graph decomposition and related methods is welcome. General knowledge of biology and genetics is welcome but not essential. French or english speaking is needed.


The contract should start around June 2006 (with some flexibility) and is renewable for a total duration of 2 years roughly.


Prospective applicants should contact Thomas Schiex

(http://www.inra.fr/mia/T/schiex) by phone or e-mail before March 26th,

2006. Use [ANR POSTDOC] for the e-mail subject.



University of Ulm, Germany


A research position is available for Ph.D. students or postdocs at the Faculty of Computer Science, University of Ulm, Department of Software Engineering and Compiler Construction in the area of Constraint Handling Rules (CHR).


The successful applicant will be responsible for a research project funded by the German Research Foundation DFG. Its topic is the specification, generation, implementation and analysis of rule-based algorithms for solving of global   constraints in CHR. The position thus requires knowledge and interest in one or more of the aforementioned areas.


At least a master or equivalent in computer science or strongly related area is required. The initial appointment will be for two years, beginning as soon as possible, with a possible renewal for another two years depending on the evaluation of the research foundation.


Gross salary is 56.400 Euro a year according to assistant position BAT IIa. It includes health and social insurance. Additional money for conference travel and visit of the advanced summer school on global constraints will be provided.


Ulm is a pleasant city of 150.000 on the Danube, with nearby rocks for free-climbing, close to Stuttgart, Munich, the Alps, and Lake Konstanz. Every day   life requires a basic command of German.


Prospective applicants should email their resume with three references, and link to homepage and publications if available, to our secretary Claudia Hammer at



  by February 28th, 2006,

  or until the position is filled.



  Prof. Thom Fruehwirth

  c/o Claudia Hammer

  University of Ulm

  Faculty of Computer Science

  Department PM

  D-89069 Ulm, Germany


·        Potential Postgraduate Scholarship at Cork Constraint Computation Centre (4C)


We are looking for people with an excellent academic background that have experience and strong interest in constraint programming and/or other fields of artificial intelligence. The EMBARK POSTGRADUATE  RESEARCH Scheme (http://www.ircset.ie/grant_schemes/postgrad.html) creates an opportunity to conduct your study at Cork Constraint Computation Centre (4C): www.4c.ucc.ie  Our  centre is located in Ireland and is the world biggest research lab in its domain. If interested in using the Embark Initiative Postgraduate Research Scholarship Scheme (2006) at 4C, the applicant should contact me on tnordlan"at"4c.ucc.ie.


Best regards,




  Dr. Tomas Eric Nordlander,

  Cork Constraint Computation Centre (


  University College Cork, 

  College Rd, Cork, Ireland.


  Tel:    +353-(0)21-4255405  

  Fax:    +353-(0)21-4255424  

  E-Mail: tnordlan"at"4c.ucc.ie

  Web:    http://4c.ucc.ie


·        1-year scholarship at the University of Padova


An opening is available for a 1-year scholarship, for people with at least 3 year of research experience after their undergraduate studies, within the group on constraint reasoning led by Francesca Rossi at the University of Padova, Italy. The work should start on June 1, 2006.


The research directions that are currently considered in this group are: constraints, soft constraints, CP-nets, preferences, bipolar preferences, preference aggregation, social choice, game theory. Further information about these lines of work can be found at the URL  http://www.math.unipd.it/~frossi/research.html


Anybody interested in this scholarship should contact Francesca Rossi (frossi@math.unipd.it) before April 10, 2006 for further information on how to apply. The formal application procedure will be opened by the end of March and will close 20 days later.


  • 3 research positions may be available in the Research Group on Mathematical Linguistics at Rovira i Virgili University (Tarragona, Spain) under the Ramon y Cajal scheme, which is partially funded by the Spanish Ministry for Education and Science.

The web site of the host institute is:


ELIGIBLE TOPICS (in decreasing order of priority)

- Language and automata theory and its applications.

- Biomolecular computing and nanotechnology.

- Bioinformatics.

- Language and speech technologies.

- Formal theories of language acquisition and evolutionary linguistics.

- Computational neuroscience.

Other related fields might still be eligible provided there are strong enough candidates for them.


- The positions are intended for experienced scientists willing to develop an academic career in the framework of the host institute for 5 years, starting in 2006-2007.

- They will be filled in under the form of a work contract.

- After evaluation of the 5-year performance, it is likely that the positions will become permanent.

- Doctoral teaching and supervising are expected, as well as a strong involvement in the institute’s activities.

- Only candidates having a high publication record will be considered.


- Having been awarded the PhD degree not earlier than April 4, 1996  and not later than December 31st, 2004.


- Annual salary amounting 31,650 euros in the first year, before taxes (at a rate of 18%, approximately).

- Up to 15,000 euros in the first two years for research expenses.

- Full Social Security rights, including health assistance for the researcher and her/his family.


It will consist of 2 steps:

- a pre-selection based on CV and carried out by the host institute,

- an application by the shortlisted candidates, including essentially CV and a research project, to be assessed by the Spanish Ministry for Education and Science.


Expressions of interest are welcome until March 26, 2006. They should simply contain the candidate's CV and mention "2006-2" in the subject line. The outcome of the pre-selection will be reported immediately after.

Pre-selected candidates will be supported in the application process by the host institute. The deadline for completing the whole process is March 31st, 2006.

Final results will be known in July 2006.


Carlos Martin-Vide