<center> <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)
- news: CP05, CP06, CP elections ..
- publications: PhD theses, recent books
- events: forthcoming conferences and workshops
- career news: job adverts
- reports: AI&Maths 04
- profiles: Nantes
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
(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
Santiago Macho Gonzalez, "Open Constraint Satisfaction", EPFL
Symmetry breaking ordering constraints, Uppsala University
Constraints, local search and computer assisted composition. University Paris 7.
Principles of Constraint Programming,
Cambridge University Press (August 2003), xiv + 407 pages.
Morgan Kaufmann (May 2003) , 480 pages.
Thom Fruhwirth, Slim Abdennadher
Essentials of Constraint Programming
Series: Cognitive Technologies, Springer Verlag (2003),
IX, 145 p. 27 illus.,
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.
Seventh International Conference on Theory and Applications
of Satisfiability Testing. 10-13 May 2004, Vancouver, Canada
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.
14th International Conference on Automated Planning &
Scheduling. June 3-7 2004, Whistler, British Columbia, Canada.
1st International Symposium on Applications of Constraint
Databases (in conjunction with SIGMOD-PODS 2004). June 12 - 13, 2004,
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.
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
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
2004, Saint-Malo, France. Workshop Coordination: Frank Valencia
MultiCPL 2004, 3rd International Workshop on Multiparadigm Constraint
Programming Languages (held in conjunction with
2004, Saint-Malo, France. Paper submission deadline: May 9, 2004.
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.
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.
Tenth International Conference on Principles and Practice of
Constraint Programming, 27 September - 1 October 2004, Toronto, Canada
Paper submission deadline: 16 April.
Second International Mozart/Oz Conference (MOZ 2004). 7-8 Oct,
2004, Charleroi, Belgium. Paper submission deadline: 9 July.
16th International Conference on Automated Planning &
Scheduling. Call for Proposals deadline: 21 May 2004.
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
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 .)
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.
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++
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:
- the CoCoA theme (Continuous Constraints and Applications) of the University of Nantes (http://www.sciences.univ-nantes.fr/lina/ )
- the CD theme (Discrete Constraints) of the Ecole des Mines de Nantes (http://www.emn.fr/)
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.
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:
- 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.
- 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.