Volume 0, Number 1, April 2004

Constraint Programming News

volume 0, number 1, April 2004

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



Welcome to the first number of CP News, an initiative of the CP organizing committee. We aim to provide a comprehensive summary of important news in the area of constraint programming. The newsletter will be published quarterly on 1st January, 1st April, 1st July, 1st October. Please email the relevant editor with any news, event, report or profile you want published.

The CP organizing committee recently decided that CP-2005 will be held in Sitges (near Barcelona) October 1st to 5th 2005. The conference will be co-located with ICLP. Pedro Meseguer and Javier Larrosa will be local chairs. Peter van Beek will be the program chair. The local organizers have already arranged for an Annular Solar Eclipse to take place in Spain during the conference.

The CP organizing committee also decided that CP-2006 will be held in Nantes in 2006. Eric Monfroy and Frederic Benhamou will be the local chairs.

Each year, the CP community has the opportunity to elect two new members to serve on the CP organizing committe. The committee consists of 10 members: 6 elected members, and 4 members drawn from the current and past local and program chairs. If you wish to stand in this year's election, please send your name and a short election statement to the Secretary of the Organizing Committee, Toby Walsh by 1st June 2004. The electronic elections will be held over the summer and the results announced at CP-2004.

Finally, don't forget. April 19th is the deadline to apply for the CP 2004 Doctoral Programme .This is a forum held during the CP conference to give PhD students visibility and an opportunity to discuss research and career objectives with established researchers. More details here.


PhD theses:

Santiago Macho Gonzalez, "Open Constraint Satisfaction", EPFL

Zeynep Kiziltan, Symmetry breaking ordering constraints, Uppsala University

Charlotte Truchet. Constraints, local search and computer assisted composition. University Paris 7.

Recent books

K.R. Apt Principles of Constraint Programming, Cambridge University Press (August 2003), xiv + 407 pages. ISBN: 0521825830.

Rina Dechter Constraint Processing Morgan Kaufmann (May 2003) , 480 pages. ISBN: 1558608907.

Thom Fruhwirth, Slim Abdennadher Essentials of Constraint Programming Series: Cognitive Technologies, Springer Verlag (2003), IX, 145 p. 27 illus., ISBN: 3-540-67623-6.


CP-AI-OR'04, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems. 20-22 April 2004, Nice, France.
First Workshop on Constraint Handling Rules. May 10 - May 14, 2004, University of Ulm, Germany.
SAT 2004, Seventh International Conference on Theory and Applications of Satisfiability Testing. 10-13 May 2004, Vancouver, Canada
FLAIRS 2004, Special Track on Constraint Solving and Programming. 17-19 May, 2004, Miami Beach, Florida, USA.
CORS/INFORMS 2004 Joint International Meeting, 16-19 May 2004, Banff, Alberta, Canada.
ICAPS 2004, 14th International Conference on Automated Planning & Scheduling. June 3-7 2004, Whistler, British Columbia, Canada.
CDB 2004, 1st International Symposium on Applications of Constraint Databases (in conjunction with SIGMOD-PODS 2004). June 12 - 13, 2004, Paris, France.
PADL'04, Sixth International Symposium on Practical Aspects of Declarative Languages 2004. Jun 18-19, 2004, Dallas, Texas, USA.
CSCLP 2004: Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming, 23-25 June 2004, EPFL, Lausanne, Switzerland Paper submission deadline: 10 May.
AAAI 2004, The Nineteenth National Conference on Artificial Intelligence. July 25 - 29, 2004, San Jose, California, USA.
ECAI 2004 workshop on "Modelling and Solving Problems with Constraints", 22 August 2004, Valencia, Spain. Paper submission deadline: 4 May
ECAI 2004 workshop on "Constraint Satisfaction Techniques for Planning and Scheduling Problems", 23 August 2004, Valencia, Spain. Paper submission deadline: 15 April.
ECAI 2004 workshop on "Configuration", 23-24 August 2004, Valencia, Spain. Paper submission deadline: 1 April.
ECAI 2004 tutorial on "Constraint Processing", Pedro Meseguer, Thomas Schiex 24 August 2004, Valencia, Spain.
STAIRS 2004, 2nd European Starting AI Researcher Symposium. August 23-24, 2004, Valencia, Spain. Paper submission deadline: April 7, 2004.
ECAI 2004, 16th European Conference on Artificial Intelligence (2004). 22-27 August, 2004, Valencia, Spain. http://www.dsic.upv.es/ecai2004/
CICLOPS'04, Colloquium on Implementation of Constraint and LOgic Programming Systems (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Paper submission deadline: April 26, 2004.
COLOPS'04, 2nd International Workshop on COnstraint & LOgic Programming in Security (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Workshop Coordination: Frank Valencia (Frank.Valencia@it.uu.se)
MultiCPL 2004, 3rd International Workshop on Multiparadigm Constraint Programming Languages (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France. Paper submission deadline: May 9, 2004.
ICLP'04, Twentieth International Conference on Logic Programming. 6-10 September, 2004, Saint-Malo, France.
KI2004, 27th GERMAN CONFERENCE ON ARTIFICIAL INTELLIGENCE. September 20-24, Ulm, Germany. Paper submission deadline: April 8.
AISC 2004, 7th International Conference on ARTIFICIAL INTELLIGENCE AND SYMBOLIC COMPUTATION. September 22-24, 2004, RISC (Research Institute for Symbolic Computation), Castle of Hagenberg, Austria. Paper submission deadline: May 1, 2004.
CP 2004, Tenth International Conference on Principles and Practice of Constraint Programming, 27 September - 1 October 2004, Toronto, Canada Paper submission deadline: 16 April.
MOZ 2004, Second International Mozart/Oz Conference (MOZ 2004). 7-8 Oct, 2004, Charleroi, Belgium. Paper submission deadline: 9 July.
ICAPS 2006, 16th International Conference on Automated Planning & Scheduling. Call for Proposals deadline: 21 May 2004.

Career news

Research assistant in planning with incomplete knowledge

We have an opening for a research assistant position in a research project on planning with incomplete knowledge. The goal of the project is the development of techniques for efficient planning under incomplete knowledge and uncertainty, and associated theoretical analysis of computational problems and algorithms. Keywords are AI planning, conditional planning, probabilistic planning, (partially observable) Markov decision processes. The position is in the research group for the Foundations of Artificial Intelligence lead by Prof. Dr. Bernhard Nebel.

Applicants having good background in computer science are asked to apply. Both theoretical knowledge (complexity theory, logics, automated reasoning, Markov decision processes) and good programming skills are appreciated. Prior knowledge and experience in relevant areas of AI (planning, search, automated reasoning) are an advantage.

As a minimum formal requirement the applicants have to have an M.Sc. or a Ph.D. degree or equivalent in computer science. The position is initially for two years, with a possible extension to a third year. Salary is class 2a in the German BAT scale (about 1500 euro a month after taxes for an unmarried person of age 26. More if you are older or married.) For applicants not yet having a Ph.D. degree the position provides possibilities of pursuing one at the University of Freiburg.

Freiburg is a very nice town (pop. 200000) in southwestern Germany in a scenic location very close to France and Switzerland, with good living quality. The university is one of the oldest in Germany (founded 1457), with a new dynamic computer science department. Main airports serving Freiburg are Basel-Mulhouse (1 hour by train or bus) and Frankfurt (2 hours by train.)

Send applications and requests for more information to: Dr. Jussi Rintanen Institut fuer Informatik Albert-Ludwigs-Universitaet Freiburg email: rintanen@informatik.uni-freiburg.de

AI Engineers (advanced configuration and ordering technology)

We are presently looking to hire AI Engineers. Our company develops advanced configuration and ordering technology that changed the way of selling products for companies like The Home Depot, Lowe's Companies and a host of industry leaders.For more information, visit http://www.edgenet.com Our company is located at Nashville, TN, USA. Please email your resume to rajeshATedgenetDOTcom (replace AT by @ and DOT by .)

Job Description:
Responsible for development of functionality that enhances and/or complements the artificial intelligence based, configuration technology. He/she will develop and extend the features of the artificial intelligence engine.

Required Skills: Familiarity with various knowledge representation techniques (frames, description logic, rules, hybrid) Experience in developing inference engines (frames, rules etc.) Experience in developing knowledge based systems (especially with storing KBs in multiple formats (binary files, text files, RDBMSs)) Experience in developing automated knowledge acquistion techniques 2+ years experience in developing/designing complex systems Expertise level in OOD and OOP Minimum 2 years of actual experience with Java/C++
Desired Skills: Familiarity with configuration technology is a big plus Familiarity with constraint satification techniques Familiarity with datamining techniques.


Eighth International Symposium on Artificial Intelligence and Mathematics. Program Chairs: Fahiem Bacchus and Peter van Beek. 4-6 January 2004

The conference was held in a balmy Florida early in January. I had arrived from the southern hemisphere and Florida's winter was hotter than New Zealand's summer. Definitely recommended as one way to escape those winter blues.

The overall standard was good. 30 papers were accepted out of 64 submissions. The topics spanned a range of topics, more so I suspect than in previous years. However, with many papers on SAT, constraints, preferences and search, I was happy. The papers are available online from the conference web site.

In addition, there were 4 special sessions: preferences, portfolio design, AI and game theory, and intelligent text processing.

There were also 3 excellent invited talks. Robert Bixby talked about The New Generation of Mixed-Integer Programming Codes, Ronen Brafman about Preference-Based Constrained Optimization with CP-Nets, and Henry Kautz about SAT as an universal inference engine for AI.

All in all, it was well worth the trip. I recommend you to the next AI & Maths conference in 2006. Toby Walsh.


The Nantes CP community is composed of researchers from two institutions:

These two themes are grouped together in the new CNRS common research structure: the LINA (Laboratoire en Informatique de Nantes Atlantique). All together, this amounts to 13 faculties: N. Beldiceanu, F. Benhamou, M. Christie, P. David, R. Debruyne, C. Jermann, F. Goualard, L. Granvilliers, N. Jussien, C. Mauras, E. Monfroy, T. Petit, E. Poder and about 10 PhD students.

Our main goal is to develop techniques, languages, and tools for discrete and continuous constraints.

Research topics:

We identified three main aspects of our research topics.

  • The first one consists in extending expressivity and efficiency of current systems to process difficult problems such as dynamic systems, real time systems, distributed problems, hybrid problems, ... This aspect is more related to theory and algorithms (e.g., for solvers, cooperative and hybrid solvers, global constraints, explanations, and languages).
  • The second one is technological and is the answer to the strong demand for integrating the constraint technology inside decision-making and engineering environments in collaboration with alternative approaches such as local search or probabilistic methods. We are strongly convinced that in a near future, systems will have to make cooperate numerous components: generic and specific solvers, different forms of problem modeling, strategies, rules, ...
  • Finally, the third aspect is based on technology transfer. Although CP for discrete domains has already penetrated companies, we think we must propose systems that correspond to the needs and methods of the users. More especially, for continuous constraints, we must participate in the development of examplary industrial applications.

More precisely, our research topics are:

Continuous constraints

  • Extensions of interval-based constraint satisfaction techniques, including hybrid (e.g., complete and incomplete methods), cooperative (e.g., symbolic/numeric), and specific (e.g., geometric constraints and exploitation of the semantics of constraints) approaches.
  • A more transverse topic is cooperative problem solving: in terms of theoretical frameworks for cooperation (e.g., various extensions of chaotic iterations for hybrid cooperation, for distributed computations, for efficient filtering algorithms), effective instantiations (symbolic/numeric, local/global, discrete/continuous), component-based software architectures (e.g., for global optimization), solving strategies.
  • Environment (e.g., solution viewer), modeling (e.g., specific languages supporting composition and hierarchies), and specific algorithms (e.g., inner/outer approximations) for applications mainly in constraint-aided conceptual design and camera control.

Discrete constraints

  • Explanations allow addressing different aspects of constraint programming such as coming up with hybrid algorithms, making the technology more accessible, or unifying different types of search procedures.
  • Systematic classification of global constraints should provide a better overview of this domain and allow establishing a systematic link between the properties of basic concepts used for describing global constraints and the properties of the global constraints as a whole.
  • Searching for essential principles from which one can derive several constraint propagation algorithms: this is both true for local consistency algorithms as well as for filtering algorithms for global constraints. In this latter case this is achieved by reusing or adapting existing work on data structure, graph theory, and geometry.
  • Developing a methodology for the semi-automatic development of reliable filtering algorithms. Currently, it is very much a craft with no guaranties regarding the correctness of the filtering algorithms.


ELISA is a C++ library implementing generic constraint algorithms and currently, specific instantiations for continuous constraints.

The PaLM system is a Library implementing explanation based constraint programming as an add-on of Choco.

RealPaver is a system for solving continuous constraints.

GAOL is a C++ interval arithmetic library.

Participation to the Choco constraint kernel which defines a software architecture for variables domains, constraints, propagation and tree search and implements the basics of a constraint system.



  • The ESPRIT COCONUT project: COntinuous CONstraints - Updating the Technology

Partners: Ilog, University of Coimbra, Catholic University of Louvain, University of Vienna, EPFL, University of Darmstadt

  • Bilateral projects with: C. Castro (Chile), J. Garloff (Germany), H. Hosobe (Japan).


  • The RNTL CO2 project: development and integration of an conception-oriented environment for solving constraints

Partners: Dassault Aviation, CRIL Ingénierie, LIP6, ENSAM Talence, ESTIA Bayonne

  • The RNTL OADyMPPaC project: a tool for the dynamic analysis and the debugging of constraints programs Partners: Ilog, Cosytec, INRIA/LOCO, IRISA, LIFO


  • Bouygues, e-lab: explanations for flow algorithms
  • Alrena: specification and validation of a component-oriented approach for constrait programming.

A selection of references:

Mats Carlsson, Nicolas Beldiceanu: From constraints to finite automata to filtering algorithms.ESOP 2004.

Emmanuel Poder, Nicolas Beldiceanu, Eric Sanlaville: Computing a lower approximation of the compulsory part of a task with varying duration and varying resource consumption. European Journal of Operational Research, 2004.

Laurent Granvilliers, Eric Monfroy Implementing Constraint Propagation by Composition of Reductions. ICLP 2003.

Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins: Loading aircraft for military operations. Journal of the Operational Resarch Society, 2003.

Narendra Jussien, Olivier Lhomme: Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 2002.

Marc Christie, Eric Languénou, Laurent Granvilliers Modeling Camera Control with Constrained Hypertubes. CP 2002.

Laurent Granvilliers, Eric Monfroy, Frédéric Benhamou: Symbolic-interval cooperation in constraint programming. ISSAC 2001.

Lucas Bordeaux, Eric Monfroy, Frédéric Benhamou: Improved bounds on the complexity of kB-consistency. IJCAI 2001.

Laurent Granvilliers, Frédéric Benhamou: Progress in the Solving of a Circuit Design Problem. Journal of Global Optimization, 2001.