Volume 5, Number 3, October 2009

Constraint Programming News

volume 5, number 3, October 2009

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

Contents

News

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.

REPORT FROM THE ASSOCIATION FOR CONSTRAINT PROGRAMMING

This is a short summary of activities within the ACP during the months July-September 2009.

The 2009 ACP Executive Committee comprises the following people:

Barry O'Sullivan - President

Jimmy H.M. Lee - Secretary

Thomas Schiex - Treasurer

Pedro Meseguer - Conference Coordinator

Christian Bessiere

John Hooker

Karen Petrie

Christian Schulte

Peter Stuckey

Michael Trick

Roland Yap

The ACP Executive Committee welcomes feedback and suggestions from the ACP community. We encourage you to engage with the ACP-EC to help design new initiatives that promote constraint programming.

ACP.1. Brief Comment on CP 2009

On behalf of the ACP, the Executive Committee would like to congratulate the various people responsible for making CP 2009 in Lisbon such a success. Special thanks goes to Pedro Barahona (Conference Chair), Ian Gent (Program Chair), Ian Miguel and Patrick Prosser (Tutorial and Workshop Chairs), Karen Petrie and Olivia Smith (Doctoral Program Chairs), Jorge Cruz (Sponsorship Chair), and Francisco Azevedo (Publicity Chair). We would also like to thank the Organising Committee: Ines Lynce, Vasco Manquinho, Ludwig Krippahl and Elsa Carvalho.

ACP.2. ACP General Assembly 2009

During the CP 2009 conference, the annual ACP General Assembly took place. It was chaired by the current ACP President, Barry O'Sullivan, and was well attended by the community. The main recommendation from the ACP-EC was that the ACP Research Excellence Award move to a 2 year cycle; this was supported. The award will be given on odd-numbered years in the future. A new award, the ACP Outstanding Service Award, will be introduced and will be awarded on even-numbered years. A constructive discussion took place on how to move the community forward from its current position of strength. The main additional discussion items were (a) how to structure the two main solver competitions in the field, and (b) other activities the ACP should run each year. The minutes for the assembly will be made available on the ACP web-site.

ACP.3. Call for Proposals for New ACP Activities

During the ACP General Assembly the Treasurer, Thomas Schiex, reported that the association is in good financial standing. It was also reported that CP 2008 would be declaring a strong surplus. Therefore, the ACP would like to receive proposals for other activities that the association should support. Please send your suggestions to secretary@cp-online.org

ACP.4. Call for Proposals to Host the ACP Summer School 2010

Members of the CP community who are interested in organizing the 2010 ACP Summer School should send a proposal to secretary@cp-online.org by November 30th 2009, containing at least the following information:

1. topic of the school

2. location

3. dates

4. organizers

5. provisional budget

Since its establishment, the summer school has been a major success with feedback from student attendees being very positive.

OTHER NEWS

CONSTRAINTS: New Editor-in-Chief.

The position of Editor-in-Chief of Constraints is a fixed five year term, non-renewable. My (Peter van Beek's) term as EiC is coming to a close at the end of this year. I am pleased to announce that Gilles Pesant will be the next EiC of Constraints. Let me take this opportunity to say that it has been rewarding to be EiC these past five years and it has been a pleasure working with many of you as reviewers, editorial board members, advisory board members, guest editors, and authors. Thank you to the reviewers, board members, and guest editors for all of your work for the journal. And best wishes to Gilles as he takes over.

CONSTRAINTS Journal Accepted Papers

The contents of the most recent issue are listed below. Links to the authors' final versions (no subscription required) and to the final published versions (subscription required) can be found here.

Volume 14, Issue 4 (2009)

A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas

Pages: 415-442

Mark Liffiton, Maher Mneimneh, Inês Lynce, Zaher Andraus, João Marques-Silva and Karem Sakallah

On implementing symmetry detection

Pages: 443-477

C. Mears, M. Garcia de la Banda and M. Wallace

SymChaff: exploiting symmetry in a structure-aware satisfiability solver

Pages: 478-505

Ashish Sabharwal

Dynamic structural symmetry breaking for constraint satisfaction problems

Pages: 506-538

Pierre Flener, Justin Pearson, Meinolf Sellmann, Pascal Van Hentenryck and Magnus Ågren

Non-binary quantified CSP: algorithms and modelling

Pages: 539-581

Peter Nightingale

Forthcoming Papers: Links to final versions of papers accepted for publication can be found here.

Constraint Programming Letters Journal Accepted Papers

Constraint Programming Letters (CPL) provides an international forum for the electronic publication of high-quality scholarly articles on constraint programming. All published papers are freely available online.

The goal of CPL is to promote and nurture constraint programming research, report on its successful applications, and encourage cross-fertilization with neighboring areas. In particular,

CPL provides an international publication medium for constraint programming research with a commitment to rigorous yet rapid reviewing. Final versions are published electronically (ISSN 1932-0973) immediately upon receipt.

CPL offers a forum for research on the practice of constraint programming, including topics such as applications, implementation, modeling, deployment successes and failures, and programming systems. Theoretical papers are also welcome.

CPL aims at strengthening the links with neighboring communities, including the operations research, numerical analysis, planning, SAT, and verification communities. Papers reporting hybridizations of constraint programming with other techniques are especially welcome.

CPL focuses on relatively short papers (less than 6,000 words) describing timely research results.

Other Publications

Book:

Title: CONSTRAINT HANDLING RULES

Author: Thom Frühwirth

Cambridge University Press 2009,

http://constraint-handling-rules.org

ISBN 9780521877763

Constraint Handling Rules (CHR) is both a versatile theoretical formalism based on logic and an efficient practical high-level programming language based on rules and constraints.

This book describes the theory of CHR and how to use it in practice. It is supported by a website containing teaching materials, online demos, and free downloads of the language. After a basic tutorial, the author describes in detail the CHR language and discusses guaranteed and desirable properties of CHR programs. The author then compares CHR with other formalisms and languages and illustrates how it can capture their essential features. Finally, larger programs are introduced and analyzed in detail. Exercises with selected solutions, and bibliographic remarks are included at the ends of chapters.

Title: Constraint Networks: Techniques and Algorithms

Author: Prof. Christophe Lecoutre (CRIL - CNRS, University of Artois)

ISTE/Wiley, June 2009 (592pp),

http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250

ISBN: 9781848211063

Abstract: Constraint networks are abstract models used in time-tabling, scheduling, vehicle routing, planning, bio-informatic applications, and also in solving crosswords, Eternity II and other puzzles. A constraint network is an expression of a collection of constraints that must be satisfied. This expression of constraints is naturally declarative and can therefore be understood and employed by many people. Constraint networks are important because of their broad applicability and because of the ready availability of a vast range of practical algorithms and heuristics.

During the last decade, there have been many substantial new developments, most of these characterized by conceptual simplicity of general techniques and underlying algorithms. This work is comprehensively and rigorously presented in this book, which provides the reader with a gentle introduction to this active field of research. Pragmatically, this book concentrates on general-purpose approaches proven to be effective in practice. These approaches are the source of a nascent generation of robust constraint solvers accessible to the average user.

After a couple of introductory chapters, this book is organized in two main parts. The first presents general inference methods based on local consistencies, which are relational and structural properties of constraint networks. Recently published techniques and algorithms are explained and compared. The second part of the book describes sophisticated general search methods, which learn before and during the search so as to reduce the number of combinations that are explored. Concepts, techniques and algorithms are illustrated by many examples.

The intended audience of this book includes researchers, PhD students, graduate students and other people interested in constraint programming or related fields such as operations research, artificial intelligence, computer science, or applied mathematics. No prior knowledge of constraint satisfaction is required to read and understand the main concepts of this book.

Software

Release of Comet 2.0

Dynadec is happy to announce the release of Comet 2.0.

Version 2.0 includes support for an additional MIP Solver (SCIP), new CP global constraints (soft global and rostering constraints), and a new Java API, as well as several bug fixes and enhancements from the 2.0-beta release. This release includes all the features of the 2.0- beta release, including a new visualization library (qtvisual) based on the Qt toolkit, a new XML library (cotxml), support for external plugins, and improved documentation.

Please look at the release notes for more details on this new version. We of course welcome feedback, bug reports, requests for new functionalities on these developments.

JaCoP 2.4 release

Radoslaw Szymanek and Kris Kuchcinski are happy to announce the release of a new version of our Java-based solver JaCoP. This new version 2.4 has a number of new features in addition to some bug fixes. The most important additions in this version are:

1. The flatzinc interface that makes it possible to run minizinc programs using JaCoP. The distribution contains number of different minizinc examples.

2. Geometrical constraint, geost, based on pruning algorithms originally proposed by Nicolas Beldiceanu et al. This constraint makes it possible to define placement problems of non-convex objects in k-dimensional space.

3. Knapsack constraint, which is based on the work published by Irit Katriel et al. We extend the original work in number of ways, for example by making it possible to use non-boolean quantity variables.

4. Set constraints defining typical operation on sets using set interval variables.

5. JaCoP user's guide extended with parts explaining new features.

For details and download page, please visit http://jacop.osolpro.com http://www.jacop.eu

This work would not be possible without help of several people. We would like to thank Hakan Kjellerstrand for his help in testing flatzinc parser as well as providing number of examples in minizinc format. We would also like to thank Meinolf Sellmann for his comments on the initial implementation of the knapsack constraint which have helped to improve it further. Marc-Olivier Fleury has implemented most of the functionality of the geost constraint. Wadeck Follonier has implemented the first version of the Knapsack constraint. Robert Åkemalm has implemented the first version of set package. We would like to thank all of them for their contributions.

Events

HM 2009, Sixth International Workshop on HYBRID METAHEURISTICS, October 16-17, 2009, Udine, Italy.

ADT 2009, First International Conference on ALGORITHMIC DECISION THEORY, October 21-23, 2009, Venice, Italy.

RR 2009, The Third International Conference on Web Reasoning and Rule Systems, October 25-26, 2009, Chantilly, Virginia, USA.

INAP 2009, 18th International Conference on Applications of Declarative Programming and Knowledge Management, November 5-7, 2009, Evora, Portugal.

RuleML 2009, 3rd International Symposium on Rules, Applications and Interoperability, November 5-7 2009, Las Vegas, Nevada, USA.

AI'09, The 22nd Australasian Joint Conference on Artificial Intelligence, 1-4 December, 2009, Melbourne, Australia.

RCRA 2009 (co-located with AI*IA 2009), 16th RCRA workshop: Experimental evaluation of algorithms for solving problems with combinatorial explosion, 11-12 December 2009, Reggio Emilia, Italy.

PADL'10 (Co-located with ACM POPL'10), Twelfth International Symposium on Practical Aspects of Declarative Languages 2010, January 18-19, 2010, Pasadena, California, USA. Abstract submission: August 31, 2009.

VMCAI 2010 (Co-located with POPL 2010), The Eleventh International Conference on Verification, Model Checking, and Abstract Interpretation, January 17-19, 2010, Madrid, Spain.

PEPM'10 (Affiliated with POPL'10), ACM SIGPLAN 2010 Workshop on Partial Evaluation and Program Manipulation, January 18-19, 2010, Madrid, Spain. Paper submission: Tue, October 6, 2009, 23:59, Apia time.

ICAPS 2010, Twentieth International Conference on Automated Planning and Scheduling, May 12-16, 2010, Toronto, Canada. Paper submission deadline: Dec 18, 2009.

Special Track on AI PLANNING AND SCHEDULING at FLAIRS-23, 23rd International Florida Artificial Intelligence Research Society Conference, May 19-21, 2010, Daytona Beach, Florida, USA. Submission deadline: 23rd November, 2009.

CP-AI-OR 2010, The Seventh International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems, June 14-18, 2010, Bologna, Italy. Abstract due: January 11, 2010, Full paper due: January 18, 2010, Short Paper due: February 15, 2010.

CSP track of ACM SAC 2010, 25th Annual ACM Symposium on Applied Computing, March 22 - 26, 2010, Sierre, Switzerland.

Career news

Post-Doc or PhD Position in Concurrent Advanced Planning & Scheduling Constraint Programming Group UCLouvain, Louvain-la-Neuve, Belgium

Context

Today's supply chain departments of industrial companies are equipped with Advanced Planning and Scheduling (APS) solutions that help the human planners and schedulers in their daily operation. Optimization algorithms are the core functions of these decision aid tools.

This research project aims at investigating the possibilities of concurrent computing, in order to improve the quality and speed of the optimization algorithms in this field of advanced planning and scheduling (APS).

The research will be based on the new Comet platform (http://dynadec.com/), and will combine local search as well as constraint programming approaches.

The research will be conducted within the Constraint Programming Group at UCLouvain (http://becool.info.ucl.ac.be/), and will be realized in collaboration with a software industry specialized in APS in the steel industry.

Practical details

- Position open for Post-Doc or PhD candidates

- Required degree : PhD or Master in Computing Science or related fields

- One or two years contract

- Starting date : September 2009

- Please send CV to Yves.Deville@uclouvain.be

Irish Research Council for Science, Engineering and Technology (IRCSET): Postdoctoral Fellowship Call 2010

B. EMPOWER: Government of Ireland Postdoctoral Fellowships in Science, Engineering and Technology: IRCSET will continue to offer their sought-after fellowships based at an Irish host laboratory. The candidates must be within 3 academic years from the award of PhD and propose pursuing their work for 24 months at an Irish research laboratory.

The Call will open to applications on 2nd October 2009 and close for applicants about six weeks later on the 12th November 2009.

For more information: http://www.ircset.ie/Default.aspx?tabid=78

Deadline: 12 November 2009

The Autonomous System group at the Monterey Bay Aquarium Research Institute (MBARI) invites applications for 1 two-year postdoc position.

MBARI (http://www.mbari.org) is a private non-profit Oceanographic research institute located in Moss Landing, California, in the heart of the largest marine sanctuary in the United States, just outside Silicon Valley. The institute is an inter-disciplinary research institution guided by a strong peer relationship between scientists, engineers and marine operations staff. MBARI pioneered the use of Remotely Operated Vehicles (ROVs http://www.mbari.org/dmo/vessels_vehicles/tiburon/tiburon.html) and Autonomous Underwater Vehicles (AUVs http://www.mbari.org/auv/default.htm ) for deep ocean research and continues to be at the cutting edge of marine robotics, marine sensor development, ocean chemistry, marine geology, micro-biology and ecology.

Research Focus:

The Autonomous Systems group is uniquely placed as being the only Artificial Intelligence group within an operational oceanographic setting anywhere. The focus of the groups effort is in automated reasoning for embodied robust intelligence for AUVs with a focus on Automated Planning, Execution, Constraint-Based Reasoning and Machine Learning. The core development effort is to enable adaptive control for AUVs to survey, sample and characterize dynamic and episodic ocean phenomenon such as Harmful Algal Blooms, Fronts and Thin Layers which have substantial societal impact (http://www.mbari.org/autonomy/TREX/ ). Further efforts are underway to study the feasibility of goal-based commanding for underwater feature-based SLAM, mixed-initiative platform control and multi-vehicle coordination.

Research Environment:

The Autonomous Systems group was established in 2005 by researchers from NASA with extensive background in commanding spacecraft including the twin Mars Rovers Spirit and Opportunity. A strong inter-disciplinary effort with biological oceanographers at MBARI and others outside has driven the design and deployment of a hybrid executive which enables an AUV to adaptively sample the environment using Planning and Machine Learning techniques to inform dynamic in-situ behavior. Publishing in peer-reviewed conferences and journals in AI, Robotics and the Ocean Sciences and interacting with scientists in the fields of biology, chemistry, ecology, genetics, ocean physics, marine robotics is an important aspect of the research effort. The group collaborates with AI and Robotics researchers in academia in the US and Europe and hosts visiting graduate students and researchers from within the US and Europe.

Primary topic areas of interest for this position are:

1. Automated Planning and Execution

2. Constraint-based Reasoning

3. Mixed-Initiative Planning with marine robots

4. Distributed Planning

Applicants are encouraged to communicate with the PI for project feasibility and relevance to ongoing MBARI research. Women and minorities are strongly encouraged to apply. Details of the application process are at http://www.mbari.org/oed/jobs/Postdocs-2010.html . The deadline for applications is December 11th 2009.