Volume 1, Number 2, July 2005

Constraint Programming News

volume 1, number 2, Jul 2005

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


  • news: ACP EC Elections, CP Summer School, Next CP Conferences, CP 2005 Call for Demo
  • CONSTRAINTS journal accepted papers
  • other publications: papers, books, journal, special issues, software
  • events: forthcoming conferences and workshops
  • career news: New MSc, PhD, and Postdoc positions
  • report: CP-AI-OR 2005 (by Michela Milano)
  • profile: Microsoft Research, Cambridge


Welcome to CP News, an initiative of the Association for Constraint Programming.

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.

Election to the EC of the Association for Constraint Programming (ACP)

We seek nominations for candidates for election to the Executive Committee (EC) of the ACP.

Any member of the ACP not already an elected or ex officio member of the EC can stand for election to the EC.  One becomes a member of the ACP by satisfying one of the following conditions (except if explicitly declining):

-          having registered in at least one CP conference in the last five years,

-          being a member of the current program committee of the CP conference,

Candidates must be nominated by members of the current EC or by at least three members of the association.

An elected member can simultaneously hold an ex officio position on the EC (e.g. as an elected member and as the current CP conference chair).  The full rules are set out in the ACP website at: www.a4cp.org

Please send your nomination to Remi Coletta, with supporting emails from an ACP executive committee member, or three members of the ACP, to:


to arrive by (California time) on July 15th 2005.

Summer School on Constraint Programming

The First International Summer School on Constraint Programming will be held September 11-15, 2005 in Hotel Villa del Mare, Acquafredda di Maratea in Italy. The school is supported by the Association for Constraint Programming and CoLogNet. Early registration is April 30th, 2005. For more details, see here.

Next CP Conferences

CP-2005 will be held in Sitges (near Barcelona) on October 1st to 5th 2005. The conference will be co-located with ICLP. Early registration deadline is 1st August. 

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

CP-2005 Call for Demo

This year's CP conference will include a session of demos on industrial and academic applications, or prototypes. One of the aims of this, is to increase the awareness for both industrial and academic researchers of the state of the art in applications within the CP area.  Each demo will be accompanied by a one-page description in the CP 2005 proceedings.

The demo sessions will be part of evening sessions which will include poster and demo presentations. Participants to the demo session will provide their own hardware.

Due to tight deadlines on the proceedings, one page submissions should be emailed in a form ready for publication in LNCS form to:


by 12th July.

The submission should be sent both as a .pdf file and in source form.  The sources for your paper, should be as listed in Springer's instructions for authors.

For LaTeX users this is a gzipped tar archive of the: LaTeX2e file and PS or EPS files for figures, DVI file and the PS file. For other word processing systems, this is an RTF, rich text format, file.  Additionally the email should contain the following information:

-          contact person

-          affiliation

-          short description of the product or prototype

We encourage the submission of demos from both companies using constraint tools, as well as from universities and research labs building prototypes or other constraint based applications.

CONSTRAINTS Journal Accepted Papers

The Constraints Journal publishes 4 times per year. The contents of the final two issues for 2005 are listed below. Links to the authors' final versions of these papers (no subscription required) and to the final published versions (subscription required) can be found at:


Volume 10, Issue 4, Special Issue of the 10th International Conference on Principles and Practice of Constraint Programming

  • Mark Wallace. Introduction to the Special Issue. 10:4, 2005.
  • Nicolas Beldiceanu, Mats Carlsson, Romuald Debruyne, Thierry Petit. Reformulation of Global Constraints Based on Constraint        Checkers. 10:4, 2005.
  • Carla Gomes, Cesar Fernandez, Bart Selman, Christian Bessiere.   Statistical Regimes Across Constrainedness Regions. 10:4, 2005.
  • Pascal Van Hentenryck, Laurent Michel, Liyuan Liu.   Constraint-Based Combinators for Local Search. 10:4, 2005.
  • John Hooker. A Hybrid Method for Planning and Sceduling.  10:4, 2005.
  • Petr Vlim, Roman Bartak, Ondrej Cepek. Extension of O(n log n) Filtering Algorithms for the Unary Resource Constraint to Optional Activities. 10:4, 2005.

Volume 10, Issue 3

  • Irit Katriel, Sven Thiel. Complete Bound Consistency for the Global Cardinality Constraint. 10:3, 2005.
  • Junhu Wang, Rodney Topor, Michael Maher. Rewriting Union Queries Using Views. 10:3, 2005.
  • Gerard Verfaillie, Narendra Jussien. Constraint Solving in Uncertain and Dynamic Environments: A Survey. 10:3, 2005.
  • Martin Cooper. High-order Consistency in Valued Constraint Satisfaction. 10:3, 2005.

Other Publications


Members of this (WATT mailing) list who are working in nurse rostering may be interested in the following recently published survey article:

E.K.Burke, P.De Causmaecker, G.Vanden Berghe and H.Van Landeghem, The State of the Art of Nurse Rostering, The Journal of Scheduling, Volume 7 issue 6, November/December 2004, pages 441-499.

You can download it from the Journal of Scheduling website at:


It includes a classification of nurse rostering problems which we tried to make as comprehensive as possible.  We want to keep this up to date (on the web), so I would be very grateful if you could send me the details of any new nurse rostering papers that appear.

Thanks in advance.

All the best,

Edmund Burke


Stochastic Local Search: Foundations & Applications by Holger H. Hoos, Thomas Stützle.  Hardcover 672 pages, Publisher: Morgan Kaufmann (September 16, 2004). ISBN: 1558608729

399 updated and new slides for free, exercises, extended errata, etc. can be found on the webpage of "Essentials of Constraint Programming"



The Journal of Discrete Algorithms (JDA) aims to facilitate communication between researchers in theoretical computer science who are concerned with the design and analysis of discrete algorithms. The Journal of Discrete Algorithms welcomes original papers in all areas of finite and discrete algorithm design and analysis.

The purpose of this journal is to feature new algorithms and data structures, new analyses or comparisons of known algorithms, complexity studies and well-focussed review articles of currently-active subject areas. Articles in other areas of theoretical computer science will also be considered when there is a clear connection to computational issues.

More information of the journal can be found at:




Guidelines for authors can also be found at:


Special issues:

European Journal of Operational Research, Special Issue on 'Scheduling with Setup Times or Costs'.  Guest editors: Ali Allahverdi and H.M. Soroush.  Paper submission deadline: Dec 31, 2005.


The AVISPA Tool is a push-button tool for the automated validation of Internet security-sensitive protocols and applications.  The AVISPA Tool v1.0 is available at http://www.avispa-project.org.


SMT-COMP'05, 1st International Satisfiability Modulo Theories Competition (CAV'05 Satellite Event).  July 6-10, 2005, Edinburgh, Scotland, UK.

Tenth Annual AAAI/SIGART Doctoral Consortium (co-located with AAAI 2005).  July 9-10, 2005 Pittsburgh, PA.

WIPIS-05, Workshop on "Integrating Planning Into Scheduling" (Held in conjunction with AAAI-05).  July 9-13, 2005, Pittsburgh, Pennsylvania.

AAAI'05, The Twentieth National Conference on Artificial Intelligence. July 9-13, 2005, Pittsburgh, Pennsylvania.

IAAI'05, The Seventeenth Innovative Applications of Artificial Intelligence Conference.  July 9-13, 2005, Pittsburgh, Pennsylvania.

PDMC 2005, 4th International Workshop on PARALLEL AND DISTRIBUTED METHODS IN VERIFICATION (Workshop affiliated to ICALP'05).  July 10, 2005 - Lisboa, Portugal. 

PPDP05, Seventh ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming. 11-13 July 2005, Lisboa, Portugal.

PDMC 2005, 4th International Workshop on PARALLEL AND DISTRIBUTED METHODS IN VERIFICATION.  July 10, 2005 - Lisboa, Portugal.   

IFORS 2005, The IFORS Triennial 2005 Conference of The International Federation of Operational Research Societies.  July 11-15, 2005, Hilton HawaiiVillage, Beach Resort & Spa, Honolulu, Hawaii, USA.

SoftMC 2005: Workshop on Software Model Checking (just after CAV'05).  July 11, 2005, Edinburgh, Scotland. 

BMC'05, Third International Workshop on Bounded Model Checking (affiliated with CAV'05).  July 11, 2005, Edinburgh, Scotland, UK.

PDPAR'05, 3rd Workshop on Pragmatics of Decision Procedures in Automated Reasoning (CAV'05 Workshop).  July 12, 2005, Edinburgh, Scotland, UK.

MISTA 2005, 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications. 18 - 21 July 2005, New York, USA.

CFV'05, 3rd International Workshop on Constraints in Formal Verification (associated with CADE-20).  July 23, 2005, Tallinn, Estonia.

CADE-20, 20th International Conference on Automated Deduction.  July 22 - July 27, 2005, Tallinn, Estonia.
AAMAS 2005, 4th International Joint Conference AAMAS on Autonomous Agents and Multiagent Systems. July 25 - 29, 2005, UtrechtUniversity, The Netherlands.

DALT 2005, the 3rd International Workshop on Declarative Agent Languages and Technologies. July 25, Utrecht, the Netherlands.
SARA'2005, Symposium on Abstraction, Reformulation and Approximation. July 26th to 29th, 2005, RadissonSASAirthCastle & Hotel, Stirlingshire Scotland, UK.

IJCAI 2005 Workshop on Configuration (to be held at IJCAI 2005).  July 30-August 1, 2005, Edinburgh, Scotland.
IJCAI-05 Workshop on Advances in Preference Handling. July 30 to August 1, 2005, Edinburgh, Scotland.

The Fifth Workshop on Modelling and Solving Problems with Constraints (to be held at IJCAI 2005). July 30-August 1, 2005, Edinburgh, Scotland.

First Constraint Modelling Challenge (in conjunction with The Fifth Workshop on Modelling and Solving Problems with Constraints, IJCAI'05).  31 July, 2005, Edinburgh, Scotland.
IJCAI-05, Nineteenth International Joint Conference on Artificial Intelligence. 30 July-5 August 2005, Edinburgh, Scotland.

FG-MOL 2005, The 10th conference on Formal Grammar and The 9th Meeting on Mathematics of Language (Collocated with the European Summer School in Logic, Language and Information), 5-7 August 2005, Edinburgh, Scotland.
CSL'05, The 14th Annual Conference (and 19th International Workshop) in Computer Science Logic. 22-25 August 2005, University of Oxford, UK.

HM 2005, HYBRID METAHEURISTICS - Second International Workshop.  August 29-31, 2005, Universitat Politecnica de Catalunya, Barcelona, Spain.   

AICS05, The 16th Irish conference on Artificial Intelligence and Cognitive Science.  7th-9th September 2005, Marine Hotel in Ballycastle, Co. Antrim.

First International Summer School on Constraint Programming.  September 11-15, 2005, Hotel Villa del Mare, Acquafredda di Maratea -- Italy.  Late registration: July 31, 2005.

PPSWR 05, Third Workshop on Principles and Practice of Semantic Web Reasoning.  Sept. 11-16, 2005, Dagstuhl, Germany.

FTP'2005, 5th International Workshop on First-Order Theorem Proving. September 14-17, 2005, Koblenz, Germany.   

WCFLP 2005, International Workshop on Curry and Functional Logic Programming (An ACM SIGPLAN sponsored workshop at ICFP 2005).  September 29, 2005, Tallinn, Estonia. 
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.

Doctoral Programme, Eleventh International Conference on Principles and Practice of Constraint Programming (CP 2005). October 1-5 2005, Sitges, Spain. 

CPAI'05, Second International Workshop on Constraint Propagation and Implementation (held in conjunction with CP 2005).  October 1, 2005, Sitges, Spain.  Co-located with ICLP and an annular eclipse.  Paper submission deadline: July 13, 2005. 

Soft 2005, 7th International Workshop on Preferences and Soft Constraints (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 4, 2005.

BeyondFD 2005, 1st International Workshop on Constraint Programming Beyond Finite Integer Domains (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain. 

LSCS 2005, Second International Workshop on Local Search Techniques in Constraint Satisfaction (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 1, 2005.

The Fourth International Workshop on Modelling and
Reformulating Constraint Satisfaction Problems (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 7, 2005.

IntCP 2005, Workshop on Interval Analysis and Constraint Propagation for Applications (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 4, 2005.  Please, email all submissions in postscript or pdf format to: intcp-sub@mpi-sb.mpg.de

CHANGES'05, International Workshop on Constraint Solving under Change and Uncertainty (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 4, 2005.

First International Workshop on Quantification in Constraint Programming (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 4, 2005.

DSCP'05, 1st International Workshop on Distributed and Speculative Constraint Processing (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.

CPSec'05, 1st International Workshop on Applications of Constraint Satisfaction and Programming to Computer Security (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 1, 2005. 

First International Workshop on CONSTRAINTS AND DESIGN (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 6, 2005. 

COSOLV 2005, 5th CP Workshop on Cooperative Solvers in Constraint Programming (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 4, 2005.

SymCon'05, The Fifth International Workshop on Symmetry and Constraint Satisfaction Problems (held in conjunction with CP 2005).  October 1st, 2005, Sitges, Spain.  Paper submission deadline: July 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. 

Doctoral Consortium, Twenty first International Conference on Logic Programming.  2-5 October, 2005, Sitges, Spain. Co-located with CP 2005 and an annular eclipse. 

CHR 2005, Second Workshop on Constraint Handling Rules (co-located with ICLP'05).  October 5, 2005, Sitges (Barcelona) Spain.  Paper submission deadline: July 5, 2005. 

CSLP 2005, 2nd International Workshop on Constraint Solving and Language Processing (co-located with ICLP 2005).  5 October 2005, Sitges, Barcelona, Spain.  Paper submission deadline: 7 August 2005.

CICLOPS 2005, Colloquium on Implementation of Constraint and LOgic Programming Systems (Satellite workshop of ICLP 2005).  October 5, 2005, Sitges (Barcelona), Spain.  Paper submission deadline: July 1, 2005.

WCB05, Workshop on Constraint Based Methods for Bioinformatics (associated to ICLP 2005).  October 5, 2005, Sitges, Spain.

MoVeLog'05, Mobile Code Safety and Program Verification Using Computational Logic Tools (an ICLP 2005 Workshop).  Sitges, Spain, Oct. 5, 2005.  Paper submission deadline: July 1, 2005. 

WLPE05, The 15th Workshop on Logic-based methods in Programming Environments (Satellite workshop of ICLP 2005).  October 5, 2005, Sitges (Barcelona), Spain.  Paper submission deadline: July 5, 2005.

ICLP'05, Twenty first International Conference on Logic Programming.  2-5 October, 2005, Sitges, Spain. Co-located with CP 2005 and an annular eclipse. 

SAGA 2005, 3rd Symposium on Stochastic Algorithms, Foundations and Applications.  October 20-22, 2005, Moscow, Russia.

INAP2005, 16th International Conference on Applications of Declarative Programming and Knowledge Management.  October 22-24, 2005, WasedaUniversity, Fukuoka, Japan.  Paper submission deadline: August 1, 2005.

ISCIS'05 The 20th International Symposium on Computer and Information Sciences.  October 26-28, 2005 - Istanbul, Turkey.

Heuristic Methods for Timetabling and Rostering (Special Invited Session of INFORMS'05).  November 13-16, 2005, New Orleans, USA.  Contact Dario Landa Silva at jds@cs.nott.ac.uk.

INFORMS'05, 2005 INFORMS Annual Meeting.  November 13-16, 2005, New Orleans, USA. 

ICTAI 2005, 17th IEEE International Conference on Tools with Artificial Intelligence.  November 14-16, 2005, Hong Kong.   

MICAI 2005, 4th Mexican International Conference on ARTIFICIAL INTELLIGENCE.  November 14-18, 2005, Monterrey, Mexico. 

LPAR-12, The 12th International Conference on Logic for Programming Artificial Intelligence and Reasoning.  2nd-6th December 2005, Montego Bay, Jamaica.  Paper submission deadline: July 18, 2005.

IICAI-05, The 2nd Indian International Conference on Artificial Intelligence.  December 20-22, 2005, Pune, INDIA.

PADL'06, Eighth International Symposium on Practical Aspects of Declarative Languages 2006 (co-located with ACM POPL'06).  January 9-10, 2006, Charleston, South Carolina, USA.  Paper submission deadline: August 20, 2005. 

CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Fall 2006, Nantes, France. Program chair: Frederic Benhamou.

Constraint Solving and Programming Track of SAC 2006, The 21st Annual ACM Symposium on Applied Computing. April 23-27, 2006, Dijon, France.

AISC-2006, AI and Symbolic Computation, September 20-22, 2006, Beijing, China.

Career news


A new MSc in Intelligent Systems for Business and Manufacturing, is planned to commence in September 2005 at University College Cork, Ireland. The deadline for applications for this course has been extended to 15th of July 2005. For more information see:



Bell Labs, the innovation engine of Lucent Technologies, is a worldwide research and development community that focuses its efforts on key technologies including Software, Wireless and Broadband networking, Signal Processing, Microelectronics, Photonics and Supply Chain technology. It is internationally renowned as the birthplace of modern information theory, the transistor, the laser and the UNIX operating system.

Bell Labs is recruiting for multiple positions within its new research facility in Dublin, Ireland. Well-funded, leading edge research will begin focusing on next generation fixed and wireless communications networks and other new emerging voice/data technologies.

We are presently recruiting for a Post-Doctoral Contract Position (duration 2 years) in the areas of:

-          Stochastic Constraint Programming

-          Robust Constraint Programming

-          Optimization

-          Supply Chain Uncertainty

This unique position will afford the opportunity for strong collaborative research with researchers at the Cork Constraint  Computation Centre (4C) at the University College Cork.

To be considered for this position, you must have a Ph.D. in computer science, operations research, mathematics, statistics, or related fields with extensive programming experience.  A comprehensive and competitive benefits package exists which would include relocation costs.

To receive role profiles and apply, Please contact Helen Creedon on +3531-886 4496. You will need to send an up-to-date CV (Including a full publications list) to hcreedon@lucent.com and eohanlon@4c.ucc.ie.

Ph.D. Positions Available on Decision Procedures for Formal Verification

International DoctorateSchool on Information and Communication Technologies, University of Trento, Italy

Firm deadline: July 11th, 2005

The MathSAT team at ITC-irst and at University of Trento is seeking candidates for two Ph.D. positions at the InternationalDoctorateSchool in Information and Communication Technologies (ICT) of the University of Trento, Italy.

The activity will be carried out within the MathSAT project, and will aim at the design and development of decision procedures and their application to formal verification.

Presentation and Inquiries

Candidates interested in the above positions should introduce themselves and inquire for further information by sending email to:


Please use 'MATHSAT PHD' as subject, and include a statement of interest and a CV. PostScript, PDF, or plain text formats are encouraged.

Application to the ICTSchool

Full details are available from http://www.ict.unitn.it/.

Candidate Profile

The ideal candidate should have a MS or equivalent (in either computer science, mathematics, electronic engineering or similar topics), and combine solid theoretical background and software development skills.

The candidate shuold be be able to work in a collaborative environment, with a strong commitment to achieving assigned objectives and reaching research excellence.

Background knowledge and/or previous experience in the areas of formal verification, boolean reasoning, constaint solving, deduction systems, hardware description languages, though not mandatory, will be considered favourably.


MathSAT (http://mathsat.itc.it/) 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.

Related Projects

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 activity of the selected candidates will be related to the ORCHID project (Enhanced Formal Checkers for RTL Circuit Designs).  The goal of the ORCHID project 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.

Contact Persons

- Alessandro Cimatti---mailto:cimatti@itc.it

- Roberto Sebastiani---mailto:roberto.sebastiani@dit.unitn.it


National ICT Australia (NICTA) is seeking applications from high performing researchers to work in its Knowledge Representation and Reasoning (KRR) Program. The positions are based at the Canberra laboratories of NICTA located at the AustralianNationalUniversity.

Appointments may be at the following levels:

-          principal researcher, continuing, salary package: 100-150K AUD

-          senior researcher, 3 years initially, salary package: 85-130K AUD

-          researcher, 3 years initially, salary package: 70-100K AUD

Candidates should have a PhD in computer science or a related field, and a record of achievements in one or more of the following areas:

-          Planning & scheduling

-          Model-based diagnosis

-          Model-checking in AI

-          Reinforcement learning

-          Constraints and search

Current members of the group include:

-          Anbulagan

-          Doug Aberdeen

-          Olivier Buffet

-          Norman Foo

-          Alfredo Gabaldon

-          Phil Kilby

-          Michael Maher

-          Thomas Meyer

-          Morri Pagnucco

-          Yannick Pencole

-          Jochen Renz

-          Sylvie Thiebaux

-          Toby Walsh

Application Process: see http://nicta.com.au/opportunities.cfm

Closing date: 15 August 2005

If you wish to apply, please contact sylvie.thiebaux@nicta.com.au

PostDoctoral Researcher in Constraint Programming

National ICT Australia (NICTA), Kensington Lab (Sydney): Knowledge Representation and Reasoning Program

Areas of particular interest include scheduling, constraint programming, and road traffic management.

Applicants must have demonstrated excellence in research. Experience of industrial research and development or of commercialisation of research would be advantageous.

The appointment will initially be for a fixed term of three years.

Applications: Please visit NICTA Careers to view the criteria essential to this role and apply online.

Contact Toby Walsh.

Closing date: Applications are welcome at any time.

POSTDOC Opportunity in Hong Kong

Department of Computer Science and Engineering, The ChineseUniversity of Hong Kong, Hong Kong.

We are looking for a motivated Postdoc fellow with Constraint Programming background to work on either one of the following areas:

-          Collaborating Redundant Models

-          Local Search

-          Over-constrained Problems

-          Symmetry Breaking

The candidate should hold a PhD or equivalent qualification, and should normally have no more than 5 years of post-qualification experience. Good track record in constraint related research is desirable.

If the candidate is not a Hong Kong resident, a valid visa to work in Hong Kong must be obtained before the appointment takes effect.

Monthly salary commences at around HK$18,780 (US$1 = HK$7.8) and depends on qualification and experience.  Hong Kong also enjoys a low tax rate of 15% maximum per annum.  The appointment will be initially for one year, but can be renewed for another year subject to satisfactory performance. Other benefits include annual leave, out-patient, and dental benefits.

We have an active research group of moderate size working on constraint programming.  Current topics of interest include, but not limited to, search algorithms (systematic, local, hybrid), problem modeling, over-constrained problems, and practical applications.

The University is situated in Shatin, an outskirt area of Hong Kong with efficient transportation into the city.  The campus is built on a hill-side spanning 134 hectares of land with beautiful surroundings and landscape.

Interested candidates should contact Jimmy Lee by email with their update CV enclosed by the end of September, 2005.


CP-AI-OR 2005 International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

(Reported by Michela Milano)

The conference CP-AI-OR has been held in Prague, Czech Republic in May 29 - June 1, 2005. The aim of the conference was to bring together interested researchers from AI and OR, and to give them the opportunity to show how the integration of techniques from AI and OR can lead to interesting results on large scale and complex combinatorial optimization problems.

This year the day before the conference a Master Class on Metaheuristics and Constraint Programming has been organized by Gilles Pesant. Six introductory and overview talks by leading researchers in the area were given to more than forty participants attending the Master Class. The presentations are available from the conference web pages.

This year the number of submissions to the main conference has been extremely high, reaching almost 100 papers. Out of these papers only 26 high quality papers have been accepted and published in Lecture Notes in Computer Science series number 3524 by Springer Verlag. The main conference lasted three days with sessions on global constraints, branch and price and column generation, benders decomposition, explanations, search and symmetries, integer programming, SAT, and many applications. A strong focus on real-life applications is one of the distinguishing aspects of the conference. For this reason, the invited talks have been mostly applicative. The first talk, given by Paul William, concerned modeling aspects of the Traveling Salesman Problem. The second talk, given by Paul Pop, was about optimization challenges in embedded systems design. Filippo Focacci, the third speaker, has presented a new ILOG product called Plan PowerOpt that merges rules and scheduling. All invited talks are available from the conference web pages.

The conference was kindly sponsored by the ARTIST, Network of Excellence sponsoring the talk by Paul Pop and making an interesting cross-fertilization possible; Carmen Systems, Sweden; CoLogNet, Network of Excellence; IISI (Intelligent Information Systems Institute, Cornell), USA; ILOG S.A., France; and SICS, Sweden. Ten students received grants to attend the Master Class and the main conference.

The conference has been extremely well organized (CharlesUniversity and Action M Agency were the local organizers) and Prague always deserves a visit.


Constraint Programming at Microsoft Research, Cambridge, is part of the "Systems and Networking Group". The constraint programming thread started with the recruitment of Youssef Hamadi to work on distributed CSPs and their applications to problems in distributed computing, which brought the CP technology into a research environment where it was previously little known.  The group currently consists of one permanent researcher (Youssef Hamadi) and one associate researcher (Lucas Bordeaux), together with occasional visitors (among the last months: Georg Ringwelski, Frank Hutter and Eric Monfroy).

Our research activity is driven by two goals: to perform academic research on a number of fundamental CP topics, and to disseminate the constraint programming technology inside the research and production groups of the company.

Our fundamental research is essentially focused on distributed and parallel search, cooperative approaches (between SAT and CP in particular), and on tools to make the modeling and constraint programming tasks more automated.

We have developed cooperations both inside Microsoft Research (machine learning and computer vision group, programming and verification group) and with external research groups (LIRMM, U. of York, U. of St-Andrews, ITU, etc).  As part of these external links, two PhD thesis will receive MSRC funding this year (LIRMM, IMAG).

Simultaneously, we are building tight collaborations with different product groups in the company. These groups benefit from our expertise in constraint solving and apply it to handle concrete optimization problems.

Central to our work is Disolver, the platform used for internal developments, which was developed by Youssef Hamadi. Disolver is a constraint programming library written in C++ which has a number of non-standard features, like parallel and distributed tree/local search algorithms.

Selected publications:

G. Ringwelski and Y. Hamadi: Boosting Distributed Constraint Satisfaction, in proc. of 11th Int. Conf. on Principles and Practice of Constraint Programming (CP). To appear, 2005.

Y. Hamadi and M. Shapiro: Pushing Log-Based Reconciliation. In Int. J. on Artificial Intelligence Tools (IJAIT), 14(3-4), 2005.

M. Bartlett, A. M. Frisch, Y. Hamadi, I. Miguel, S. A.Tarim and C. Unsworth: The temporal knapsack problem and its Solution, in proc. of Int. Conf. on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), p. 34-48. 2005 .

L. Bordeaux, M. Cadoli and T. Mancini: CSP Properties for Quantified Constraints: Definitions and Complexity, in proc. of 20th American Conf. on Artificial Intelligence (AAAI), p. 360-365. 2005