Volume 0, Number 1, April 2004


  <h2>Constraint Programming News</h2>

  <h3>volume 0, number 1, April 2004</h3>

  <h4>Editors: <br>

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


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



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.



International Conference on Integration of AI and OR Techniques

in Constraint Programming for Combinatorial Optimisation Problems.

20-22 April 2004, Nice, France.


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.


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.


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


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


6-10 September,

2004, Saint-Malo, France. Workshop Coordination: Frank Valencia


MultiCPL 2004, 3rd International Workshop on Multiparadigm Constraint

Programming Languages (held in conjunction with


6-10 September,

2004, Saint-Malo, France. Paper submission deadline: May 9, 2004.


Twentieth International Conference on Logic Programming. 6-10

September, 2004, Saint-Malo, France.


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


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.