Volume 1, Number 0, January 2005


  <h2>Constraint Programming News</h2>

  <h3>volume 1, number 0, Jan 2005</h3>

  <h4>Editors: <br>

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,


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


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


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


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


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


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


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


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


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.