Constraint Programming News
volume 2, number 0, Jan, 2006
Editors: Jimmy Lee (events, career news) Eric Monfroy (profiles, publications) Toby Walsh (news, reports)
Contents
- news: ACP News, ACP Summer School 2006, CP 2006, CP 2007, CP-AI-OR, ERCIM Workshop on Constraints, Yahoo! Discussion Group on Constraints
- CONSTRAINTS journal accepted papers
- other publications: book, phd theses, special issues, book review, software
- events: forthcoming conferences and workshops
- career news: Doctoral, Postdoc, Researcher, and Intern positions
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.
Association for Constraint Programming (ACP)
ACP EC news: January 1st, 2006 to March 31, 2006
· After a call for bids for the CP 2006 summer school, the EC received two bids. The accepted bid was from Kostas Stergiou and Toby Walsh, who will organize the 2006 CP summer school in Samos, Greece, on June 18-23, 2006. As decided by the EC after the 2005 school, general and advanced summer schools will alternate. This school will be an advanced school on global constraints. The school web site is at the URL http://www.cse.unsw.edu.au/%7Etw/school.html
· The travel grant scheme that was announced in Sitges is still on hold. In the meantime, the EC considered, and accepted, the following requests for sponsorship:
o 1000 euros to the International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic and Graph Theory, that has been held on March 20-24, at St Anne’s College, University of Oxford. The workshop web site, containg all presentation slides, is at the URL http://www.cs.rhul.ac.uk/home/green/mathscsp/
o 1000 euros to the Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming (CSCLP 2006) to be held on June 26-28, 2006, at the Universidade Nova de Lisboa, Caparica, Portugal. Web site: http://centria.di.fct.unl.pt/conferences/csclp06
o 3000 euros to the 2006 CP summer school (see above for details about the school).
o CP 2005 had a nice surplus. Many thanks to Pedro, Javier, and Peter for a wonderful organization and program! The EC hopes that this money will be useful to support many interesting CP activities in the future.
· Frederic Benhamou, the program chair of CP 2006, wanted to know the ACP EC opinion about the possibility of eliminating doctoral program abstracts from the CP proceedings. The AC EC has discussed this issue, and it is in favour of the following:
o removing the 1-page DP abstracts from the Springer proceedings
o putting the DP abstracts and/or longer versions in the DP web site and in Corr
o distributing the DP abstracts to the CP participants by printing a separare booklet, like a workshop proceedings
o use Corr also for the workshop proceedings
However, full responsability for the program and the proceedings of the CP conference remains in the hands of the program chair and the program committee.
· To encourage discussion on ACP-related matters, the ACP EC has started a Yahoo! discussion group on constraints, where anybody can join or leave at any time, by following the simple instructions at the URL http://groups.yahoo.com/group/constraints/ On March 23, 2006, this discussion group has 145 members.
· To follow the discussion which took place at the ACP general assembly at CP 2005, the EC is creating a task force on CP applications, that will be led by Barry O’Sullivan. The role if this task force is to identify mechanisms to attract practitioners and industrial people to CP conferences, and in general to strenghten the link between academia and industry in the CP field. People interested in joining this task force should contact Barry.
· After the 2005 ACP research award, given to Eugene Freuder at CP 2005, there has been an ongoing discussion about an annual versus a two-yearly ACP research award. We will hopefully finalize this discussion soon and post the result on the ACP web site and the CP newsletter. In any case, the receipient of the next award will be chosen by the EC among a set of candidates proposed by the CP community through an open call.
· The ACP EC will be happy to receive proposals for initiating new activities, or for improving the current ones. Any member of the CP community who wants to make any of such proposals should send a detailed message describing his/her proposal to the address proposals@a4cp.org, with subject “ACP EC proposals: [a specific subject]”.
Second International Summer School of the Association for Constraint Programming
Second International Summer School of the Association for Constraint Programming
http://www.cse.unsw.edu.au/~tw/school.html
Advanced School and International Workshop on Global Constraints
Doryssa Bay Hotel, Samos, Greece
Organizers: Kostas Stergiou and Toby Walsh
June 18-23, 2006
The Second International Summer School on Constraint Programming is an advanced school and associated workshop on global constraints. The school and workshop are aimed at PhD students, researchers, and practitioners of all levels who wish to learn about this key area in depth. Lecturers include: Philippe Baptisite, Nicolas Beldiceanu, Christian Bessiere, Mats Carlsson, Willem-Jan van Hoeve, Irit Katriel, Michela Milano, and Jean-Charles Regin. The school and workshop will take place in the Doryssa Bay hotel on the Aegean island of Samos in Greece. The hotel is next to the fishing village of Pythagorion, the birth place of the Greek philosopher Pythagoras. To participate in the advanced school and workshop, please email Toby Walsh (tw@cse.unsw.edu.au) as soon as possible.
CP 2006 Call For Papers:
CP 2006
Twelfth International Conference on
Principles and Practice of Constraint Programming
September 25 - 29, 2006
Nantes, France
http://www.sciences.univ-nantes.fr/cp06/
The CP conference is the annual international conference on constraint programming and related areas. It is concerned with all aspects of computing with constraints, including: theory, algorithms, applications, environments, languages, models and systems. CP 2006 includes a technical programme, where presentations of theoretical and application papers, as well as invited talks, tutorials, posters and system demos aim at describing the best results and techniques in the state-of-the-art of constraint programming. Moreover, CP 2006 continues the tradition of the CP doctoral programme, in which PhD students can present their work, listen to tutorials on career and ethical issues, and discuss their work with senior researchers via a mentoring scheme. Finally, there will also be a number of workshops, where researchers will be able to meet in an informal setting and discuss their most recent ideas with their peers.
Papers are solicited from all disciplines concerned with constraints and any application domain using constraints. Example topics include problem modelling, problem solving, efficiency and usability. Papers which report on successful applications of constraint technology are also solicited.
Submitted papers must be original and must not be simultaneously submitted for publication in a journal or another conference. Authors are required to prepare their papers by following the Springer instructions found at: http://www.springer.de/comp/lncs/authors.html.
A page limit of 15 will be strictly enforced. The proceedings will be published by Springer Verlag, in the Lecture Notes in Computer Science series.
IMPORTANT DATES
* April 21, 2006: Deadline for submissions
* June 14, 2006: Notifications
* July 5, 2006: Camera-ready copy
ORGANIZATION
Conference Chairs
Frédéric Benhamou, U of Nantes, France
Narendra Jussien, EMN, France
Program Chair
Frédéric Benhamou, U of Nantes, France
Doctoral Program Chairs
Zeynep Kiziltan, U of Bologna, Italy
Brahim Hnich, 4C, Ireland
Workshop/Tutorial Chair
Barry O’Sullivan, 4C, Ireland
Poster/Demo Chair
Laurent Michel, U of Connecticut, USA
Publicity Chairs
Christian Schulte, KTH, Sweden
Mikael Lagerkvist, KTH, Sweden
Program Committee
Pedro Barahona, New U of Lisbon, Portugal Nicolas Beldiceanu, EMN, France Christian Bessiere, LIRMM-CNRS, France David Cohen, Royal Holloway, UK Andrew Davenport, IBM, USA Boi Faltings, EPFL, Switzerland Carla Gomes, Cornell, USA Laurent Granvilliers, U Nantes, France John Hooker, CMU, USA Peter Jonsson, Linköping U, Sweden Irit Katriel, U of Aarhus, Denmark Zeynep Kiziltan, U of Bologna, Italy Luc Jaulin, ENSIETA Brest, France Jimmy Lee, CUHK, Hong Kong Michael Maher, NICTA, Australia Pedro Meseguer, IIIA-CSIC, Spain Laurent Michel, U of Connecticut, USA Michela Milano, U of Bologna, Italy Barry O’Sullivan, 4C, Ireland Gilles Pesant, Polytech Montréal, Canada Jean-François Puget, ILOG, France Jean-Charles Régin, ILOG, France Francesca Rossi, U of Padova, Italy Louis-Martin Rousseau, Polytech Montréal, Canada Michel Rueher, U of Nice, France Thomas Schiex, INRA Toulouse, France Christian Schulte, KTH, Sweden Helmut Simonis, CrossCore Optimization, UK Barbara Smith, 4C, Ireland Peter Stuckey, U of Melbourne, Australia Peter van Beek, U Waterloo, Canada Pascal Van Hentenryck, Brown U, USA Mark Wallace, Monash U, Australia Toby Walsh, NICTA and UNSW, Australia Roland Yap, NUS, Singapore Makoto Yokoo, Kyushu U, Japan Weixiong Zhang, Washington U, USA
CP 2007:
* Location: Providence, RI, USA
* Dates: fall 2007.
* Conference chairs: Meinolf Sellmann and Laurent Michel
* Program chair: Christian Bessiere
* Co-located with ICAPS 2007 (International Conference on Automated Planning and Scheduling)
CP-AI-OR Call For Participation
C A L L F O R P A R T I C I P A T I O N
The Third International Conference on
Integration of AI and OR Techniques in Constraint Programming
for Combinatorial Optimization Problems
CP-AI-OR'06
May 31-June 2, 2006, Cork, Ireland
http://tidel.mie.utoronto.ca/cpaior
cpaior@mie.utoronto.ca
After a successful series of five international workshops (Ferrara, Paderborn, Ashford, Le Croisic, and Montreal) and two international conferences (Nice, Prague), the third international conference devoted to integration of Constraint Programming, Artificial Intelligence, and Operations Research techniques will be held in Cork, Ireland, in 2006.
The aim of the conference is 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 problems. We explicitly welcome new ideas and methods for integrating OR and AI techniques that have arisen from real-world applications.
CP-AI-OR is intended primarily as a forum to focus on the integration and hybridization of the approaches of CP, AI, and OR technologies. A secondary aim is to provide an opportunity for researchers in one area to learn about techniques in others. 20 hiqh-quality papers have been accepted that either actively combine, integrate or contrast approaches from some of these areas, or focus on a single area of interest to all the communities involved. For details see:
http://tidel.mie.utoronto.ca/cpaior/index.php?n=Main.AcceptedPapers
As in previous years, CP-AI-OR'06 will be preceded by a Master Class where leading researchers give introductory and overview talks in a given area. This year, the topic of the Master Class will be “Modelling and Solving for Uncertainty and Change.” The Master Class is intended for PhD students, researchers, and practitioners. For details see:
http://tidel.mie.utoronto.ca/cpaior/index.php?n=Main.MasterClass
REGISTRATION DETAILS
http://tidel.mie.utoronto.ca/cpaior/index.php?n=Main.Registration
IMPORTANT DATES
Deadline for Early Registration April 28, 2006
Master Class May 30, 2006
CP-AI-OR'06 May 31-June 2, 2006
PROGRAM CO-CHAIRS
Chris Beck, University of Toronto, Canada Barbara Smith, Cork
Constraint Computation Centre, Ireland
CONFERENCE CHAIR
Barry O’Sullivan, Cork Constraint Computation Centre, Ireland
MASTER CLASS CHAIRS
Ken Brown, Cork Constraint Computation Centre, Ireland Armagan Tarim,
Cork Constraint Computation Centre, Ireland
PUBLICITY CHAIR
Ian Miguel, University of St. Andrews, Scotland
SPONSORSHIP CHAIR
Michela Milano, Universita di Bologna, Italy
PROGRAM COMMITTEE
Gautamkumar Appa, London School of Economics, UK Philippe Baptiste,
Ecole Polytechnique, France Roman Bartak, Charles University, Czech
Republic Mats Carlsson, SICS, Sweden Ondrej Cepek, Charles University,
Czech Republic Hani El Sakkout, CISCO Systems Inc.
Bernard Gendron, CRT and Univ. of Montreal, CanadaCarmen Gervet,
Brown University USA/Imperial College UK Carla Gomes, Cornell
University, USANarendra Jussien, Ecole des Mines de Nantes, France
Stefan Karisch, Carmen Systems, Canada Francois Laburthe, Bouygues,
France Andrea Lodi, Univ. of Bologna, ItalyMichela Milano, Univ. of
Bologna, Italy Gilles Pesant, CRT and Ecole Polytechnique de Montreal,
Canada Jean-Francois Puget, ILOG, France Jean-Charles Regin, ILOG,
France Michel Rueher, Univ. of Nice-Sophia Antipolis, France Meinolf
Sellmann, Brown University, USA Helmut Simonis, CrossCore
Optimization, UK Gilles Trombettoni, Univ. of Nice-Sophia Antipolis,
France Michael Trick, Carnegie Mellon University, USA Pascal van
Hentenryck, Brown University, USAMark Wallace, Monash University,
AustraliaWeixiong Zhang, Washington University, USA
ERCIM Workshop on Constraints
Call For Papers
11th ERCIM Workshop on
Constraint Solving and Constraint Logic Programming
(CSCLP 2006)
http://centria.di.fct.unl.pt/conferences/csclp06
June 26-28, 2006
FCT, Universidade Nova de Lisboa
Caparica, Portugal
Background
==========
This workshop is organized as the 11th meeting of the ERCIM
Working Group on Constraints, co-ordinated by Francois Fages.
Call for paper submissions
==========================
The workshop will cover all aspects of constraint and logic
programming, including various foundational issues,
implementation techniques, new applications as well as
teaching issues. Particular emphasis is on assessing the
current state of the art and identifying future directions.
We would like to invite authors to submit papers on all
aspects of research on constraint and logic programming.
Standard research papers, position papers and work-in-progress
papers describing current projects are all welcome.
To submit a paper to the workshop, please email a postscript
or PDF file, preferably in Springer LNCS format to the
workshop chairs at ercim06@di.fct.unl.pt.
Papers can be of any length but should not exceed 15 pages.
All submissions must be received by 5th May 2006.
Publication
===========
A printed volume of the workshop papers will be given to the
participants, free of charge. Note that the proceedings of the
workshop will also be available online here as a single pdf file.
After the workshop, we will decide whether to publish a subset
of papers in a Springer Lecture Notes on Artificial Intelligence
(LNAI) volume, as was done for previous editions of this workshop.
In this case, all the papers will have to go through a new
peer-review and selection process. Further details about this
possibility will be given during the workshop.
Important Dates
===============
Paper submission deadline: May 5th
Notification of authors: May 16th
Camera ready version deadline: June 7th
Registration deadline: June 9th
Financial support applications: June 2nd
CSCLP 2006 Workshop: June 26-28th
Registration and Scholarships
=============================
The workshop is open to all and is not restricted to ERCIM
members. There is no registration fee. However, participants
wishing to attend the workshop Banquet are kindly asked to
contribute with 30 Euros to be paid on site.
Participants are kindly asked to register for the workshop
before the registration deadline - 9th June 2006 - by sending
a message to the workshop chairs at ercim06@di.fct.unl.pt.
(Registration form available in the workshop web site).
Some limited scholarships may also be available to help
students with travel expenses. Students who need support
should ask their primary advisor to send a reference letter
to the workshop chairs at ercim06@di.fct.unl.pt before 2nd June.
To submit the camera-ready version, please send a PDF file,
preferably in Springer LNCS format to the workshop chairs at
ercim06@di.fct.unl.pt. Papers can be of any length but should
not exceed 15 pages.
Organization
============
Francisco Azevedo (CENTRIA, FCT/UNL, Portugal)
Pedro Barahona (CENTRIA, FCT/UNL, Portugal)
Francois Fages (INRIA, France)
Francesca Rossi (University of Padova, Italy)
Yahoo! Discussion Group on Constraints
A Yahoo! Group dedicated to constraints has been established. The purpose of this group is to encourage discussion amongst the community, in particular in order to highlight issues that should be addressed by the ACP EC, as well as providing an online archive for general discussions.
To visit and join the group go to:
http://groups.yahoo.com/group/constraints/
The advantage of a Yahoo! Group is that it is an easy way to manage discussions over a period of time. No email needs to come to your mailbox, but is instead archived so you can read it whenever you want. The access to the groups is limited to members of the group, but anyone can become a member by following a simple sign-up procedure.
There are many nice facilities available through the group.
For example, there is a feature for setting up online polls.
You can setup databases of various kinds and creating links to various web-sites that are of interest: I have already included links to CSPLib, CP-Online, the CP Conference Series, the Editor’s page at the Constraint Journal, CORR and several other things. Please extend this as you wish.
We look forward to seeing this resource being used by the CP community.
CONSTRAINTS Journal Accepted Papers
The Constraints Journal publishes 4 times per year. The contents of the current issue and forthcoming papers 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 here.
Constraints, Forthcoming Papers
· Constraint Models for the Covering Test Problem
Brahim Hnich, Steven D. Prestwich, Evgeny Selensky, and Barbara M. Smith
· Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction
Y.C. Law and J.H.M. Lee
· Cardinal: A Finite Sets Constraint Solver
Francisco Azevedo
· Asynchronous Forward-Checking for DisCSPs
Amnon Meisels and Roie Zivan
Constraints, Volume 11, Issue 2&3 (2006)
Special Issue of the 11th International Conference on Principles and Practice of Constraint Programming,
Dedicated to Eugene C. Freuder on the occasion of his 60th birthday
- Introduction to the Special Issue
Barry O’Sullivan and Peter van Beek
- A Tribute to Eugene Freuder
Alan K. Mackworth
- Gene Freuder and the Roots of Constraint Propagation
David L. Waltz
- Applying Ad-hoc Global Constraints with the case Constraint to Still-Life
Kenil C. K. Cheng and Roland H. C. Yap
- Symmetry Definitions for Constraint Satisfaction Problems
David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, and Barbara M. Smith
- An Integrated Method for Planning and Scheduling to Minimize Tardiness John N. Hooker
- The Impact of Search Heuristics on Heavy-Tailed Behaviour
Tudor Hulubei and Barry O’Sullivan
- Dynamic Ordering for Asynchronous Backtracking on DisCSPs
Roie Zivan and Amnon Meisels
Publications
PhD theses
Florian Letombe. De la validité des formules booléennes quantifiées : étude de complexité et exploitation de classes traitables au sein d’un prouveur QBF (in french). Université d’Artois (UFR Lens)
Supervisors : Pierre Marquis, Sylvie Coste-Marquis, Daniel Le Berre
Abstract :
This thesis is centered on QBF, the validity problem for quantified Boolean formulae.
Since QBF is computationally hard (PSPACE-complete), it is important to point out some specific cases for which the practical solving of QBF could be achieved. In this thesis, we have considered some restrictions of QBF based on the matrices of instances. Our main purpose was (1) to identify the complexity of QBF for some restrictions not considered so far and (2) to explore how to take advantage of polynomial classes for QBF within a general QBF solver in order to increase its efficiency."
Julien Bidot. A General Framework Integrating Techniques for Scheduling under Uncertainty. ILOG S.A. in collaboration with Laboratoire Génie de Production de l’Ecole Nationale d’Ingénieurs de Tarbes.
Supervisors: Bernard Grabot, Thierry Vidal, Philippe Laborie
Abstract:
For last years, a number of research investigations on task planning and scheduling under uncertainty have been conducted. This research domain comprises a large number of models, resolution techniques, and systems, and it is difficult to compare them since the existing terminologies are incomplete. However, we identified general families of approaches that can be used to structure the literature given three perpendicular axes. This new classification of the state of the art is based on the way decisions are taken.
In addition, we propose a generation and execution model for scheduling under uncertainty that combines these three families of approaches. This model is an automaton that develops when the current schedule is no longer executable or when some particular conditions are met.
The third part of this thesis concerns our experimental study. On top of ILOG Solver and Scheduler, we implemented a software prototype in C++ directly instantiated from our generation and execution model. We present new probabilistic scheduling problems and a constraint-based approach combined with simulation to solve some instances thereof.
Slides
400 updated slides about constraint programming at http://www.informatik.uni-ulm.de/pm/mitarbeiter/fruehwirth/pisa/ based on the book Essentials of Constraint Programming.
Special issue
Constraints Journal, Special Issue on Local Search Techniques in Constraint Satisfaction.
GUEST EDITORS
Yehuda Naveh, IBM Research, Haifa, Israel
Andrea Roli, Universita’ “G.D’Annunzio”, Chieti-Pescara, Italy
IMPORTANT DATES
Tentative partial abstract: April 30, 2006
Submission of papers: July 14, 2006
Notification of acceptance: November 2006
Publication of the Special Issue: early 2007
Special issue homepage:
http://www.haifa.il.ibm.com/projects/verification/octopus/cj_sls
Constraints Journal homepage:
http://ai.uwaterloo.ca/~vanbeek/Constraints/constraints.html
Guidelines for authors: http://ai.uwaterloo.ca/~vanbeek/Constraints/Instructions_for_Authors.html
Software
· FRODO: a FRamework for Open/Distributed Optimization
Dear all,
I would like to take this opportunity to announce the public release of our simulation platform for distributed constraint satisfaction/optimization problems.
It’s name is FRODO: a FRamework for Open/Distributed Optimization. The framework is implemented in Java, and simulates a multiagent environment in a single Java virtual machine. Each agent in the environment is executed asynchronously in a separate execution thread, and communicates with its peers through message exchange. The framework is highly customizable, allowing the user to implement and experiment with any distributed optimization algorithm. Support for synchronous/asynchronous message passing, monitoring and statistics, as well as problem visualization tools are provided. A number of distributed algorithms are already implemented in this framework, like the Distributed Breakout Algorithm, and the DPOP Algorithm. A number of random evaluation problems are also provided, from two distinct domains: meeting scheduling and resource allocation in a sensor network.
This is the first release (obviously not perfect, nor commercial-grade ;-) ), so we would greatly benefit from your feedback, comments, ideas for improvement, etc.
If you have any questions, no not hesitate to ask me.
For more details, downloads, etc: http://liawww.epfl.ch/frodo/
Thank you for your time, and your valuable feedback!
Best regards,
Adrian Petcu.
· Koalog Newsletter
Dear Koalog friend or user,
We are very pleased to send you this fourth newsletter.
Its goal is to keep you informed about Koalog and its activities.
We plan to send one newsletter each quarter or semester depending on the news (fresh news are still available from http://www.koalog.com/php/news.php
and we have a RSS feed at http://www.koalog.com/php/rss.php).
Don’t hesitate to reply to this email to request more information.
The content of this newsletter is as follows:
1/ Sudokus
2/ Software releases
3/ Koalog is growing
4/ Talks
1/ Sudokus
You probably know Sudokus …. but do you know that Sudokus can be easily solved using Constraint Programming? We recently published an article about this topic on http://www.java.net:
http://today.java.net/pub/a/today/2005/11/29/solving-sudokus-in-java.html
We also decided to use Koalog Constraint Solver to generate and explain Sudokus. You will find Sudokus generated by Koalog on:
- Phosphore,
- Le Monde (since January, 3rd),
- Le Monde 2 (starting this week),
- http://www.lemonde.fr (starting this week).
2/ Software releases
We are very proud to announce the release of the long awaited Koalog Constraint Solver v3.0.
KCS includes
- new constraints,
- methods for shaving variables,
- various optimizations leading to a 25% performance improvement.
More info on http://www.koalog.com/php/jcs.php.
3/ Koalog is growing
In 2006, 3 sales persons will be joining Koalog.
4/ Talks
On 2005/11/04, we were invited by Narendra Jussien at the Ecole des Mines de Nantes (http://www.emn.fr) to give a talk about Koalog Constraint Solver.
This talk is available from http://www.koalog.com/php/talks.php.
Best regards,
The Koalog team
· Koalog announces the release of Koalog Configurator v1.1
Paris, France - February 2006
Koalog Configurator is a powerful Java configuration software based on Koalog constraint programming technology. This technological choice broadens the functional possibilities of configuration: interactive configuration in any order, selection prioritization, complex pricing rules, unambiguous XML modelization, features that cannot be accurately implemented in common rule-based configurators.
Koalog Configurator comes with an intuitive Swing maintenance tool and efficient web components. A car configurator example built with Koalog Configurator web components can be seen at http://democonfig.koalog.com.
Visit http://www.koalog.com/php/jcf.php for documentation, release notes.
About Koalog: founded in 2002, headquartered in Paris, Koalog is a software company developing components and applications for problem solving, configuration, journey planning, pricing, leasing.
Visit http://www.koalog.com for additional information about Koalog.
· Gecode 1.0.0
We would like to announce the release of Gecode 1.0.0
Gecode is an open, free, portable, accessible, and efficient environment for developing constraint-based systems and applications:
open
Gecode is radically open for programming: it can be easily interfaced to other systems. It supports the programming of new propagators (as implementations of constraints), branching strategies, and search engines. New variable domains can be programmed with the same efficiency as the finite domain and integer set variables that come predefined with Gecode.
free
Gecode is distributed under a BSD-style license. All of its parts including documentation, implementations of global constraints, and examples are available as source code.
portable
Gecode is implemented in C++ that carefully follows the C++ standard. It can be compiled with modern C++ compilers and runs on a wide range of machines (including 64bit machines).
accessible
Gecode comes with extensive reference documentation that allows to focus on different programming tasks like modelling, implementing propagators, and implementing variable domains.
efficient
Gecode offers competitive performance with respect to both runtime and memory usage.
allows contributions
Gecode is designed to facilitate contributions on top of it. CP(Graph) and CP(Map) providing graph and map variables for constraint programming is available as a first contribution built on top of Gecode.
Gecode and contributions built on top of it are available from http://www.gecode.org/
· New opensource constraint solver
The jOpt open source optimization project has just released the beta version 1.0 of its CSP constraint solver.
Here’s a quick summary of features
- Finite integer numeric variables
- Floating point numeric variables
- Integer set variables
- Numeric, boolean, trigonometric, and set constraints, etc.
- Generic constraints such as summations, indexed variables (similar to having subscripts on a variable), all-different, etc.
Lots of searching capabilities:
- DFS, BFS
- Different memory models for tracking the data during searches
- Ability to define actions that will produce a search tree that are navigated by search techniques such as the order variables are selected for generation and how values are assigned
- Local Neighborhood Search techniques
For more information please visit: http://jopt.sourceforge.net
· New releases of the Parma Polyhedra Library
We are very happy to announce the availability of PPL 0.9, the latest release of the Parma Polyhedra Library, a modern library for the manipulation of convex polyhedra and other numerical abstractions especially targeted at static analysis and verification of complex software and hardware systems.
Besides improving upon almost all of the functionality available since the release of PPL 0.7 in December 2004, the two recent releases of PPL 0.8 and PPL 0.9 have expanded the usefulness of the library by providing new features that should be of great interest to people working in the research fields mentioned above. In particular, the latest release includes support for:
The Domain of Relational Rational Grids
=======================================
The class Grid can represent and manipulate the set of solutions of a finite conjunction of congruence relations. Elements of this domain can thus be used to encode information about the patterns of distribution of the values that program variables can take. Operations provided include everything that is needed in the field of static analysis and verification, including affine images, preimages and their generalizations, grid-difference and widening operators. This is the first time that one of the most precise variants of the domain initially proposed by P. Granger is made freely available to the community. Moreover, as the PPL provides several polyhedral domains as well as full support for lifting any domain to the powerset of that domain, a user of the library can now experiment with the extra precision provided by abstract domain constructions and combinations including not only Z-polyhedra, but also grid-polyhedra, grid-bounded-differences and their powersets.
The Domain of Bounded Difference Shapes
=======================================
This is a subdomain of the domain of convex polyhedra providing coarse but efficient-to-compute approximations for large analysis problems. The domain can be instantiated to use a wide range of different data types, including exact arithmetic rationals or integers, bounded precision floating point data types with controlled rounding and bounded integer data types with systematic yet efficient overflow detection. The full set of operations needed for static analysis and verification are supported, here included the semantic widening operator defined in our SAS 2005 paper.
A Linear Programming Solver Based on Exact Arithmetic
=====================================================
The class LP_Problem can be used to represent, check the satisfiability and optimize linear programming problems. The solver is based on a primal simplex algorithm using exact arithmetic.
Other enhancements include a new configuration program and Autoconf function making library usage even easier; several new operations useful for static analyzers; new output methods for debugging; improvements to the C and Prolog interfaces; several important portability improvements; and (only) a handful of bug fixes.
For more information, visit the PPL web site at
The PPL core development team:
Roberto Bagnara bagnara@cs.unipr.it
Patricia M. Hill hill@comp.leeds.ac.uk
Enea Zaffanella zaffanella@cs.unipr.it
Events
2006 Special Programme on Logic and Algorithms (6 Workshops). 16 January - 7 July 2006, Isaac Newton Institute for Mathematical Sciences at Cambridge, UK.
http://www.newton.cam.ac.uk/programmes/LAA/ws.html
Special semester on Grobner Bases and Related Methods 2006. February - July, 2006, Linz and Hagenberg, Austria.
http://www.ricam.oeaw.ac.at/srs/groeb/
Constraint Solving and Programming Track of SAC 2006, The 21st Annual ACM Symposium on Applied Computing. April 23-27, 2006, Dijon, France.
http://www.acm.org/conferences/sac/sac2006/pages/tracks.htm
DALT 2006, 4th International Workshop on Declarative Agent Languages and Technologies (held in conjunction with AAMAS 2006). 8 May 2006, Future University Hakodate, Japan.
http://www.illc.uva.nl/~ulle/DALT-2006/
CLIMA VII, Seventh International Workshop on Computational Logic in Multi-Agent Systems (held in conjunction with AAMAS 2006). May 8,9 2006, Future University, Hakodate, Japan.
http://research.nii.ac.jp/climaVII/
FLAIRS 06, Track on Secure Multiparty Computations and Distributed Constraint Reasoning. May 11-13, 2006, Holiday Inn Melbourne Beach, FL, USA.
http://www.cs.fit.edu/~msilaghi/FLAIRS06/
INCOM06, 12th IFAC Symposium on Information Control Problems in anufacturing (a Series of Special Sessions on Value-Chain Optimisation using Constraint Programming). May 17 - 19, 2006, Saint-Etienne, France.
CP-AI-OR'06, The Third International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. May 31-June 2, 2006, Cork, Ireland.
http://tidel.mie.utoronto.ca/cpaior
ICAPS-06, The 16th International Conference on Automated Planning and Scheduling. June 6-10, 2006, The English Lake District, Cumbria, U.K.
http://icaps06.icaps-conference.org/
PPSWR @ ESWC 06, 4th Workshop on Principles and Practice of Semantic Web Reasoning (Co-located with ESWC'06). 10-11 June, 2006, Budva, Montenegro.
CSCLP 2006, 11th ERCIM Workshop on Constraint Solving and Constraint Logic Programming. June 26-28, 2006, Caparica, Portugal. Paper submission deadline: May 5th, 2006.
http://centria.di.fct.unl.pt/conferences/csclp06
AITOCP 2006, “Artificial Intelligence Techniques for Optimization and Constrained Problems” at the International Conference on Artificial Intelligence IC-AI 2006. June 26-29, 2006, Monte Carlo Resort, Las Vegas, USA. Emails: mtounsi@cis.psu.edu.sa (Dr. Mohamed Tounsi) and souis@ccis.imamu.edu.sa (Dr. Samir Ouis)
AMAST 2006, 11th International Conference on Algebraic Methodology and Software Technology (co-located with MPC'06). 5-8 July 2006, Kuressaare, Estonia.
http://cs.ioc.ee/mpc-amast06/amast/
Calculemus'06, 13th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning 2006 (Co-located with ISSAC 2006). July 7-8, 2006, Genova, Italy. Submission of title and abstract: April 8, 2006.
Submission of papers: April 15, 2006.
http://www.loria.fr/~ranise/calculemus06
CHR 2006, Third Workshop on Constraint Handling Rules (Co-located with ICALP 2006). July 9, 2006, S. Servolo, Venice, Italy.
Paper submission deadline: May 7, 2006. http://www.cs.kuleuven.be/~toms/CHR2006/
ISSAC 2006, International Symposium on Symbolic and Algebraic Computation.
July 9 - 12, 2006, Genoa, Italy.
http://issac2006.dima.unige.it/
ACM PPDP 2006, 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming. July 10-12, 2006, Venice, Italy.
http://www.dsi.unive.it/ppdp2006/
The AAAI-06 Workshop on Learning for Search. July 16/17, 2006, Boston, Massachusetts.
http://www.cs.ubc.ca/~hutter/aaai06_ws
AAAI-06, Twenty-First National Conference on Artificial Intelligence. July 16-20, 2006, Boston, Massachusetts, USA.
http://www.aaai.org/Conferences/National/2006/aaai06.html
ISMP 2006, 19th International Symposium on Mathematical Programming. July 30 to August 04, 2006, Rio de Janeiro, Brazil.
Abstract submission deadline: June 10, 2006.
PRICAI'06, The Ninth Pacific Rim International Conference on Artificial Intelligence. 7-11th August, 2006, Guilin, China.
http://www.csse.monash.edu.au/pricai06
WRS06, The Sixth International Workshop on Reduction Strategies in Rewriting and Programming. August 11, 2006, Seattle, Washington.
Abstract Submission: May 8, 2006.
Paper Submission: May 15, 2006.
http://www.cs.pdx.edu/~antoy/wrs06/
SAT 2006, 9th International Conference on Theory and Applications of Satisfiability Testing. August 12 - 15, Seattle, Washington, USA.
WST 2006, Eighth International Workshop on Termination (Part of FLoC 2006).
15-16 August, 2006, Seattle, Washington.
Paper submission deadline: May 19, 2006.
http://www.cs.mu.oz.au/wst2006/
IJCAR 2006, Third International Joint Conference on Automated Reasoning. August 16-21, 2006, Seattle, USA.
http://ijcar06.uni-koblenz.de/
ALPSWS2006, International Workshop on Applications of Logic Programming in the Semantic Web and Semantic Web Services (co-located with ICLP06). 16 August, 2006, Seattle, Washington, USA.
Paper submission deadline: 12 May 2006. http://www.deri.at/events/workshops/alpsws2006
International Workshop on Preferences and Their Applications in Logic Programming Systems (held in conjunction with ICLP06). August 16, 2006, Seattle, Washington. Paper Submission Deadline: May 15th, 2006.
http://www.cs.nmsu.edu/lldap/Prefs06
ICLP'06 Doctoral Consortium, 22nd International Conference on Logic Programming (Part of Fourth Federated Logic Conference, FLoC 2006). 17-20 August, 2006, Seattle, Washington, USA.
Submission deadline: April 1, 2006.
http://www.cs.nmsu.edu/~epontell/DC2006
Search and Logic: Answer Set Programming and SAT (A Workshop affiliated with ICLP-06 and FLoC-06). August 16, 2006, Seattle, Washington, USA.
Paper Submission: May 22, 2006.
http://www.cs.sfu.ca/~SearchAndLogic/
ICLP'06, 22nd International Conference on Logic Programming (Part of Fourth Federated Logic Conference, FLoC 2006). 17-20 August, 2006, Seattle, Washington, USA.
Workshop on Modelling and Solving Problems with Constraints 2006 (Co-located with ECAI 2006). 29th August 2006, Riva del Garda, Italy.
Paper submission deadline: 15 April 2006.
http://www.cs.ucc.ie/ecai06ws/ecai06ws.html
INFERENCE METHODS BASED ON GRAPHICAL STRUCTURES OF KNOWLEDGE (a one day ECAI workshop). 29th August 2006, Riva del Garda, Italy.
Paper submission deadline: April 15, 2006.
http://www.irit.fr/LC/WIGSK06/
Multidisciplinary ECAI-06 Workshop on ADVANCES IN PREFERENCE HANDLING. Aug 28th - Aug 29th, 2006, Riva del Garda, Italy.
Paper submission deadline: April 15, 2006.
http://www.mycosima.com/ecai2006-preferences/
ECAI 2006 Workshop on Configuration. August 28 - 29, 2006, Riva del Garda, Italy.
Paper submission deadline: April 15th, 2006.
http://fmv.jku.at/ecai-config-ws-2006
ECAI 2006, 17th European Conference on Artificial Intelligence. August 28th - September 1st 2006, RIVA DEL GARDA, Italy.
SAS'06, The 13th International Static Analysis Symposium. 29-31 August 2006, Seoul, Korea.
Paper submission deadline: 7 April 2006.
PATAT 2006, the 6th International Conference on the Practice and Theory of Automated Timetabling. August 30 - September 1, 2006, Brno, Czech Republic.
OR 2006, International Conference Operations Research, special interest section “logistics and transport”. September 6th to 8th, 2006, University of Karlsruhe, Germany.
Abstract submission deadline: April 30th, 2006.
Full paper submission deadline: July 31st, 2006.
AIMSA 2006, The 12th International Conference on Artificial Intelligence: Methodology, Systems, Applications. 13-15th September, 2006, Varna, Bulgaria. Paper submission deadline: April 15, 2006.
CP 2006 CALL FOR WORKSHOP AND TUTORIAL PROPOSALS. September 25th-29th, 2006, Nantes, France.
Workshop Proposal submission deadline: March 31, 2006.
Tutorial Proposal submission deadline: May 19, 2006.
http://www.sciences.univ-nantes.fr/cp06/
CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Sept 25-29, 2006, Nantes, France.
Paper submission deadline: Apr 21, 2006.
http://www.sciences.univ-nantes.fr/cp06/
AISC-2006, AI and Symbolic Computation, September 20-22, 2006, Beijing, China.
Paper submission deadline: April 7, 2006.
http://www.cc4cm.org/aisc2006/
CSL'06, Annual Conference of the European Association for Computer Science
Logic. September 25 – 29, 2006, Szeged, Hungary.
Title & Abstract Submission deadline: 24 April, 2006.
Full Paper Submission deadline: 1May, 2006.
http://www.inf.u-szeged.hu/~csl06/
ADVIS 2006, Fourth Biennial International Conference on Advances in Information Systems, 18-20 October, 2006, Izmir, Turkey.
Paper submission deadline: April 1, 2006.
LPAR-13, The 13th International Conference on Logic for Programming Artificial Intelligence and Reasoning. 13th-17th November, 2006, Phnom Penh, Cambodia. Submission of full paper abstracts: 2nd May, 2006.
Submission of full papers: 9th May, 2006.
http://www.lix.polytechnique.fr/~hermann/LPAR2006
MICAI 2006, 5th Mexican International Conference on ARTIFICIAL INTELLIGENCE. November 13-17, 2006, Mexico.
Paper submission deadline: June 2, 2006.
AI 2006, the 19th ACS Australian Joint Conference on Artificial Intelligence. December 4 - 8, 2006, Hobart, Tasmania, Australia.
Paper submission deadline: June 30, 2006.
http://www.comp.utas.edu.au/ai06/
AI-2006, Twenty-sixth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence. December 11th - 13th, 2006, Cambridge, UK. Paper/Poster Submission: 5th June, 2006.
http://www.bcs-sgai.org/ai2006/
IJCAI-07, Twentieth International Joint Conference on Artificial Intelligence. January 6-12, 2007, Hyderabad, India.
Paper submission deadline: June 30th, 2006.
CP 2007, 13th International Conference on Principles and Practice of Constraint Programming (co-located with ICAPS 2007). Fall, 2007, Providence, RI, USA. Conference chairs: Meinolf Sellmann and Laurent Michel.
Program chair: Christian Bessiere.
Career news
DOCTORAL AND POSTDOCTORAL RESEARCH POSITIONS
· Post-Doc position WEIGHTED CONSTRAINT PROCESSING Applied mathematics and computer science department Toulouse INRA FRANCE
A 2 years postdoc position is available in our lab. in the Applied Mathematics and Computer sciences dept. at INRA in the frame of a ANR (french NSF) founded project. The project is aimed at the development, implementation and experimentation of algorithms for solving weighted constraint networks by mixing local consistency enforcing and dynamic programming like approaches. It involves three teams with a nice research record in graph decomposition, weighted constraint processing and the use of decomposition for solving weighted constraint networks and with active relations with other teams in France, Italy, Spain…
The project offers a nice spectrum of research from graph theory, development of new algorithms for weighted constraint processing, their implementation in a new platform and application to problems in biology (pedigree analysis, RNA gene finding…) using recent hardware with a large memory.
The ideal applicant will have a good knowledge of constraint processing and a taste for algorithmic development from theory to practice. Programming skills are essential. Additional knowledge in weighted constraint processing, graph decomposition and related methods is welcome. General knowledge of biology and genetics is welcome but not essential. French or english speaking is needed.
The contract should start around June 2006 (with some flexibility) and is renewable for a total duration of 2 years roughly.
Prospective applicants should contact Thomas Schiex
(http://www.inra.fr/mia/T/schiex) by phone or e-mail before March 26th,
- Use [ANR POSTDOC] for the e-mail subject.
· DOCTORAL/POSTDOCTORAL RESEARCH POSITION IN CONSTRAINT SOLVING AND PROGRAMMING
University of Ulm, Germany
A research position is available for Ph.D. students or postdocs at the Faculty of Computer Science, University of Ulm, Department of Software Engineering and Compiler Construction in the area of Constraint Handling Rules (CHR).
The successful applicant will be responsible for a research project funded by the German Research Foundation DFG. Its topic is the specification, generation, implementation and analysis of rule-based algorithms for solving of global constraints in CHR. The position thus requires knowledge and interest in one or more of the aforementioned areas.
At least a master or equivalent in computer science or strongly related area is required. The initial appointment will be for two years, beginning as soon as possible, with a possible renewal for another two years depending on the evaluation of the research foundation.
Gross salary is 56.400 Euro a year according to assistant position BAT IIa. It includes health and social insurance. Additional money for conference travel and visit of the advanced summer school on global constraints will be provided.
Ulm is a pleasant city of 150.000 on the Danube, with nearby rocks for free-climbing, close to Stuttgart, Munich, the Alps, and Lake Konstanz. Every day life requires a basic command of German.
Prospective applicants should email their resume with three references, and link to homepage and publications if available, to our secretary Claudia Hammer at
by February 28th, 2006,
or until the position is filled.
Prof. Thom Fruehwirth
c/o Claudia Hammer
University of Ulm
Faculty of Computer Science
Department PM
D-89069 Ulm, Germany
· Potential Postgraduate Scholarship at Cork Constraint Computation Centre (4C)
We are looking for people with an excellent academic background that have experience and strong interest in constraint programming and/or other fields of artificial intelligence. The EMBARK POSTGRADUATE RESEARCH Scheme (http://www.ircset.ie/grant_schemes/postgrad.html) creates an opportunity to conduct your study at Cork Constraint Computation Centre (4C): www.4c.ucc.ie Our centre is located in Ireland and is the world biggest research lab in its domain. If interested in using the Embark Initiative Postgraduate Research Scholarship Scheme (2006) at 4C, the applicant should contact me on tnordlan"at"4c.ucc.ie.
Best regards,
Tomas
Dr. Tomas Eric Nordlander,
Cork Constraint Computation Centre (
4C)
University College Cork,
College Rd, Cork, Ireland.
Tel: +353-(0)21-4255405
Fax: +353-(0)21-4255424
E-Mail: tnordlan"at"4c.ucc.ie
Web: http://4c.ucc.ie
· 1-year scholarship at the University of Padova
An opening is available for a 1-year scholarship, for people with at least 3 year of research experience after their undergraduate studies, within the group on constraint reasoning led by Francesca Rossi at the University of Padova, Italy. The work should start on June 1, 2006.
The research directions that are currently considered in this group are: constraints, soft constraints, CP-nets, preferences, bipolar preferences, preference aggregation, social choice, game theory. Further information about these lines of work can be found at the URL http://www.math.unipd.it/~frossi/research.html
Anybody interested in this scholarship should contact Francesca Rossi (frossi@math.unipd.it) before April 10, 2006 for further information on how to apply. The formal application procedure will be opened by the end of March and will close 20 days later.
- 3 research positions may be available in the Research Group on Mathematical Linguistics at Rovira i Virgili University (Tarragona, Spain) under the Ramon y Cajal scheme, which is partially funded by the Spanish Ministry for Education and Science.
The web site of the host institute is:
ELIGIBLE TOPICS (in decreasing order of priority)
Language and automata theory and its applications.
Biomolecular computing and nanotechnology.
Bioinformatics.
Language and speech technologies.
Formal theories of language acquisition and evolutionary linguistics.
Computational neuroscience.
Other related fields might still be eligible provided there are strong enough candidates for them.
JOB PROFILE
The positions are intended for experienced scientists willing to develop an academic career in the framework of the host institute for 5 years, starting in 2006-2007.
They will be filled in under the form of a work contract.
After evaluation of the 5-year performance, it is likely that the positions will become permanent.
Doctoral teaching and supervising are expected, as well as a strong involvement in the institute’s activities.
Only candidates having a high publication record will be considered.
ELIGIBILITY CONDITION
- Having been awarded the PhD degree not earlier than April 4, 1996 and not later than December 31st, 2004.
ECONOMIC CONDITIONS
Annual salary amounting 31,650 euros in the first year, before taxes (at a rate of 18%, approximately).
Up to 15,000 euros in the first two years for research expenses.
Full Social Security rights, including health assistance for the researcher and her/his family.
EVALUATION PROCEDURE
It will consist of 2 steps:
a pre-selection based on CV and carried out by the host institute,
an application by the shortlisted candidates, including essentially CV and a research project, to be assessed by the Spanish Ministry for Education and Science.
SCHEDULE
Expressions of interest are welcome until March 26, 2006. They should simply contain the candidate’s CV and mention “2006-2” in the subject line. The outcome of the pre-selection will be reported immediately after.
Pre-selected candidates will be supported in the application process by the host institute. The deadline for completing the whole process is March 31st, 2006.
Final results will be known in July 2006.
CONTACT
Carlos Martin-Vide