Volume 3, Number 3, October 2007

Constraint Programming News

volume 3, number 3, Oct 2007

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

Contents

  • news: ACP news, call for proposals for ACP summer school
  • publications: Constraint journal, special issues
  • events: forthcoming conferences and workshops
  • career news: job adverts
  • reports: 1st workshop on autonomous search

News

Association for Constraint Programming

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

2007 EC elections

To increase the level of security in the election process, a new election software was developed by Pedro Meseguer. It includes the generation of passwords, the use of encryption for vote confirmation and the duplication of votes in different servers in real time.

The 2007 ACP EC elections took place in August-September 2007. There were two open slots. The call for candidates was sent out in early July, with deadline July 30. Three candidates were presented.

While the ACP rules state that the ACP secretary should run the elections, this time the secretary (Pedro Meseguer) was one of the candidates, so the EC decided to have the elections run by another member of the EC. Jean Charles Regin voluntereed to run them but was unable to accomplish the task, so Barry O'Sullivan accepted to run them.

The call for votes was sent out on August 22. The election period ran from August 22 to September 15, 2007. Among the candidates, the elected ones are Pedro Meseguer and Thomas Schiex. They will remain in the EC for a 3 year term.

Call for 2008 CP Summer School

The call for bids for the 2008 Summer School was sent out on September 11. The deadline for bids is October 30 (earlier than previous years to give more time to the school organizers).

Members of the CP community who are interested in organizing the 2008 CP summer school should send a proposal to Jimmy Lee (jlee@cse.cuhk.edu.hk) by October 30th, 2007, containing at least the following information:

  • 1. topic of the school
  • 2. location
  • 3. dates
  • 4. organizers
  • 5. provisional budget

    Resignations

    Jean-Charles Regin, Frederic Benhamou and Narendra Jussien resigned from their positions in the EC. Meinolf Sellman and Laurent Michel, who could have one seat in the EC as CP 2007 co-chairs, decided not to take this seat.

    New ACP bylaws

    In these three months, the EC finalized the discussion, started almost one year ago, on a new version of the ACP bylaws. This discussion has been led by Mike Trick and was carried on within a subcommittee of the EC. The main goals of the new bylaws were: a full elected EC, more power to the General Assembly, and a clearer membership procedure.

    The EC proposal for new bylaws was discussed at the ACP general assembly, during the CP 2007 conference, and was approved by the assembly without any opposing vote. The new version of the bylaws will be posted soon on the ACP web site.

    CP 2007

    The CP 2007 conference took place in Providence, RI, USA, on September 22-27, 2007. It was colocated with ICAPS 2007. The conference was very successful, with 172 participants to CP and 210 to ICAPS. The program of CP 2007 included 52 paper presentations (of which 9 were application papers), 14 posters, 3 tutorials, 3 invited lectures, and 6 solver presentations. The conference received 165 submissions, of which 143 to the general track and 22 to the application track. The EC would like to thank Meinolf Sellmann, Laurent Michel, Christian Bessiere, and the whole program committee for their hard work.

     

    Publications

    Constraint journal:

    The contents of the most recently completed 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.

    Volume 12, Issue 4 (2007)

    • A Constraint-Based Approach for Annotating Music Scores with Gestural Information
      Daniele P. Radicioni and Vincenzo Lombardo
    • An Analysis of Arithmetic Constraints on Integer Intervals
      Krzysztof R. Apt and Peter Zoeteweij
    • Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems
      Y.C. Law, J.H.M. Lee, and Barbara M. Smith
    • Maxx: Test Pattern Optimisation with Local Search over an Extended Logic
      Francisco Azevedo
    Forthcoming Papers

    Special Issue on Bioinformatics and Constraints.
    Guest Editors: Agostino Dovier, Alessandro Dal Palu, Sebastian Will

    • Constraint Programming in Structural Bioinformatics.
      Pedro Barahona and Ludwig Krippahl.
    • Modelling biological networks by action languages via answer set programming
      Susanne Grell, Victoria J. Nikiforova, Torsten Schaub, Joachim Selbig.
    • Modeling Biological Systems in Stochastic Concurrent Constraint Programming
      Luca Bortolussi and Alberto Policriti.
    • DARN! A soft constraint solver for RNA motif localization
      Christine Gaspin, Thomas Schiex, Matthias Zytnicki.
    • Efficient Sequence Alignment with Side-Constraints by Cluster Tree Elimination
      Sebastian Will, Anke Busch and Rolf Backofen.
    • Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques
      Marti Sanchez, Simon de Givry, Thomas Schiex.
    • Boosting Haplotype Inference with Local Search
      Ines Lynce, Joao Marques-Silva, Steve Prestwich.

    Special issues:

    Recent Advances in Constraints: Post-proceedings of the CSCLP'07 workshop

    This book will continue a series edited by LNAI since 2002 as post-proceedings of the annual workshop on Constraint Solving and Constraint Logic Programming CSCLP of the ERCIM Working Group on Constraints.

    Many of the papers presented at CSCLP'07 are of interest to a wider audience and the intention of this book is to make them more widely accessible. Authors of papers that have been presented at the workshop are therefore invited to submit final versions that take into account the discussion at the workshop for this volume.

    In addition, we give an opportunity for other papers to appear in this volume, even when they have not been presented at the workshop.

    All submissions will be peer-reviewed. Submission of a paper implies implicit agreement to review several other submissions by the deadline.

    Important dates:

    Oct. 26th, 2007: papers due
    Dec. 14th, 2007: reviews due
    Jan. 12th, 2008: notification
    Feb. 15th, 2008: final papers due
    Papers should be formatted in Springer LNCS style and should not exceed 15 pages in that format.

    Please submit papers in .pdf format by e-mail to: Sylvain.Soliman@inria.fr before October 26th.

    Special Issue on Ant Colony Optimization of Swarm Intelligence

    Guest editors:
    Karl Doerner, Universitaet Wien, Austria
    Daniel Merkle, Universitaet Leipzig, Germany
    Thomas Stuetzle, Universite' Libre de Bruxelles, Belgium

    Submission

    All researchers are invited to submit original work on topics relevant for this special issue of the new journal Swarm Intelligence (http://www.springer.com/11721), which is published by Springer Verlag.

    Submission deadline: November 1, 2007
    Tentative publication: Summer 2008

    Authors should submit their manuscripts to the Swarm Intelligence Editorial Manager at http://www.editorialmanager.com/swrm. Please, select "Special Issue on Ant Colony Optimization" as the article type. When submitting a paper, please send at the same time also an email to Thomas Stuetzle (stuetzle nospam ulb.ac.be) with paper title and author list to inform about the submission.

    A page with up-to-date information regarding the special issue is maintained at http://iridia.ulb.ac.be/~stuetzle/SI_ACO.html.

    Lecture Notes on Artifical Intelligence: Special Issue on Recent Advances in Constraint Handling Rules

    Editors:
    Thom Fruehwirth (Thom.Fruehwirth at uni-ulm.de)
    Tom Schrijvers (Tom.Schrijvers at cs.kuleuven.be)

    Submissions

    Revised and enhanced versions of papers published at the Workshops on Constraint Handling Rules and other occasions that have not appeared in archival journals are eligible for submission.Papers describing important past research in this area which have not been published in archival journal papers are also solicited. New work, surveys and comparison of state of the art techniques are also solicited. None of the submissions should have been published in any form prior to 2002.

    When submitting already published papers with minor changes only, authors are responsible for ensuring copyright clearance with the previous publisher by obtaining a written permission to republish.

    For any doubt regarding the appropriateness of the topic of a paper for this special issue please email one of the editors.

    Papers should be written in English, and formatted using the LaTeX style files developed by Springer Verlag for LNCS. They can be downloaded from http://www.springer.de/comp/lncs/index.html

    To submit please send your paper in pdf format only to both editors. For further information, please look at: http://www.cs.kuleuven.be/~toms/chr_lncs_collection

    First call for papers: September, 2007
    Submission: December 15, 2007
    Notification: April 1, 2008
    Final version due: June 1, 2008

    Journal of Symbolic Computation: Special Issue on Symbolic and Algebraic Computation

    Guest Editors:
    Carlos D'Andrea & Bernard Mourrain

    Submission:

    • All the papers will be refereed according to the JSC standards.
    • Papers should be submitted to http://www.easychair.org/jsc-issac07/
    • DEADLINE: NOVEMBER 30, 2007
    • The format is pdf. Please prepare your manuscript by using the JSC style files, which are available from the JSC home pages at http://www4.ncsu.edu/~hong/jsc.htm.
    • Notification of acceptance: around end of February 2008.
    • The final versions should be sent in by the end of March 2008, with tex sources, in the same way as the initial submission.
    • The special issue is expected to appear by the time of ISSAC 2008.

    Books

    • Since 2005, ISTE Ltd translates and publishes books written by french and european researchers from the Hermes/Lavoisier french publishing company. As of January 1st, ISTE and John Wiley & Sons Inc. will jointly publish those books. Both trademarks will be present and the cover and will be dispatched by ISTE in Europe and Maghreb and John Wiley in the rest of the world. This is a good opportunity for european and french research works to widely spread.

     

    Events

    • INAP 2007, International Conference on Applications of Declarative Programming and Knowledge Management, October 4-6, 2007, University of Wuerzburg, Germany. Deadline for Submission: July 1, 2007.
    • LPAR 2007, The 14th International Conference on Logic for Programming Artificial Intelligence and Reasoning, 15th-19th October 2007, Yerevan, Armenia.
    • 2nd Nordic Optimization Symposium, October 18-20, 2007, Oslo, Norway.
    • KCCP-07, K-CAP 2007 WORKSHOP: Knowledge Capture and Constraint Programming (held in conjunction with KCAP 2007), October 28, 2007, Whistler, BC, Canada. Paper submission deadline: July 15, 2007.
    • ICTAI-2007, The 19th IEEE INTERNATIONAL CONFERENCE on TOOLS with ARTIFICIAL INTELLIGENCE, October 29-31, 2007, Patras, Greece.
    • MIWAI 2007, 1st Mahasarakham International Workshop on AI 2007, November 18-19, 2007, Mahasarakham, Thailand.
    • CAEPIA 2007, Workshop on Planning, Scheduling and Constraint Satisfaction, November, 12-13, 2007, Salamanca, Spain. Paper submission deadline: July 15, 2007.
    • AI 2007, Twentieth Australian Joint Conference on Artificial Intelligence, 2nd-6th December 2007, Gold Coast, Queensland, Australia. Deadline for paper submissions: 13th July 2007.
    • STCS 2007, Workshop on Search Techniques for Constraint Satisfaction (held at EPIA 2007), 3-7 December, 2007, Guimaraes, Portugal.
    • EPIA 2007, 13th Portuguese Conference on Artificial Intelligence, December 3-7, 2007, Guimaraes, Portugal.
    • LION 2007 II, Learning and Intelligent OptimizatioN Conference, December 8-13, 2007, Trento, Italy.
    • PlanSIG 2007, The 26th Workshop of the UK PLANNING AND SCHEDULING Special Interest Group, December 17-18, 2007, Prague, Czech Republic. Paper Submission Deadline: October 5, 2007.
    • ISAIM 2008, Tenth International Symposium on Artificial Intelligence and Mathematics, January 2-4, 2008, Fort Lauderdale, Florida.
    • PADL'08, Tenth International Symposium on Practical Aspects of Declarative Languages 2008 (Co-located with ACM POPL'08), January 7-8, 2008, San Francisco, USA. Paper submission deadline: August 24, 2007.
    • PEPM 2008, ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (Co-located with ACM POPL'08), January 7-8, 2008, San Francisco, USA. Paper Submission Deadline: October 17, 2007.
    • VMCAI'08, The Ninth International Conference on Verification, Model Checking and Abstract Interpretation, January 7-9, 2008, San Francisco, USA.
    • SAC 2008, Track on Constraint Solving and Programming part of the 23rd Annual ACM Symposium on Applied Computing, March 16 - 20, 2008, Fortaleza, Ceara, Brazil.
    • FLOPS 2008, Ninth International Symposium on Functional and Logic Programming, April 14 - 16, 2008, Ise, Japan. Paper Submission Deadline: October 10, 2007.
    • SAT 2008, 11th International Conference on Theory and Applications of Satisfiability Testing, May 12 - 15, 2008, Guangzhou, P. R. China. Paper Submission Deadline: January 18, 2008.
    • FLAIRS 2008, AI PLANNING AND SCHEDULING A Special Track at the 21st International FLAIRS Conference, May 15-17, 2008, Florida, USA. Paper Submission Deadline: November 19, 2007.
    • PATAT 2008, The 7th International Conference on the Practice and Theory of Automated Timetabling, August 19 - 22, 2008, Montreal, Canada. Paper Submission Deadline: January 20, 2008.
    • ITC 2007, The Second International Timetabling Competition (held with PATAT 2008), August 19 - 22, 2008, Montreal, Canada. Paper Submission Deadline: January 25, 2008.
    • CP 2008, 14th International Conference on Principles and Practice of Constraint Programming, Sydney, Australia, September 14 - 18, 2008.

    Career news

    • Postdoctoral Position at Cork Constraint Computation Centre

      The Centre for Telecommunications Value-chain Research (CTVR) and the Cork Constraint Computation Centre (4C) at University College Cork, Ireland, have a vacancy for a postdoctoral researcher to work on optimisation problems in wireless networking. Strong programming skills are necessary. Experience in the one or more of the following areas will be required: distributed computing, distributed constraint optimisation, multi-agent systems, constraint programming, local search, optimisation algorithms, combinatorial auctions and game theory. Knowledge of wireless networking would be an advantage.

      CTVR (www.ctvr.ie) is a multi-disciplinary, multi-institution research centre funded by Science Foundation Ireland. Its aim is to develop breakthrough research in areas relevant to the telecommunications industry, with particular emphasis on the economic context and value- chain impact of the research. The centre is led by Trinity College Dublin, and involves five technology strands: Emerging Networks, Radio Frequency, Photonics, Test & Reliability, and Optimisation & Management. The Optimisation and Management strand is led by 4C, working with UCD, and involves collaborative research and development in optimisation, decision support and business management in telecommunications. Sample projects include protocols for negotiating access to spectrum commons, optimised fault detection in optical networks, distributed coordination in supply chains, stochastic inventory management, demand forecasting, the economic impact of dynamic spectrum, and optimisation of backhaul networks for cellular systems.

      The Cork Constraint Computation Centre (www.4c.ucc.ie) at University College Cork is one of the leading academic centres of constraint programming research in the world. The centre has about 50 members, including academics, research staff and students, from over a dozen countries and collaborates with researcher

      Open position: Research Scientist in applied optimization at SINTEF

      There is currently an open position for a research scientist in applied optimization at SINTEF ICT in Oslo, Norway. For details, see: http://www.sintef.no/content/page61____12955.aspx

      Dynamic System Analysis & Uncertainty Research Position in Decision Support Systems Project

      Also available in same project:
      - one year position in Human Computer
      - two year position in Psychology of Decision Making
      For details see http://4c.ucc.ie/creeds/

      The Cork Constraint Computation Centre (http://4c.ucc.ie) is seeking candidates for a one-year appointment beginning in 2008 connecting dynamic systems and uncertain reasoning with constraint satisfaction problems and constraint programming. This position is part of an EU-funded project, "Constraint Reasoning Extended to Enhance Decision Support" (CREEDS), which began in July, 2006. The purpose of CREEDS is to allow 4C to extend the scope of its research activities into the field of Decision Support Systems; this will include exploring the integration of constraint programming and decision support and devising new methods to support decision making, which can be guided by theoretical treatments of decision making.

      Eligibilty:

      The applicant must have a Ph.D. or four years of research experience since obtaining a university degree and have expertise in relevant areas, such as forecasting, prediction, simulation or reasoning under uncertainty. In addition, any experience in constraint programming would be an advantage.EU-requirements: The applicant must not have worked or studied in Ireland for more than 12 months during the past 3 years. Preference will be given to Researchers from the EU, Associated States, and to researchers that have resided more than 4 years in the EU or Associated states.(Associated states are: Norway, Switzerland, Turkey, Iceland, Israel, Croatia, The Former Yugoslav Republic of Macedonia, Liechtenstein.)

      Job description:

      The researcher will work with and train 4C staff members in the course of carrying out research related to decision support systems. The research responsibilities involve:

    • working on the development of applications in the area of decision support;
    • examination of relations between the researcher's own area of expertise and work conducted at 4C and in constraint programming generally. This will entail production of deliverables in the form of documents that may be written up for workshop, conference, or journal submission. Critiques, surveys, and proposals may also be written up as Technical Reports;
    • leading a "talks and seminars" program in the relevant area of expertise.

      CREEDS hosted researchers will benefit from a broad exposure to constraint programming, including a master's level course offered by the Computer Science Department. Moreover, they will benefit from 4C's active visitor program: we hosts about 20 research visitors a year, for stays ranging from a few days to a few months, from all over the world.

      Each incoming researcher will be equipped with a PC and office facilities and access to the 4C and university computer network. 4C has its own administrative and systems support staff, plus support from the Computer Science Department and University administrators.

      Location:

      The Cork Constraint Computation Centre at University College Cork is one of the leading academic centres of constraint programming research in the world. The centre has about 50 staff members, including academics, research staff and students, from over a dozen countries and collaborates with researchers from many countries. It, therefore, has considerable experience absorbing non-Irish and even non-EU researchers into its organisation. 4C is collaborating on research projects with a number of companies and has an Industry Associates Program (www.4c.ucc.ie/iap) with over 50 members. 4C is based in its own building in the centre of Cork City, a short walk from the main University College Cork campus.

      Contact details:

      Interested parties can contact either Rick Wallace (r.wallace@4c.ucc.ie) or Tomas Nordlander (t.nordlander@4c.ucc.ie) or Nic Wilson (n.wilson@4c.ucc.ie).

    Reports

    First Workshop on Autonomous Search

    The first workshop on autonomous search has been held on the 23th of September in Providence (RI), as a side event of the 13th International Conference on Principles and Practice of Constraint Programming (CP 2007).

    Ten papers have been submitted and we have selected eight of them for an oral presentation during the three sessions of this meeting, which has brought together up to 30 attendants from various research areas like constraint programming, artificial intelligence and operation research.

    Through this event, we wanted to promote works interested in the dynamic and autonomous adaptation of search procedures since recent progresses in the processing of combinatorial problems have demonstrated that search algorithms can become extremely efficient when they take advantage of unsuccessful attempts to drive their exploration. For instance in modern DPLLs, the collect of conflicts feeds the variable selection heuristic, and the quality of unit propagation controls the use of the restart strategy.

    We believe that a more principled and autonomous approach for search efficiency has to be started now in Constraint Programming. This workshop represents a first important step into that direction.

    Presented works focused on different algorithmic aspects of combinatorial search. In order to provide autonomous algorithms to the end-users, it appears that two main points have to be carefully studied. First, one has to clearly understand the behaviour of the search mechanisms and, secondly, one should benefit from dynamic control techniques. Of course, other important features could be taken into account such as the structure of the instances and the model's properties.

    The proposed approaches cover the two main families of solving techniques for constrained optimization problems: complete (or exact) methods and incomplete (or approximate) methods. Since complete methods are mostly based on a search tree, the automatic control of the resolution process often relies on the underlying heuristics used to explore these search trees. Such automatic control can be based on constraints and variables handling through a dynamic exploration strategy. Concerning incomplete approaches that rely most of the time on metaheuristics, their control, and success, is mainly related to the numerous parameters that they involve (population size, noise, temperature scheme...). Therefore, the proposed techniques often consist in understanding the role of these parameters in order to provide an easiest way to set and control them.

    As organisers, we hope that this first workshop has opened new prospects for future works in the new and promising area of Autonomous Search.

    Youssef Hamadi, Eric Monfroy and Frederic Saubion