Volume 3, Number 2, July 2007

Constraint Programming News

volume 3, number 2, July 2007

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

Contents

  • news: ACP EC news, Dechter wins ACP award, AFPC
  • publications: Constraint journal, PhD theses, recent books, special issues, web resources.
  • events: forthcoming conferences and workshops
  • career news: job adverts

News

ACP EC

This is a short summary of the activities of the ACP EC during the months April-June 2007.

ACP Research award

The call for nominations was sent out in April-May, and the award committee (composed of C. Bessiere, E. Freuder, P. Meseguer (chair), F. Rossi, P. Van Hentenryck) decided to give the 2007 ACP award for research excellence to Rina Dechter, for her multiple and significant contributions to CP. Rina will receive the award at CP 2007, where she will be invited to give a talk about her reseach activities.

DP feedback procedure

Six years after the first CP doctoral program in 2001, the ACP EC decided to have a procedure where students and organizers can give their opinions about the various aspects of the doctoral program, in order to possibly improve the structure and content of this initiative in future years. Zeynep Kiziltan was in charge of the whole procedure, which involvd a detailed questionnaire to be filled in by students and organizers of the past editions of the doctoral program. Emma Rollon built a very nice web site where the questions were presented and there was also space to give open comments. The procedure was successfully received by both students and organizers, who entered their opinions. Zeynep then collected and summarized the responses in a report that will be passed to the organizers of future doctoral programs and that will also be made available on the ACP web site and possibly presented at CP 2007. The ACP EC deeply thanks both Zeynep and Emma for their hard work.

CP 2007 support

As usual, the AC EC supports fully the CP conference, and gives money even before the conference to take care of advance payments. This year we gave: 13.5K euros as seed money for the expenses of the conference, and 10K euros money to support the doctoral program.

ACP EC elections

The current members of the Executive Committee of the Association for Constraint Programming are: Frederic Benhamou, Narendra Jussien, Javier Larrosa, Jimmy Lee, Pedro Meseguer, Michela Milano, Barry O'Sullivan, Jean Charles Regin, Francesca Rossi, Christian Schulte, Mike Trick, and Peter Van Beek. According to the rules of the ACP (see www.a4cp.org), Javier Larrosa, Pedro Meseguer, Michela Milano, and Peter Van Beek will end their term this summer, while Christian Bessiere and one of the conference chairs of CP 2007 (Meinolf Sellmann or Michel Laurent) will enter the ACP EC. We are now running an election to choose two new members of the ACP EC. The call for candidates will be out very soon, with a probable deadline of July 30th to present the candidates. Elections will take place in August-mid September, and the results will be announced at CP 2007.

AFPC news

The third French-speaking Constraint Programming Days (JFPC) were held in Rocquencourt (France) from June 4 to June 6 just before the annual CSCLP ERCIM workshop. During this occasion, the French Association for Constraint Programming (AFPC) held its general assembly on June, 4. Elections took place and a new Administrative Council has been elected. The new official of the association are Narendra Jussien, president ; Christine Solnon, vice-president ; Pierre Deransart, general secretary and Bertrand Mazure, secretary.

During the 2007-2008 period, the association will organize the fourth JFPC in Nantes (France) with a programme committee defined by Gilles Trombettoni and a French-speaking school on Constraint Programming. Moreover, documents aimed at the general audience will be produced to help the promotion of Constraint Programming.

Narendra Jussien, PhD, HdR. Ecole des Mines de Nantes

 

Publications

Constraint journal:

Forthcoming Papers
  • 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
Volume 12, Issue 3 (2007)
Special Issue on Local Search Techniques in Constraint Satisfaction
  • Introduction to the Special Issue
    Yehuda Naveh and Andrea Roli
  • Local Search-Based Hybrid Algorithms for Finding Golomb Rulers
    Carlos Cotta, Ivan Dotu, Antonio J. Fernandez, and Pascal Van Hentenryck
  • Generic Incremental Algorithms for Local Search
    Magnus Agren, Pierre Flener, and Justin Pearson
  • Local-Search Extraction of MUSes
    Eric Gregoire, Bertrand Mazure, and Cedric Piette
  • Satisfiability Testing of Boolean Combinations of Pseudo-boolean Constraints using Local-search Techniques
    Lengning Liu and Miroslaw Truszczynski
  • Stochastic Local Search Algorithms for Graph Set T-Colouring and Frequency Assignment
    Marco Chiarandini and Thomas Stutzle
Volume 12, Issue 2 (June 2007)
  • A CSP Search Algorithm with Responsibility Sets and Kernels
    Igor Razgon and Amnon Meisels
  • Design of Financial CDO Squared Transactions Using Constraint Programming
    Pierre Flener, Justin Pearson, Luis G. Reyna, and Olof Sivertsson
  • Cost-Based Filtering for Shorter Path Constraints
    Meinolf Sellmann, Thorsten Gellermann, and Robert Wright
  • The Complexity of Reasoning with Global Constraints
    Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh

PhD theses:

Special issues:

Guest Editors:

  • Alan M Frisch, University of York, UK.
  • Ian Miguel, University of St Andrews, UK.

Important Dates:
Submission of papers: July 31st, 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).

Constraints Journal: Special Issue on Quantified CSPs and QBF

Guest Editors:

  • Enrico Giunchiglia. Universita di Genova, Italy
  • Kostas Stergiou University of the Aegean, Greece

    Important Dates:
    Submission of papers: September 15th, 2007
    Notification of acceptance: December 15th, 2007
    Final versions of accepted papers: February 15th, 2008

    Swarm Intelligence: Special Issue on Ant Colony Optimization

    Guest Editors:

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

    All researchers are invited to submit original work on topics relevant for this special issue of the new journal Swarm Intelligence, which is published by Springer Verlag. 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.

    Important dates:
    Submission deadline: November 1, 2007
    Tentative publication: summer 2008

    •  

    Events

    • SMT Workshop '07, 5th International Workshop on Satisfiability Modulo Theories (affiliated with CAV '2007), 1-2 July, 2007, Berlin, Germany.
    • 14th RCRA workshop: Experimental evaluation of algorithms for solving problems with combinatorial explosion, 5-6 July, 2007, CNR (National Research Council), Rome, Italy.
    • ATCP07, (an Affiliated Workshop of ICALP 2007 and LICS 2007) International Workshop on Algorithmic Topics in Constraint Programming, July 8, 2007, Wroclaw, Poland.
    • Timetabling and Rostering stream at EURO XXII (the 22nd European Conference on Operational Research), July 8-11, 2007, Prague, Czech Republic.
    • Educational Timetabling stream at EURO XXII (the 22nd European Conference on Operational Research), July 8-11, 2007, Prague, Czech Republic.
    • ACM PPDP 2007, 9th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming, July 14-16, 2007, Wroclaw, Poland.
    • CFV'07, Fourth International Workshop on Constraints in Formal Verification (satellite event to CADE-21), July 16, 2007, Bremen, Germany.
    • CADE21, 21st International Conference on Automated Deduction, July 17-20, 2007 (workshops July 15-16), International University Bremen, Germany.
    • SARA'07, (organised in cooperation with AAAI and co-located with AAAI'07) The Seventh International Symposium on Abstraction, Reformulation and Approximation, July 18-21, 2007, Whistler, Canada.
    • AAAI 2007 Workshop on Configuration (affiliated with AAAI'07), July 22-23, 2007, Vancouver, British Columbia, Canada.
    • AAAI'07, The Twenty-Second National Conference on Artificial Intelligence. July 22-26, 2007, Vancouver, British Columbia, Canada.
    • ISSAC 2007, The International Symposium on Symbolic and Algebraic Computation 2007, July 29 to August 1, 2007, Waterloo, Canada.
    • CSLP@Context07, 4th International Workshop on Constraints and Language Processing (Affiliated with CONTEXT07), 20-21 August 2007, Roskilde, Denmark.
    • SLS 2007, Engineering Stochastic Local Search Algorithms --- Designing, Implementing and Analyzing Effective Heuristics, 6-8 September, 2007, Brussels, Belgium.
    • 3rd Doctoral Consortium at (ICLP'07) the 23rd International Conference on Logic Programming, September 8-13, 2007, Porto, Portugal.
    • CHR 2007, Fourth Workshop on Constraint Handling Rules (Co-located with ICLP 2007), September 8, 2007, Porto, Portugal.
    • CICLOPS 2007, Colloquium on Implementation of Constraint LOgic Programming Systems (held in conjunction with ICLP 2007), September 8, 2007, Porto, Portugal. Paper Submission Deadline: July 1st, 2007 (strict).
    • WCB07, Workshop on Constraint Based Methods for Bioinformatics (held at ICLP07), September 13, 2007, Porto, Portugal.
    • ICLP'07, 23rd International Conference on Logic Programming, September 8-13, 2007, Porto, Portugal.
    • Doctoral Programme of CP 2007, 13th International Conference on Principles and Practice of Constraint Programming (co-located with ICAPS 2007), September 23-27, 2007, Providence, RI, USA. Email: cp-phd2007 @ aegean.gr.
    • DCR 2007, Ninth International Workshop on Distributed Constraint Reasoning (Held in conjunction with CP-07), September 23, 2007, Providence, Rhode Island, USA. Submission Deadline: July 12, 2007.
    • ModRef'07, Sixth International Workshop On Constraint Modelling and Reformulation (held at CP 2007), September 23, 2007, Providence, Rhode Island, USA. Submission deadline: Jul 4, 2007.
    • First Workshop on Autonomous Search (held at CP 2007), September 23, 2007, Providence, Rhode Island, USA.
    • SAT-SMT-CP07, second workshop on the Integration of SAT/SMT and CP techniques (held at CP 2007), September 23, 2007, Providence, Rhode Island, USA. Submission deadline: Jul 6, 2007.
    • COPLAS 2007, CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (held at CP 2007), September 23, 2007, Providence, Rhode Island, USA.
    • SymCon'07, The Seventh International Workshop on Symmetry and Constraint Satisfaction Problems (held at CP 2007), September 23, 2007, Providence, Rhode Island, USA.
    • Second International Workshop on Constraint Programming for Graphical Applications (held in Conjunction with CP 2007), September 23rd, 2007, Providence, Rhode Island, USA. Paper Submission deadline: July, 1st, 2007.
    • CP 2007, 13th International Conference on Principles and Practice of Constraint Programming (co-located with ICAPS 2007), September 23-27, 2007, Providence, RI, USA. Conference chairs: Meinolf Sellmann and Laurent Michel. Program chair: Christian Bessiere.
    • M-PREF 2007, 3rd Multidisciplinary Workshop on ADVANCES IN PREFERENCE HANDLING (Held in conjunction with VLDB 2007), September 23 or 24, Vienna, Austria.
    • ICKEPS 2007, (hosted at ICAPS 2007), The 2nd International Competition on Knowledge Engineering for Planning and Scheduling, September 22--26, 2007, Providence, Rhode Island, USA.
    • AIPL-07, Workshop on ARTIFICIAL INTELLIGENCE PLANNING and LEARNING (in conjunction with ICAPS-07), September 22, 2007, Providence, Rhode Island, USA.
    • ICAPS'07 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges, September 22nd, 2007, Providence, Rhode Island, USA.
    • ICAPS-07 Workshop on International Planning Competition: Past, Present and Future, September 23, 2007, Providence, Rhode Island, USA.
    • SSC@ICAPS07, International Workshop on Scheduling a Scheduling Competition (held in conjunction with ICAPS 2007), Sept. 22nd, 2007, Providence, Rhode Island, USA.
    • ICAPS PG 2007, The ICAPS 2007 Workshop on Planning in Games (held at ICAPS 2007), September, 23, 2007, Providence, Rhode Island, USA.
    • ICAPS-07 Workshop on Moving Planning and Scheduling Systems into the Real World (held in conjunction with ICAPS 2007), 23 September 2007, Providence, Rhode Island, U.S.A.
    • ICAPS 2007, The International Conference on Automated Planning and Scheduling (Co-located with CP 2007), September 22--26, 2007, Providence, Rhode Island, USA.
    • WLP 2007, 21st Workshop on (Constraint) Logic Programming (Co-located with INAP 2007), October 4-6, 2007, Wuerzburg, Germany.
    • 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.
    • 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.
    • 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.

     

    Career news

    • PhD studentship Available at 4C

      Position: PhD studentship; fully funded for three years.
      Location: Constraint Computation Centre, University College Cork, Ireland
      Area: Advanced Electronic Auctions for B2B Commerce, Optimisation
      Contact: Barry O'Sullivan - b.osullivan@cs.ucc.ie

      Research Topic: This project involves the study of combinatorial auctions in which multiple distinguishable items are sold. In contrast to standard single unit auctions, in a combinatorial auctions bidders bid on preferred combinations of items, thus enabling the expression of complementarities. For example, a take-off slot in Cork airport and a landing slot in Heathrow 1 hour apart complement each other because this is the precise flight time between the two cities and their combined value is much greater than that of two slots 90 minutes apart. Bidders can describe their preferences in a more expressive manner so that they can be awarded combinations of items that result in greater economic efficiency over single-item auctions.

      Combinatorial auctions present difficulties in terms of preference elicitation, how the bidder describes their preferences concisely, and winner determination. The bid-taker must choose the combination of bids that maximises revenue and this requires a sophisticated algorithmic solution, given that potentially thousands of bids may be submitted.

      This project aims to develop a combinatorial auction solution for the multi-billion euro procurement sector so that suppliers can inform purchasers of those combinations of items that cause cost reductions for suppliers, thus enabling a win-win situation for bidders and the bid-taker.

      Research manager position at PARC

      We have an open position for manager of the Embedded Reasoning group at PARC. Please find the job ad here. Feel free to forward this message. Markus Fromherz.

      President of Ireland Young Researcher Award (PIYRA) 2008

      The President of Ireland Young Researcher Award (PIYRA) is Science Foundation Ireland's most prestigious award for young researchers from around the world to carry out their research in third level institutions in Ireland. The award recognizes outstanding engineers and scientists who, early in their careers, have already demonstrated or shown exceptional potential for leadership at the frontiers of knowledge. Awardees will be selected on the basis of exceptional accomplishments in engineering and science disciplines that underpin ICT and BIO, and creative research plans that are built on work that has attracted international attention.

      SFI will invite submission of up to eight PIYRA nominations from each of the Research Bodies in Ireland. SFI expects a diverse group of nominees, including Irish and foreign nationals, currently based anywhere in the world, who will conduct their research in Ireland. Through this Award, SFI will identify the most promising of a new generation of top-tier cutting edge researchers in fields that are critical to Ireland's economic and social prosperity.

      Summary of Award:
      Duration: 5 years.
      Amount: Up to 1 million Euros direct costs.
      Eligibility Criteria: Applicants for the PIYRA 2008 competition must meet all of the following requirements.

    • Awarded PhD or equivalent no earlier than October 1st 2001.
    • Have not previously received an SFI award funded by the ICT or BIO Directorates. Researchers currently holding a Basic Research Grant or holding/applying for a Research Frontiers Programme Grant are eligible to apply.

    Deadline: Wednesday, 17th of October at 5pm
    Decision Date: Offers will be made to successful candidates in March 2008.
    Start Date: Successful applicants need to commence their grant before December 1st, 2008.
    Limit on Number of Proposals: The prospective host institution (an Irish Research Body such as a University or Institute of Technology) may submit a maximum of eight proposals for this call.
    Candidate Nominations: A potential candidate for the Award can contact any Irish Research Body and request consideration by the institution to be one of their nominees. It is up to the Research Body to determine how it will select exceptional candidates. Each candidate can only be nominated by one Research Body.
    Estimated Number of Awards: up to 10 awards

    Full details on the proposal and submission requirements and contact details for Research Bodies in Ireland are found in the proposal call:
    Call for Proposals http://www.sfi.ie/content/../uploads/documents/upload/PIYRA_2008_Programme_Call.pdf
    FAQs http://www.sfi.ie/content/../uploads/documents/upload/PIYRA_2008_FAQs.pdf

    For questions and queries on this Programme please contact the relevant Research Body directly or alternatively Dr Ruth Freeman, SFI Biosciences and Bioengineering Directorate, by email only at: piyra-at-sfi.ie

    RESEARCH POSITION: Implementation of the Bach coordination language in MANETs and application to image analysis

    The CoordiNam coordination group of the Institute of Informatics of the University of Namur has an opening for a researcher to work on a FSR project aiming at implementing the Bach coordination language in mobile ad hoc networks (MANETs) and to establish its practicability through its application to distributed image analysis techniques. The appointment is funded by the University of Namur for one year and is, in principle, for a junior researcher. It can however be transformed in a postdoc position in some cases. The net salary is approximatively 1,500.00 EUR/month for a single junior applicant and 1,800.00 EUR/month for a single postdoc applicant.

    To be considered, candidates must have a MSc degree in Computer Science or in Mathematics or equivalent. They should be comfortable with C and Java programming as well as with the Linux operating system. Publications or experiences in coordination languages, mobile computing, constraint satisfaction or image processing are a plus. For further information, please visit the project web site http://www.info.fundp.ac.be/~jmj/Fsr or contact Professor Jean-Marie Jacquet (jmj@info.fundp.ac.be).

    Application forms are delivered by the "Direction du Personnel des Facultses of two academic references, should be sent to the Rector, same postal address, with copy to Professor Jean-Marie Jacquet (Institute of Informatics, University of Namur, rue Grandgagnage 21, B-5000 Namur, Belgium, email: jmj@info.fundp.ac.be) by August 15th 2007.

    The University is located in Namur, a 100,000-inhabitant town located 50 km south from Brussels in Belgium (European Union). Established in 1831, it has about 4,800 students. Teaching and research are conducted at the highest level in the fields of natural sciences, economic and social sciences, law, humanities, medicine and computer science. The University annual budget is in excess of 35 million euros.

    The Institute of Informatics is the oldest and largest CS faculty in the French Community of Belgium. Its staff comprises 16 fulltime professors and about 60 researchers. It has graduated more than 1,300 M.Sc. and Ph.D. students since 1973.

    2 PhD and 2 Post-doc positions in Orsay, France

    2 PhD and 2 Post-doc positions are open in the area of automatic tuning of search and optimization methods in Orsay, France.

    Optimization and search methods for combinatorial or mixed discrete-continuous problems are reaching a mature state that allows users to tackle real-world problems in an efficient way. However, both exact methods (e.g. Constraint Programming) and heuristic and meta-heuristic approaches (e.g. Evolutionary Algorithms) have to face the critical issue of parameter tuning, that remains problem- and even instance-dependent, and requires past experience of the algorithm being used.

    In this context, a project is being launched at the INRIA-Microsoft joint lab in Orsay, co-headed by Youssef Hamadi (Microsoft Research, Cambridge, UK) and Marc Schoenauer (INRIA Futurs, Orsay, France). Its goal is to set up automatic tuning methods for search algorithms in e-science, allowing scientists who have little knowledge of the search technique itself to nevertheless solve their optimization problem without the need for some "optimization engineer".

    Relying on Machine Learning and statistical techniques, the project will address both off-line and on-line tuning issues, at the problem level as well as at the instance level. The target algorithms will be Constraint Programming, building on the expertise of the Constraint Reasoning Group at MSR, and meta-heuristics, with a particular emphasis on Evolutionary Algorithms, one research area of the TAO project-team at INRIA Futurs.

    Two PhD and two post-doc positions are open (to start on October 1.). The location for all positions is the new INRIA-Microsoft Joint lab in Orsay, France. The PhDs will be supervised by Youssef Hamadi (MSR), Marc Schoenauer (INRIA), and other TAO researchers. Needless to say, all the results of this project will be published and made available as Open Source.

    Profile for PhD students

    Both PhD students should have a Master in Computer Science or Applied Maths, or some equivalent diploma, with a strong background on Statistics and Machine Learning, and a solid programming experience. Some knowledge of optimization methods, either complete combinatorial methods or heuristic methods, is also mandatory. One position will be focused on Constraint Programming techniques, and the other one on Evolutionary Algorithms, but both should work together on the statistical learning techniques that are common to both problems when it comes to parameter tuning. Note that other related profiles will also be considered.

    Competencies: Constraint Programming, Meta-heuristics, Machine Learning.
    Technical skills: C, C++, C#, Matlab.
    Additional competencies: French and English, Knowledge in Biology/Bioinformatics/e-Sciences, Development experience with MS Visual Studio.
    Salary: Standard French public PhD scholarship package.

    Profile for Post-doc students

    Post-doc candidates must have completed their PhD at the start of the project. The profile of the first Post-doc position is similar to that of the PhD students above. The other Post-doc should have a strong experience in bio-informatics, related to search or Machine Learning. She will work on the applications of the project, ensuring the practical relevance of the fundamental findings of the project.

    Competencies: Constraint Programming, Meta-heuristics, Machine Learning.
    Technical skills: C, C++, C#, Matlab.
    Additional competencies: French and English, Knowledge in Biology/Bioinformatics/e-Sciences, Development experience with MS Visual Studio.
    Salary: Standard French public Post-doc package.

    Contact: Send full CV and at least two letters of reference to 'youssefh at microsoft dot com' and 'Marc dot Schoenauer at inria dot fr'.