Constraint Programming News
volume 3, number 0, January, 2007
Jimmy Lee (events, career news)
Eric Monfroy (profiles, publications)
Toby Walsh (news, reports)
- news: including ACP News
- CONSTRAINTS journal accepted papers
- other publications: books, thesis, special issues, software
- events: forthcoming conferences and workshops
- career news: Doctoral, Postdoc, Researcher, and Intern positions
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: October 1st to December 31th, 2006
This is a short summary of the activities of the ACP EC during the months October-December 2006.
* Appointment for all the EC charges.
All the charges of the ACP (president, vice-president, secretary, treasurer and conference coordinator) were reconsidered. After an internal election process, with the following candidates:
-President: Francesca Rossi, Jean-Charles Régin
Peter van Beek,
-Secretary: Pedro Meseguer
-Treasurer: Christian Bessiere
-Conference coordinator: Barry O'Sullivan
the following people were elected:
-President: Francesca Rossi
-Vice-president: Peter van Beek
-Secretary: Pedro Meseguer
-Treasurer: Christian Bessiere
-Conference coordinator: Barry O'Sullivan
These charges will be held for one year (until CP 2007).
* Discussion on possible changes in the ACP rules.
The EC is considering the possibility to improve some of the ACP rules. To do this, a subcommittee of the EC, chaired by Michael Trick, is analyzing many other associations and is discussing possible improvements of the current set of ACP rules. The whole ACP EC will then decide on the changes, which will apply within a year.
* Feedback on Doctoral Program.
A procedure has been activated to get feedback from students that have participated in the Doctoral Program of previous conferences. This information will be used to improve the structure of the DP in future CP conferences.
* Decision for 2007 CP summer school.
The call for
bids for the CP 2007 summer school was sent out soon after CP 2006, and it has
been closed on December 20. The ACP EC decided to accept the bid prepared by
Javier Larrosa and Pedro Meseguer, who will organize the 2007 CP Summer School
Please visit the website of the Association, http://www.a4cp.org/. It explains the purpose of the ACP and its rules, and it provides links to the ACP EC elections, the Constraints Journal, the CP conferences, the CP summer school, the Yahoo! discussion group on constraints, and other activities of the ACP.
are saddened to pass on news that Marco
Cadoli (http://www.dis.uniroma1.it/~cadoli ) has passed away on November 21, 2006, after a long battle with cancer. He
leaves his beloved wife Laura and two small sons Andrea and Riccardo. Marco
made many contributions to research in constraints, satisfiability, knowledge
representation and databases. An international symposium in
We are pleased to announce that Alan Holland and Roberto Rossi, both of the Cork Constraint Computation Centre, are two of the four short-listed candidates for the Irish Software Association Student Medal for Commercially Viable Software 2006.
"The Irish Software Association (ISA) Student of the Year medal will be made to the post graduate student, who in the opinion of the judges has developed the most innovative and commercially viable software product. This also provides an opportunity to foster closer links between the software industry and Irish 3rd level institutions.
medal will be presented at the ISA Annual Software Industry Awards ceremony to
be held in the Burlington Hotel,
has received support from
* Call for Organization
6th International Planning Competition (alongside ICAPS 2008)
* European Commission Framework 6 Programme
Integrated Infrastructures Initiatives
Symbolic Computation in
TRANSNATIONAL ACCESS PROGRAMME
Research Institute for Symbolic Computation (RISC)
RISC-Linz, a research institute at the Johannes Kepler University, Austria, offers opportunities to researchers to obtain access to its infrastructure and facilities. Access is free of charge and is provided through the project SCIEnce within the 6th Framework Programme of the European Commission.
What we offer
Free access to the infrastructure, facilities, and expertise of a world-leading center in symbolic computation.
Scientific, technical, administrative, and logistic support, including travel and living expenses.
Who can benefit
Students and Researchers from various fields of sciences who use or would like to use symbolic computation in their work.
For more information and the application procedure please visit the program web page:
* European Commission Framework 6 Programme
Integrated Infrastructures Initiatives
February 5-18, 2007
* ICAPS Best Dissertation Award
The ICAPS Executive Council has established a new
ICAPS Best Dissertation Award
This award honors an outstanding Ph.D. dissertation in any area of automated planning and scheduling. It will be given during ICAPS conferences.
PhD dissertations that were completed and filed in 2005 or 2006 may be considered for the next ICAPS07 award.
The recipient of the 2007 award will receive a certificate, 500 US$ and a complementary registration to the ICAPS07 conference.
The award committee is requesting nominations of candidate PhDs.
The nomination material should include the following :
-a CV of the candidate with a complete list of publications,
-a copy of the dissertation,
-a nomination letter by the PhD advisor,
-two additional recommendation letters, or a copy of the request for such letters.
Nominations should be submitted in electronic form (preferably as a single pdf file or the url of such a file) to the ICAPS Award Committee chair: Malik.Ghallab@laas.fr
Submission deadline : January 31st 2007.
The decision will be notified by June 1st, 2007
* Post your articles in CoRR!
by Krzysztof R. Apt
By means of this short note I would like to call your attention/remind you of the e-Print archive, http://arXiv.org/ that started in 1991 as Los Alamos National Laboratory e-Print archive (LANL) by the physicist Paul Ginsparg. At present ArXiv contains more than 392,000 e-prints in Physics, Mathematics, Computer Science and Quantitative Biology. It is a fully automated electronic archive and distribution server for research papers.
* CP 2007:
*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)
The Constraints Journal has two special issues which currently have open calls for papers:
Special Issue on Abstraction and Automation in Constraint Modelling Guest editors: Alan Frisch, Ian Miguel Call for Papers: http://www.cs.st-andrews.ac.uk/~ianm/ModellingSpecialIssue.html
Special Issue on Constraint-Based Methods for Bioinformatics Guest editor: Agostino Dovier Call for Papers: http://www.dimi.uniud.it/dovier/WCBSI/
CONSTRAINTS Journal Accepted Papers
The contents of upcoming issues 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: http://ai.uwaterloo.ca/~vanbeek/Constraints/constraints.html
Volume 12, Issue 2
A CSP Search Algorithm with Responsibility Sets and Kernels
I. Razgon and A. Meisels
Design of Financial CDO Squared Transactions Using Constraint Programming
P. Flener, J. Pearson, L. G. Reyna, and O. Sivertsson
Cost-Based Filtering for Shorter Path Constraints
M.Sellmann, T. Gellermann, and R. Wright
The Complexity of Reasoning with Global Constraints
C. Bessiere, E. Hebrard, B. Hnich, and T. Walsh
Volume 12, Issue 3 (tentative)
Special Issue on Local Search
Local Search-Based Hybrid Algorithms for Finding Golomb Rulers
C. Cotta, I. Dotu, A. J. Fernandez, P. Van Hentenryck
Generic Incremental Algorithms for Local Search
M. Agren, P. Flener, J. Pearson
Local-Search Extraction of MUSes
É. Grégoire, B. Mazure, C. Piette
Satisfiability Testing of Boolean Combinations of Pseudo-boolean
Constraints using Local-search Techniques
Lengning Liu, Miroslaw Truszczy´nski
Stochastic Local Search Algorithms for Graph Set T-Colouring and
Marco Chiarandini Thomas Stutzle
-SAT 2005: satisfiability in the year
2005 General Computer Science series, Springer 2006. Enrico Giunchiglia and
-Constraint Logic Programming Using Eclipse, K. R. Apt and M. G. Wallace, Cambridge University Press, Hardback (ISBN-13: 9780521866286 | ISBN-10: 0521866286). http://www.cambridge.org/catalogue/catalogue.asp?isbn=0521866286
of Constraint Programming. Francesca Rossi, Peter van
Part I : Foundations
1. Introduction (Francesca Rossi, Peter van
Chapter 2. Constraint Satisfaction: An Emerging Paradigm (Eugene C. Freuder, Alan K. Mackworth)
Chapter 3. Constraint Propagation (Christian Bessiere)
Chapter 4. Backtracking Search Algorithms (Peter van Beek)
Chapter 5. Local Search Methods (Holger H. Hoos, Edward Tsang)
Chapter 6. Global Constraints (Willem-Jan van Hoeve, Irit Katriel)
Chapter 7. Tractable Structures for CSPs (Rina Dechter)
Chapter 8. The Complexity of Constraint Languages (David Cohen, Peter Jeavons)
Chapter 9. Soft Constraints (Pedro Meseguer, Francesca Rossi, Thomas Schiex)
Chapter 10. Symmetry in Constraint Programming (Ian P. Gent, Karen E. Petrie, Jean-Francois Puget)
Chapter 11. Modelling (Barbara M. Smith)
Part II : Extensions, Languages, and Applications
Chapter 12. Constraint Logic
Programming (Kim Marriott, Peter J. Stuckey,
Chapter 13. Constraints in Procedural
and Concurrent Languages (
Chapter 14. Finite Domain Constraint Programming Systems (Christian Schulte, Mats Carlsson)
Chapter 15. Operations Research Methods in Constraint Programming (John Hooker)
Chapter 16. Continuous and Interval Constraints(
Chapter 17. Constraints over Structured
Chapter 18. Randomness and Structure
Chapter 19. Temporal CSPs (Manolis Koubarakis)
Chapter 20. Distributed Constraint Programming (Boi Faltings)
Chapter 21. Uncertainty and Change (Kenneth N. Brown, Ian Miguel)
Chapter 22. Constraint-Based Scheduling and Planning (Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten)
Chapter 23. Vehicle Routing (Philip Kilby, Paul Shaw)
Chapter 24. Configuration (Ulrich Junker)
Chapter 25. Constraint Applications in Networks (Helmut Simonis)
Chapter 26. Bioinformatics and Constraints (Rolf Backofen, David Gilbert)
-Constraint Theory, George Friedman, ISBN: 0387234187, Springer-Verlag GmbH, 2005
-Constraint-Based Verification, Jun Yuan, Carl Pixley, Adnan Aziz, Springer; 1 edition (January 13, 2006), ISBN: 0387259473
-Constraint Reasoning for Differential Models, Volume 126 Frontiers in Artificial Intelligence and Applications, J. Cruz, July 2005, 244 pp., ISBN: 1-58603-532-0
-Constraint-Based Local Search by Pascal VanHentenryck and Laurent Michel, The MIT Press (August 1, 2005) , ISBN: 0262220776
combinatoires et applications industrielles by BENOIST Thierry. Collection
programmation par contraintes, Hermes, 2-7462-1569-1. To appear: 03-
-Précis de sudoku by JUSSIEN Narendra. Hermes, 2-7462-1559-4, 10-2006, 190p. In french.
formels et complexité pour l'informatique, by
-A to Z of sudoku by
-Trends in Constraint Programming,
Title : Automatic Solver Construction, Constraint Learning and Quantified Constraint
- M. Christian Bessière Chargé de Recherche, CNRS Reporter
- M. Jimmy Ho-Man Lee Professeur, CUHK, Hong-Kong Reporter
- Mme Christel Vrain Professeur, Université d?Orléans Examiner
Summary : Constraint Programming is a powerful tool for solving problems in AI and for Decision Support Systems. Two aspects are important: the modelling language has to be expressive and the solver efficient.
Our contributions tackle these two problems. We propose automatic solver construction techniques based on Machine Learning for an arbitrary constraint defined in extension. These techniques yield different filtering levels. When a concept known only by a subset of positive and negative examples has to be used as a constraint in a problem, we propose a technique to learn the constraint and derive from this step a propagator.
Then, we have studied the problem of quantified constraints which is able to model uncertainty or competition against an opponent. We have proposed and built a solver for an extended language which is able to express naturally quantified problems and at the same time to solve them faster.
solveurs de contraintes (in french) http://login.irin.sciences.univ-nantes.fr/thesis-private
area of this thesis is related to (cooperative) constraint solving –(C)CS. Classical CS methods yield generally poor performances
on large scale problems. New methods are oriented towards synergetic
behaviours. The literature brings numerous examples of successes associated to
the combination (in the large sense) of CS techniques. Solver cooperation -
Hybridization of complet and incomplete methods to solve CSP
Hybridization of incomplete and constraint programming techniques for solving Constraint Satisfaction Problems is generally restricted to some kind of master-slave combinations for specifc classes of problems. In this PhD thesis, we are concerned with the design of a hybrid resolution framework based on K.R. Apt's chaotic iterations. In this framework, basic resolution processes are abstracted by functions over an ordered structure. This allows us to consider the different resolution agents at a same level and to study more precisely various strategies for hybridization of local
search, genetic algorithms and constraint propagation. Hybrid resolution can be achieved as the computation of a fixed point of some specific reduction functions. Our framework opens up new and finer possibilities for hybridization/combination strategies. Our prototype implementation gave experimental results showing the interest of the model to design such hybridizations.
Keywords : CSP, local search, genetic algorithms, constraint propagation, hybrid resolution
* CONSTRAINTS Journal
Special Issue on Constraint based methods for Bioinformatics
Alessandro Dal Palu',
Email: alessandro.dalpalu AT unipr.it
Email: dovier AT dimi.uniud.it
Email: will AT informatik.uni-freiburg.de
Abstract submission: January 10th, 2007
Submission Deadline: January 31th, 2007
Notification of acceptance: April 30th, 2007
Final versions of accepted papers: June 30th, 2007
* CONSTRAINTS Journal
Special Issue on Abstraction and Automation in Constraint Modelling
+ Alan M
Expression of interest: May 1st, 2007
Submission of papers: July 1st, 2007
Notification of acceptance: October 1st, 2007
Final versions of accepted papers: Dec 1st, 2007.
Expected publication of the special Issue: 2nd issue of 2008 (Apr 1st).
* Journal on Satisfiability, Boolean Modeling and Computation (JSAT)
Special Issue on Application of constraints to formal verification (CFV)
Guest Editors: Miroslav Velev and Joao Marques-Silva
Deadline for paper submission: January 10, 2007
Topics include, but are not limited to, the following:
-application of constraint solvers to hardware verification;
-application of constraint solvers to software verification;
-dedicated solvers for formal verification problems;
-tuning SAT for formal verification and testing;
-challenging formal verification problems.
The submissions have to be in the JSAT format: http://www.isa.ewi.tudelft.nl/Jsat/ and have to be e-mailed to: firstname.lastname@example.org
If possible, please confirm your intent to submit a paper.
* Constraint Programming Letters Journal Special Issue on Arc Consistency Algorithms, Analysis, and Applications
Submissions and questions regarding this special issue of the Constraint Letters Journal may be sent electronically to Marc van Dongen (email@example.com) or by regular mail to the following address:
Marc van Dongen
Computer Science Department
Paper submission deadline: March 31, 2007
Acceptance notification: June 30, 2007
-The "ozziKs" QCSP Solver
When a quantified CSP (QCSP) is claimed to be TRUE by some solver, how can we verify that such answer is correct?
In a standard CSP, it is just a matter of checking (in polynomial time) the values assigned to the variables by the solver against each constraint in the CSP.
In the QCSP framework things are more complex: As a certificate we need a strategy. A strategy can be seen as a set of functions - one for each existentially quantified variable - yielding admissible values for existential variables as a function of some relevant subset of the universally quantified ones.
One such strategy is what we can actually check against the set of constraints to certify its validity.
Also, a strategy is a piece of information which is itself interesting (provided a "real-world" problem has been encoded into the underlying QCSP) as it provides an explicit scenario in which the validity of the quantified set of constraints is revealed.
For the case of quantified boolean constraints (QBFs), which we address here, strategies are also called simply certificates.
The software "ozziKs", whose public availability we publicise here, is the implementation of an algorithm that: builds a certificate of satisfiability C(F) - a.k.a. strategy or policy or quantified model - for any given true Quantified Boolean Formula F for which a suited inference log is available (at present, only the QBF solver sKizzo produces a suited log); verifies C(F) against F, thus certifying in a solver-independent way the validity of F; evaluates user-provided expressions of various kinds over C(F); writes to file in different formats C(F) and/or the result of the evaluation of the above mentioned expressions.
A detailed user manual is available here. Linux, OS-X, and cygwin versions are available for download at http://sKizzo.info.
Marco Benedetti, PhD
DCR-2007, Eighth International Workshop on Distributed Constraint
Reasoning (In Conjunction with IJCAI'07). January 8th, 2007,
IJCAI-07, Twentieth International
Joint Conference on Artificial Intelligence. January 6-12, 2007,
PADL'07, Ninth International Symposium on Practical
Aspects of Declarative Languages 2007 (Co-located with ACM POPL'07). January 14-15, 2007, Nice,
International Symmetry Conference. 14th to
the 17th of January, 2007, Thistle Hotel,
VMCAI'07, The Eighth International Conference on
Verification, Model Checking, and Abstract Interpretation. January 14-16, 2007, Nice,
SAC'07, 22nd Annual ACM Symposium on
Applied Computing (Track on Constraint Solving and Programming). March
DALT 2007, 5th International Workshop on Declarative
Agent Languages and Technologies (held in conjunction with AAMAS 2007), 14 or
15 May 2007,
CPAIOR 2007, The Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, May 23-26, 2007, Brussels, Belgium. Paper submission deadline: January 26, 2007. www.cs.brown.edu/sites/cpaior07
SAT'07, 10th International Conference on Theory and
Applications of Satisfiability Testing, May 28 - 31, 2007,
SMT Workshop '07, 5th International Workshop on
Satisfiability Modulo Theories (affiliated with CAV '2007), 1-2 July, 2007,
Rostering" stream at EURO XXII (the 22nd European Conference on
Operational Research), July 8-11, 2007,
*/Educational Timetabling/* stream at EURO XXII (the
22nd European Conference on Operational Research), July 8-11, 2007,
CADE21, 21st International Conference
on Automated Deduction, July 17-20, 2007 (workshops July 15-16),
AAAI'07, The Twenty-Second
National Conference on Artificial Intelligence. July 22-26, 2007,
ISSAC 2007, The International
Symposium on Symbolic and Algebraic Computation 2007, July 29 to August 1,
CP 2007, 13th International Conference on Principles
and Practice of Constraint Programming (co-located with ICAPS 2007). Fall, 2007,
Symbolic computation is the branch of mathematics and
computer science which solves problems on symbolic objects representable on a
computer. RISC-Linz, the Research Institute for Symbolic Computation of the
RISC-Linz invites students for its well established Ph.D. program in symbolic computation. For excellent applicants we offer fellowships covering tuition and living expenses.
Applications for studies starting in October should be received by February 15. For a description of application details and the RISC curriculum, see the web page
The RISC Ph.D. Coordinator
- Open position: Product Manager for ILOG OPL
There is an open position for a Product Manager in the Optimization Product Marketing division at ILOG. The position is centered around ILOG OPL Development studio which is ILOG's modeling IDE for building and deploying models and applications based on both Mathematical Programming (ILOG CPLEX) and Constraints Programming (ILOG CP) technology.
For more information see:
Although listed here as a
Greger Ottosson, PhD
Manager, Optimization Product Marketing firstname.lastname@example.org
1681 Route des Dolines Cell: +33 628 766 758
Les Taissounieres HB2 Office: +33 492 966 206
06560 Valbonne, FRANCE Fax: +33 492 966 162
- Postdoctoral Fellowship Scheme
CALL FOR APPLICANTS (2007)
The Irish Research Council for Science, Engineering and Technology invites applications for research funding under the Government of Ireland\222s Embark Postdoctoral Fellowship Scheme (2007).
The scheme, in its fifth year, will invest a total of approximately \2004.7 million into the Irish research sector and is open to researchers from all nations who are at an early stage of their postdoctoral research career and who wish to further their research in the sciences, engineering or technology, at an Irish research institution in 2007.
Closing Date: 5.00pm on Friday, 26th January, 2007.
For more information: http://www.ircset.ie/grant_schemes/postdoctoral.html
Candidates interested in applying for one of these to use at the Cork Constraint Computation Centre can contact me:
-Post doc position in
The Department of Electronics and Information at the Politecnico di Milano (
Applicants must have at least a Master degree in Science or Engineering (a Ph.D is preferred), and evidence of significant research accomplishments. The successful applicant will receive a 1 year appointment with possible extensions. Abilities in programming in tools for scientific data analysis (Matlab, Matematica, R, or other) and knowledge about Computational Chemistry are a must.
To apply or ask for more information please contact: Giuseppina Gini (email@example.com)
To apply - send letter of
application, curriculum vitae, statement of research accomplishments and goals,
and relevant publications to: the Rector of Politecnico di Milano, piazza L da
Vinci 32, 20133 MILANO (
A colloquium is scheduled for March 12, 2007, and the position will be filled by March 2007.
Science Post-Doctoral Positions -
are invited for Post-Doctoral Fellowships supporting work on the MX Project, in
the Computational Logic Laboratory at
http://www.cs.sfu.ca/research/groups/mxp/. Between 1 and 3 fellowships will be offered, depending upon final level of funding and availability of suitable candidates.
Ideal candidates will have background in logic for computing science, with an interest in several of:
*finite model theory and descriptive complexity
*constraint modelling languages
*Logic and databases or database query processing
*solvers for SAT/CSP/SMT/QBF
*combinatorial optimization and algorithms
*knowledge representation or theorem proving
The selected candidate(s) will work closely with the other members of the MX Project team on fundamental theoretical or applied problems related to the project. Work on the more applied problems may also involve interaction with our industrial partner.
Positions will commence as soon as possible after a candidate is chosen. Current project funding is for one year, with possibility of extension. Funding will depend upon background, but will be not less than Cdn $42,000, with the possibility teaching a one-semester course for additional stipend. Some funds will be available for conference travel.
Interested applicants should contact one of project leaders:
Eugenia Ternovska firstname.lastname@example.org
David Mitchell email@example.com
For full consideration, application should be made by February 10, 2007.