Volume 1, Number 0, January 2005

Constraint Programming News

volume 1, number 0, Jan 2005

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


  • news: CP online, CP 2005
  • publications: books, PhD theses, online journals, special issues, software
  • events: forthcoming conferences and workshops
  • career news: Postdoc and PhD jobs at Montpellier, PARC, Namur, NICTA (Melbourne), Vidus (Ipswich), KTH (Stockholm), IRST (Trento)
  • reports: Workshop on Graph and Hypergraph Decompostions
  • profiles: Lisbon Constraint Programming Group


Welcome to the second year 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 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.

Another initiative supported by the CP organizing committee is a new web portal, CP online. This is designed to be a single place for information about constraint programming. Please visit this site, and add your news, conferences announcements, online resources, etc.

CP-2005 will be held in Sitges (near Barcelona) on 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. Michela Milano and Zeynep Kiziltan will chair the Doctoral Programme. Submissions due (approx) May 6th 2005.

CP-2006 will be held in Nantes in 2006. Frederic Benhamou will be the program chair.



K.R. Apt, F. Fages, F. Rossi, P. Szeredi and J. Vancza (editors) Recent Advances in Constraints. Lecture Notes in Computer Science 3010, Springer (2004), vii + 284 pages.

PhD theses:

Sebastian Brand, Rule-Based Constraint Propagation: Theory and Applications, CWI, The Netherlands, 2004.

Ludovic Langevine, Observation de programmes par contraintes et traces d'exécutions : une sémantique générique et une architecture d'analyse dynamique., Some chapters of this thesis are written in English: the technical chapters, 4, 5, 6, and 7, and the Appendix C. INRIA, France, 2004.

Online journals:

Theory and Practice of Logic Programming (TPLP) now free online

If you are a TPLP author who might recall that the Cambridge University Press has agreed that the accepted versions of the TPLP submissions are posted in the Computing Research Repository (CoRR),

We are happy to inform you that thanks to this provision we now have a free online version of TPLP that also includes all book reviews published in TPLP. This online version can also be reached through the home page of the Association for Logic Programming in Leuven,

We would like to thank Qiu Jiang, a student at the National University of Singapore, for creating the website and adding to CoRR the accepted versions of the `missing' papers. We hope that this small contribution of the logic programming community will inspire others in promoting a free access to scientific literature.

We plan to maintain this free online version of TPLP and appeal to prospective TPLP authors to keep helping us in this endevour.

Krzysztof Apt, Maurice Bruynooghe, and Bart Demoen.

Special issues:

Hybrid Metaheuristics. Special issue of the Journal of Mathematical Modelling and Algorithms. Guest editors: Christian Blum, Andrea Roli, and Michael Sampels. To appear in 2005.

Combining Logical Systems. Special issue of Information and Computation. Guest editors: Alessandro Armando and Christophe Ringeissen. Submission deadline: January 22, 2005.

Journal of Heuristics, Special issue on Preferences and Soft Constraints. Guest editors: S. Bistarelli and F. Rossi. Paper submission deadline: February 27th, 2005. Submissions are to be made electronically, by using the Springer online manuscript submission system of the Journal of Heuristics.


Cardinal, a sets constraints solver with especial inferences on set functions, such as cardinality, is available as an ECLiPSe Prolog third party library (packaged with ECLiPSe 5.7 and newer).


ICS2005, The Ninth INFORMS Computing Society Conference. January 5-7, 2005, Annapolis, Maryland USA.
PADL 05, Seventh International Symposium on Practical Aspects of Declarative Languages 2005 (co-located with ACM POPL 2005). January 10-11, 2005, Long Beach, California, USA.
VMCAI'05, 6th Int. Conf. on Verification, Model Checking and Abstract Interpretation. January 17-20, 2005, Paris, France.
W(C)LP 2005, 19th Workshop on (Constraint) Logic Programming. 21-25 February, 2005, University Ulm, Germany.
RCA'2005, Reliable Computations and their Applications (a Technical Track at the 20th ACM Symposium on Applied Computing SAC'2005). March 13 - 17, 2005, Santa Fe, New Mexico, USA.
LPAR-11, The 11th International Conference on Logic for Programming Artificial Intelligence and Reasoning. March 14-18, 2005, Montevideo, Uruguay.
CSP 2005: Track on Constraint Solving and Programming part of the 20th Annual ACM Symposium on Applied Computing SAC'2005 Santa Fe, New Mexico, March 13 -17, 2005.
UNIF'2005, The 19th UNIF workshop (collocated with RTA'05 and TLCA'05 as part of RDP'05). April 19--21, 2005, Nara, Japan. Paper submission deadline: January 28, 2005.
RTA'05, The 16th Int. Conf. on Rewriting Techniques and Applications (co-located with TLCA'05 as part of RDP'05). April 19--21, 2005, Nara, Japan.
FLAIRS, Technical Track on Constraint Solving and Programming, 18th International FLAIRS Conference, 2005). May 16-18, 2005, Clearwater Beach, Florida, USA.
FLAIRS, Technical Track on Secure Multiparty Computations and Distributed Constraint Reasoning, International FLAIRS Conference, 2005). May 16-18, 2005, Clearwater Beach, Florida, USA.
CP-AI-OR 2005, International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Prague, Czech Republic. May 30 - June 1, 2005. Paper submission deadline: January 16 2005.
CPPS-05, Workshop on Constraint Programming for Planning and Scheduling (to be held alongside ICAPS-05). June 5th-10th 2005, Monterey, California, USA. Paper Submission: Feb 21st, 2005.
VVPS'05, 1st Workshop on Verification and Validation of Model-Based Planning and Scheduling Systems (held in conjunction with ICAPS 2005). June 6, 7 - 2005, Monterey, California, USA. Paper submission deadline: April 18, 2005.
ICAPS 2005, International Conference on Automated Planning & Scheduling, June 5 - 10, 2005, Monterey, California, USA. Papers due on 15 November, 2004. Deadline for Doctoral Program application is February 23, 2005. Software demos due on 21 March, 2005. Poster session submissions due on March 14, 2005. (Competition in Knowledge Engineering for Planning submission due on March 21st 2005, )
SAT-2005, Eighth International Conference on Theory and Applications of Satisfiability Testing (co-located with 2005 SAT SOLVER COMPETITION and 2005 QBF SOLVER EVALUATION). June 19-23 2005, St Andrews, Scotland. Paper submission deadline: February 20, 2005.
TIME 2005, The 12th International Symposium on TEMPORAL REPRESENTATION AND REASONING. June 23-25, 2005, Burlington, Vermont, USA. Paper submission deadline: January 22, 2005.
PPDP05, Seventh ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming. 11-13 July 2005, Lisboa, Portugal. Paper submission deadline: 13 February 2005.
MISTA 2005, 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications. 18 - 21 July 2005, New York, USA. Paper submission deadline: 21st January 2005.
AAMAS 2005, 4th International Joint Conference AAMAS on Autonomous Agents and Multiagent Systems. July 25 - 29, 2005, Utrecht University, The Netherlands.
SARA'2005, Symposium on Abstraction, Reformulation and Approximation. July 26th to 29th, 2005, Radisson SAS Airth Castle & Hotel, Stirlingshire Scotland, UK. Paper submission deadline: February 25, 2005.
IJCAI-05 Workshop on Advances in Preference Handling. July 30 to August 1, 2005, Edinburgh, Scotland. Paper submission deadline: March 24, 2005.
The Fifth Workshop on Modelling and Solving Problems with Constraints (to be held at IJCAI 2005). July 30-August 1, 2005, Edinburgh, Scotland. Paper submission deadline: April 23, 2005.
JCAI 2005 Workshop on Configuration (to be held at IJCAI 2005). July 30-August 1, 2005, Edinburgh, Scotland. Paper submission deadline: March 8, 2005.
IJCAI-05, Nineteenth International Joint Conference on Artificial Intelligence. 30 July-5 August 2005, Edinburgh, Scotland. Paper submission deadline: February 15, 2005.
CSL'05, The 14th Annual Conference (and 19th International Workshop) in Computer Science Logic. 22-25 August 2005, University of Oxford, UK. Paper submission deadline: 1 April, 2005.
MOZ 2004, Second International Mozart/Oz Conference (MOZ 2004). 7-8 Oct, 2004, Charleroi, Belgium. Paper submission deadline: 16 July, 2004.
FroCoS 2005, 5th International Workshop on Frontiers of Combining Systems. September 19-21, 2005, Vienna, Austria. Paper submission deadline: May 9, 2005.
CP 2005, 11th International Conference on Principles and Practice of Constraint Programming, October 1-5 2005, Sitges, Spain. Co-located with ICLP and an annular eclipse. Program chair: Peter van Beek. Conference chairs: Pedro Meseguer and Javier Larrosa.
CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Fall 2006, Nantes, France. Program chair: Frederic Benhamou.

Career news

Assistant Prof and Prof at Univ. of Montpellier

There is a high probability that a position for an assistant professor ("maitre de conferences" in french) and for a professor will be opened next spring at the university of Montpellier. Applicants will be asked to show connections with the topics studied in the constraint programming group of Montpellier.

People interested in these positions must have some basic knowledge of french. In addition, to be allowed to be a candidate next spring, applicants must have received the "qualification" label from the french government. This qualification is a very light procedure, but it has to be done **** before October 19th, **** on the Antares web site.

People who would like more information or help for the qualification procedure should contact Christian Bessiere (bessiere@lirmm.fr).

PostDoc at Palo Alto Research Center (PARC)

Embedded Reasoning Group

We invite applications from candidates with research interests in artificial intelligence or intelligent control. Relevant areas include diagnosis, reasoning under uncertainty, multi-agent and distributed systems, planning and scheduling, constraint reasoning, distributed control, and multi-objective optimization. A PhD or substantial relevant experience is required. For more information, please see here.

A subsidiary of Xerox, PARC offers a multidisciplinary environment for pursuing both basic and applied research. Our funding comes from both corporate sources and government agencies. PARC is an Equal Employment Opportunity company committed to workforce diversity.

TA and PhD at Univ. of Namur

The University of Namur (FUNDP) opens a research and teaching assistant position in the domain of programming (in a wide acceptance).

The job is 50% of PhD research. We ask the candidate to state his research interests and propose the plan of a PhD in his application. This plan is just indicative, it will help us to select the PhD supervisor and the real plan. Thus, the topic should match the research interests of one or several of the following academics:

  • Wim Vanhoof. Program analysis, program transformation, program generation and synthesis, advanced compilation, program specialization, program optimization, abstract interpretation
  • Jean-Marie Jacquet. coordination languages, constraint logic programming, semantics of concurrent languages.
  • Naji Habra. software quality
  • Pierre Yves Schobbens specification languages, UML, agent logics, verification, model checking, proof of programs
50% of teaching, mainly exercises for courses in the programming area. Typical examples are: compiler construction, program proofs, object-oriented programming in Java, etc.

Applicants should have a master degree in computer science. The job starts in Jan 2005 for 6 years. Applicants should ask for an application form from: Service du Personnel des FUNDP, rue de Bruxelles 61, B-5000 Namur (Tel.: +32 81/72 40 42) and return it there filled and with a CV, list of publications and a PhD plan proposal before 15 december 2004.

For more information contact the head of the Programming Department, Pierre Yves Schobbens.

PostDocs at National ICT Australia

NICTA is Australia's national research centre in Information and Communications Technology (ICT), with a focus on fundamental and use-inspired research.

Openings withing the Network Information Processing Program. Constraint Programming, Researchers Levels B and D

The Network Information Processing Program of NICTA Victoria Laboratory has a research focus on building a robust, efficient and flexible constraint programming platform. Constraint programming will be used as a technology to tackle combinatorial problems arising in all facets of networks: for example, routing, scheduling, and ad- hoc network generation.

The constraint programming research project will be lead by Professor Mark Wallace and includes Professor Peter Stuckey, Professor Michael Maher, Professor Kim Marriott, Dr Zoltan Somogyi, and Professor Toby Walsh as active participants. The starting point for the project is the existing HAL and Mercury languages developed here in Melbourne. The aim is to build an environment which will dramatically enhance the productivity of applications problem solvers and algorithm developers, and enable us to tackle more complex problems than ever before.

The program is seeking to build a team of constraint programmers to drive this exciting project, and subsequently have four positions available, for one Principal Researcher D (4 year fixed term) and three Researcher B (2 x 2 year fixed term & 1 x 4 year fixed term).

Applications: Please visit NICTA Careers to view the criteria essential to the positions and apply online. Enquiries to peter.stuckey@nicta.com.au. Closing date: 20 January 2005.

Vidus, Ipswich, England

Job Opportunity for Scheduling/Optimisation Expert in Ipswich, England.

Vidus requires a highly experienced scheduling/optimisation expert to join a small team responsible for the conceptualisation, and down streaming into product, of novel scheduling algorithms and architectures. Vidus, located in Ipswich, England, is the leading company in the area of mobile resource scheduling for telecom and utility environments. The expert will contribute to the delivery of major enhancements to taskforce, the company's core scheduling product.

The candidate should demonstrate expertise in Local Search and Constraint Based Scheduling techniques. The role also requires at least 3 years development experience in Java and/or C++. Experience using UML would also be an advantage.

Our standard terms of employment include performance bonus, stock options - we think it's important that everyone has a stake in the business - pension, private healthcare insurance, life assurance, long term incapacity benefits, personal accident insurance and 25 days holiday (plus public holidays).

If you are interested in applying please mail your CV to: julie.fryatt@vidus.com Further information about the position can be obtained from Bob Laithwaite (bob.laithwaite@vidus.com)

Applicants for the above position must be eligible to work in the UK and CVs from agents will not be considered.

PhD at KTW, Sweden

A PhD position in the area of constraint programming is open for application at the Department of Microelectronics and Information Technology (IMIT) of the Royal Institute of Technology (KTH) in Stockholm, Sweden.

For more information, please consult here.

Researcher and Programmer Positions at ITC-irst

The MathSAT team at ITC-irst and at University of Trento is seeking a young researcher and one/two programmers to join the ORCHID project. The positions last one year, are renewable for two more years, and are already open. Monthly salaries vary depending on age, qualification, and experience.

MathSAT is a decision procedure for logic theories combining boolean propositions with constraints over integer and real variables, and uninterpreted functions. It has been applied in different real-world application domains, ranging from formal verification of infinite state systems (e.g. timed and hybrid systems) to planning with resources, equivalence checking and model checking of RTL hardware designs. The MathSAT family of deciders is based on the extension of a DPLL-like propositional satisfiability procedure, used as an assignment enumerator. MathSAT pioneers a lazy and layered approach, where propositional reasoning is tightly integrated with solvers of increasing expressive power, in such a way that more expensive layers are called less frequently. Formal methods are widely applied as powerful verification and early debugging techniques in the development of complex industrial systems. In particular, formal checking at Register-Transfer Level (RTL) is currently a fundamental step in the design of hardware circuits. Most tools for formal checking, however, work at the boolean level, which is not expressive enough to capture the abstract, high level (e.g., structural, word level) information of RTL designs. Tools for formal checking are thus confronted with problems which are "flattened" down to boolean level so that a predominant part of their computational effort is wasted into brute force reasoning at boolean level. Thus, the checking process would greatly benefit from the ability to represent and exploit higher level informations.

The goal of the ORCHID project (Enhanced Formal Checkers for RTL Circuit Designs) is to investigate enhanced SAT-based techniques for RTL formal checking and to deliver better verification tools for RTL designs. These tools will avoid flattening by working directly at a level of expressivity higher than boolean reasoning, and will be able to analyze larger scale RTL designs. The results of the research will be applicable to the extension of any existing formal checkers based on SAT procedures.

The project is carried on with the external collaboration of the Logic and Validation Technologies, Intel Architecture Group in Haifa, Israel.

The project has open positions for a young researcher and a programmer.

Applications should be sent via email to: mathsat-recruit@itc.it using 'ORCHID: application' as subject, and including a statement of interest and a CV. PostScript, PDF, or plain text formats are encouraged. Please use the above address also for further inquiries.

Young researcher:

The activity of the young researcher will include design and implementation of new algorithms and functionalities, their integration into the MathSAT solver, the preparation of project deliverables. Publication of scientific papers will be a primary objective.

Important research objectives include: improving the efficiency of MathSAT by enriching it with new algorithms; extending the expressivity of MathSAT, with new constructs (including, e.g., bitwise operators and memories); developing new integration algorithms and/or improving current ones; developing and implementing new verification tools using MathSAT as a back-end.

The ideal candidate should have a Ph.D. in either computer science, mathematics, electronic engineering or similar topics, and be able to work in a collaborative environment, with a strong commitment to achieving assigned objectives and reaching research excellence.

Background and/or previous experiences in the areas of formal verification, boolean reasoning, deduction systems, hardware description languages, are desired. Good skills in programming in C/C++ and software developing are also desired.


The activity will include the implementation of new algorithms and functionalities, their integration into the MATHSAT solver, maintenance, and benchmarking.

We encourage the application from young, talented master students who may be interested in pursuing a Ph.D. at the International School on Information and Communication Technologies at the University of Trento.

The ideal candidates must have very good skills in programming in C/C++ and software developing, and be able to work in a collaborative environment, with a strong commitment to achieving assigned objectives. Background knowledge and/or previous experience in the areas of formal verification, boolean reasoning, deduction systems, hardware description languages, though not mandatory, will be considered favourably.


President of Ireland Young Researcher Award (PIYRA) 2005 Up to 1.2M euros. Applications worldwide welcome.

CP or AI researchers can contact Gene Freuder, e.freuder@4c.ucc.ie for further info. Final D


The workshop on Graph and Hypergraph Decompostions - Methods and Applications in Computer Science was organized jointly by the Wolfgang Pauli Institute (Austria), Laboratoire GREYC CNRS UMR 6072 (France), and Vienna University of Technology (Austria). The organizing committee -composed of Georg Gottlob, Etienne Grandjean, and Nysret Musliu -invited around 31 researchers from all over the world for a two days and a half programme from December 16 till December 18. The invited researchers came from different research communities such as complexity theory, graph and hypergraph decompositions, constraint satisfaction problems and constraint programming, database, mathematics, etc. This mix of disciplines was also reflected in the talks. In particular, the first session was devoted to Graph and Hypergraph Decompositions and Constraint Satisfaction. Rina Dechter presented her AND/OR paradigm that exploits tree-decomposition in search while Dave Cohen talked about structural decompositions of CSP instances. Stefan Szeider presented his work on Dulmage-Mendelson decompositions and SAT. The other sessions covered areas such as tree and hypertree decompositions, trees/hypergraphs and queries, clique-width and acyclicity, the complexity of directed graphs, geometrical aspects of hypergraphs, and matriods. Overall, the workshop created a nice atmosphere for various researchers from various areas to interact and exchange ideas and the organization was excellent!


The Lisbon Constraint Programming Group is an informal research group within the Centre for Artificial Intelligence of the New University of Lisbon. Research includes a number of topics within Constraint Programming, ranging from theory to applications and including the development of dedicated constraint solvers for different domains. A full report on the group and its activities is available here.