Volume 4, Number 2, July 2008

Constraint Programming News

volume 4, number 2, Jul 2008


            <h4>Editors: <br />
              <a target="_blank" href="http://www.cse.cuhk.edu.hk/~jlee/">Jimmy Lee</a> (events, career news) <br />
              <a target="_blank" href="http://www.sciences.univ-nantes.fr/info/perso/permanents/monfroy/">Eric Monfroy</a> (profiles, publications) <br />
              <a target="_blank" href="http://4c.ucc.ie/~tw/">Toby Walsh</a> (news, reports)</h4>

    <li><a href="#news">news</a>:  report from the ACP EC, honours       to members of the CP community, ICAPS 2010 call for proposals, Minion Users       Group Call for Members, News from the AFPC</li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#_CONSTRAINTS_Journal_Accepted">CONSTRAINTS       journal accepted papers</a></li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#_Constraint_Programming_Letters">Constraint Programming Letters       journal accepted papers</a></li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#_Other_Publications">other publications</a>: books, software</li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#_Special_Issues_CFPs">special issues cfps</a></li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#events">events</a>: forthcoming conferences and workshops</li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#career">career news</a>: new PhD and Postdoc       positions</li>
    <li defanged_style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;       mso-list:l0 level1 lfo1;tab-stops:list 36.0pt"><a href="file:///D:/mgelain/Desktop/cpnews.v4.n2.html#_Reports">report:</a> SAT-Race 2008 by Carsten       Sinz</li>
  <h2><a name="news" id="news">News</a></h2>
  <p defanged_style="text-align:justify;text-justify:inter-ideograph">Welcome to CP News, an initiative  of the <a href="http://slash.math.unipd.it/acp/">Association for Constraint  Programming</a>.</p>
  <p defanged_style="text-align:justify;text-justify:inter-ideograph">&nbsp;</p>
  <p defanged_style="text-align:justify;text-justify:inter-ideograph">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 <a href="http://www.math.unipd.it/cp-online/register">here</a>.</p>
  <p defanged_style="text-align:justify;text-justify:inter-ideograph">REPORT FROM THE  ASSOCIATION FOR CONSTRAINT PROGRAMMING</p>
  <p defanged_style="text-align:justify;text-justify:inter-ideograph">This is a short summary of activities within  the ACP during the months April-June (including some news from early July)  2008. The current Executive Committee comprises:</p>
  <p>&nbsp; - Officers:<br />

     Barry O'Sullivan (President), Jimmy H.M. Lee (Secretary), Thomas Schiex (Treasurer), Pedro Meseguer (Conference Coordinator)
  - Other Members:
     Christian Bessiere, Francesca Rossi, Christian Schulte, Michael Trick

  1. Alain Colmerauer to receive the 2008 ACP Research Excellence Award.

      The Association for Constraint Programming is honoured to announce that Alain Colmerauer (University II of Aix-Marseille, France) is the 2008 recepient of the ACP Research Excellence Award. The award will be give at a special session at CP 2008, followed by an acceptance talk by Alain.

      The previous winners of this award are:

  - 2005 Eugene Freuder, Cork Constraint Computation Centre, University College Cork
  - 2006 Pascal Van Hentenryck, Brown University
  - 2007 Rina Dechter, University of California at Irvine

      Alain was nominated for the award by Frederic Benhamou (University of Nantes).  The committee involved in deciding this award was chaired by Barry O'Sullivan (President of the ACP), Jimmy Lee (Secretary of the ACP), Rina Dechter, Eugene Freuder and Peter Stuckey. The chair of the committee would like to thank the members of the committee for their hard work and careful deliberations.

  2. Programme Chair of CP 2009

      The Association for Constraint Programming is pleased to announce that Ian Gent (University of St. Andrews) will be the Programme Chair of CP 2009.  Earlier this year, we announced that Pedro Barahona (New University of Lisbon) will be Conference Chair. We congratulate and wish Ian and Pedro every success with the conference.

  3. ACP Summer School 2008

      A very successful ACP Summer School 2008 was held in St. Andrews, Scotland, from June 30th - July 4th 2008. The topic of this year's school was "Modelling with Constraints: Theory and Practice". The summer school was organised by Ian Gent, Karen Petrie, and Angela Miguel. The speakers and tutorialists at the summer school included: Christian Bessiere, Chris Jefferson, Ian Miguel, Barry O'Sullivan, Karen Petrie, Patrick Prosser, Barbara Smith and Toby Walsh.  The ACP would like to thank all those involved in the summer school.

  4. Progress on the ACP Doctoral Research Award 2008.

      Nominations for the ACP Doctoral Research Award 2008 have been received and a committee, chaired by Mike Trick, is currently working on the process.

  5. Call for Nominations: Candidates for Election to the ACP-EC.

      We seek nominations for candidates for election to the Executive Committee (EC) of the ACP.  Candidates must be nominated by a member of the ACP or a member of the Election Committee.  Nominated persons must agree to be a candidate and must write an election statement that will be posted on the ACP election site.

      Please send your nominations to Jimmy Lee to arrive by midnight (California time) on August 10th, 2008.

      We recall that the Executive Committee of the ACP decides the venue of the annual CP international conference, as well as its program and conference chairs.  It also organizes other activities such as the CP doctoral programme, the CP summer school, the CP newsletter, web sites, etc. Finally, it retains the surplus from CP conferences and re-invests it in other activities of the CP research community.  The current members of the Executive Committee of the Association for Constraint Programming are: Christian Bessiere, Jimmy Lee, Pedro Meseguer, Barry O'Sullivan, Francesca Rossi, Thomas Schiex, Christian Schulte, and Mike Trick.

      Bylaw 5 of the ACP Bylaws dictates the election procedure and rules.  The 2008 is a transition year.  According to the transition year arrangement of the ACP Bylaws, Barry O'Sullivan and Francesca Rossi will end their term this summer.  In addition, we shall run an election for (a) three new regular members to a four year term and (b) two interim members to a two year term to the ACP EC.

      The ACP EC has appointed the following Election Committee:

      - (Chair) Jimmy Lee, Secretary of the ACP
      - Pedro Meseguer
      - Mike Trick

      for the current election exercise.

      Any member of the ACP not already an elected or ex officio member of the EC can stand for election to the EC.  One is a member of the ACP if the person has registered in at least one CP conference in the last five years (except if explicitly declining).

      All nominated candidates will be treated equally in the upcoming election. The top 3 elected candidates will serve as regular members of the EC with a 4 year term, and the next 2 will serve as interim members with a 2 year term.

      Elections will take place electronically in August-September 2008.  Results will be posted on the ACP web site before CP 2008.

      The full rules are set out in the ACP website at www.a4cp.org.

  6. Sponsorships.

      This year the ACP has agreed to sponsor the CSCLP workshop and CPAIOR. This is in addition to the ACP Summer School, the CP main conference and the CP Doctoral Programme that the ACP also supports.

Honours to members of the CP Community

Pedro Meseguer and Francesca Rossi, both members of the ACP Executive Committee, were elected ECCAI fellows.

Peter van Beek and Toby Walsh were elected AAAI Fellows.

Call for proposals to host ICAPS 2010

Deadline : Thursday July 31, 2008

The ICAPS Executive Council is seeking proposals to host the 2010 International Conference on Automated Planning & Scheduling. ICAPS is the premier international conference focused on the field of automated planning and scheduling.

- ICAPS'08 will take place in September 2008 in Sydney, Australia.
- ICAPS'09 will take place in September 2009 in Thessaloniki, Greece.

Proposals to host ICAPS'10 should include:

  • Organizers and Organizational Structure

-        The proposal should indicate proposed program chair(s) and any other proposed conference committee members (e.g., conference chair, local arrangements chair), and include a short CV of each.

  • Proposed conference dates and timetable

-        Provisional time-table - should include submission-date; reviewing period; author notification date, for conferences, workshops, etc.

  • Venue

-        Details of the venue and accommodation available to delegates including information about conference facilities, transportation access, accommodation and venue attractiveness.

-        Previous experience of the local organization team in organizing similar events.

  • Format

-        Information on the format of the conference (e.g. single track vs. multi-track, posters vs. presentations, etc.)

-        Special related events such as potential invited speakers, workshops, competitions, demonstrations, visits, etc.

-        Any planned collocation with other conferences. ICAPS was co-located with CP in 2007 and will be co-located with both CP and KR in 2008. Collocation is not a requirement for submitting a proposal.

  • An outline budget of the event, including information regarding the break-even point, registration fees and model (e.g., whether a single fee applies to all events, policy for joint registration with collocated conferences), policy and support for students and young researchers.
  • List of potential sponsors and support organizations.
  • Logistics

-        If the conference is outside North America, include a brief description of the organization that will handle the logistics (managing registration, issuing badges, staffing registration desk, financial management, etc.) When ICAPS is in North America, ICAPS uses AAAI to provide conference and administration support. AAAI may also be willing to provide conference support outside of North America and you can discuss this with AAAI directly.

-        Please note that the conference does not necessarily need to be held in the organizers' home region.  Organizers can consider hiring suitable logistical support or a separate local arrangements team to be responsible for negotiation and selection of hotel, meeting place, and social event sites.  For instance, when the conference is held in the North America, AAAI can perform these logistical functions, particularly when the proposers live outside the region selected for the conference.  The ICAPS Council has contacted AAAI and obtained further information on the costs of these services.  Organizers who wish to explore this option are encouraged to contact the Conference Liaison.

A number of other items would be positively considered, however, each of these is only one of several factors that the executive council will consider in their decision.

  • Proposals that foster interaction and cross fertilization with related fields (such as collocation with related conferences).
  • Proposals that include means for encouraging and including members of the community in early phases of their careers are also welcomed (such as the doctoral consortium).
  • Proposals that include means for fostering new areas of work and growing potentially under-represented areas of work (such as the special tracks).

Proposers should note that

  • funds are available carried over from previous conferences as seed money for future conferences. This money is required to guarantee the existence of the conference series and each organization applying to host ICAPS must show how they aim to cover all costs of the event.
  • ICAPS is a "AAAI affiliated conference": AAAI provides conference services when the conference is in North America; AAAI Press publishes the ICAPS Proceedings, including online version of the proceedings.

Proposals to host ICAPS should be sent electronically (PDF file) to: icaps-council@googlegroups.com

Please submit proposals by Thursday July 31, 2008

Proposers are welcome to submit draft proposals before that deadline. Please get in touch with the Conference Liaison Officer Shlomo Zilberstein for 

  • comments or advice on particular points
  • statistics on previous ICAPS conferences,
  • past successful proposals (pending the agreement of their proposers).

Clearly the closer to the deadline, the harder it will be to offer feedback. Information about previous and next ICAPS conferences is available at Guidelines for Conference Organizers

Minion Users Group Call for Members

Minion is a open source constraint solver currently developed by a team at Oxford and St Andrews University.  Full details of the solver can be found here.  We hope that this will be a place where all users of Minion can discuss any questions they have with regard to the constraints solver.  If you have any problems using Minion than this is the place to come to for help.  However, please also feel free to discuss features you would like Minion to have and any other related material here.  Basically, if you have anything to say about the Minion constraint solver this is the place to say it.  Please visit here to join the mailing list.

News from the AFPC

The fourth French-Speaking Constraint Programming Days (JFPC) took place during the first days of June in Nantes, France. Around 40 papers were presented during those 3 days. The programme committee was chaired by Gilles Trombettoni.

On June 4th, the general assembly of the French Association for Constraint Programming (AFPC) took place. A new Administrative Council whose president is Narendra Jussien and vice-president Christine Solnon have been elected.  The next few months will see the following topics being addressed:

   - the organisation of the 5th French-Speaking Constraint Programming Days in Orléans, France. The programme committee will be chaired by Yves Deville.
   - a new website
   - a Constraint Programming School for computer-science PhD students will be organized in 2009.

CONSTRAINTS Journal Accepted Papers

The contents of the most recently completed issue 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 13, Issue 4 (2008)

  • Evaluating ASP and Commercial Solvers on the CSPLib
    Toni Mancini, Davide Micaletto, Fabio Patrizi, Marco Cadoli
  • Minimization of Locally-Defined Submodular Functions by Optimal Soft Arc Consistency
    Martin C. Cooper
  • Combining Tree Partitioning, Precedence, and Incomparability Constraints
    Nicolas Beldiceanu, Pierre Flener, Xavier Lorca
  • A Global Chance-Constraint for Stochastic Inventory Systems under Service Level Constraints
    Roberto Rossi, S. Armagan Tarim, Brahim Hnich, Steven Prestwich
  • A Parametric Filtering Algorithm for the Graph Isomorphism Problem
    Sébastien Sorlin, Christine Solnon


Constraint Programming Letters Journal Accepted Papers

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

Volume 4 will be a special issue dedicated to Autonomous Search. It will be edited by Youssef Hamadi, Eric Monfroy, and Frederic Saubion.

Other Publications


  • Probleme SAT: Progrés et Défis. Livre sous la direction de L. Sais.
    Hermes Publishing Ltd, London, mai 2008
    To appear in the constraint programming collection (Hermes - in French). summer 2008: Resolution de Problemes Combinatoires a l'aide de Colonies de Fourmis.

Special Issues CFPs


  • SMT-COMP 2008, 4th International Satisfiability Modulo Theories Competition, July 7 - 14, 2008, Princeton, USA. 

  • MPREF-08, 4th Multidisciplinary Workshop on Advances in Preference Handling (AAAI-08 Workshop), July 13-14, 2008, Chicago, Illinois. 

  • AAAI-08 Workshop on Search in Artificial Intelligence and Robotics, July 13-14, 2008 (directly before AAAI) in Chicago, IL, USA. 

  • AAAI-08, Twenty-Third AAAI Conference on Artificial Intelligence, July 13-17, 2008, Chicago, USA. 

  • CHR 2008, Fifth Workshop on Constraint Handling Rules (Co-located with RTA 2008), July 14, 2008, Hagenberg, Austria. 
  • RTA 2008, 19th International Conference on Rewriting Techniques and Applications, July 15-17, 2008, Castle of Hagenberg, Austria.

  • UNIF 2008, 22nd International Conference on Unification, July 18, 2008, Castle of Hagenberg, Austria. 

  • ACM PPDP 2008, 10th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming, July 15-17, 2008, Valencia, Spain.

  • MoChArt-2008, Fifth Workshop on MODEL CHECKING and ARTIFICIAL INTELLIGENCE (At ECAI-2008), July 2008, Patras, Greece. 

  • Workshop on INFERENCE METHODS BASED ON GRAPHICAL STRUCTURES OF KNOWLEDGE (associated with ECAI 2008), 21st or 22nd July, 2008, Patras, Greece. 

  • Workshop on Modeling and Solving Problems with Constraints (held in conjunction with ECAI 2008), July 21-22, 2008, Patras, Greece.  

  • AIG-08, The Workshop on AI in Games (Held at ECAI-08), Patras, Greece, July, 2008. 

  • ECAI 2008 Workshop on Configuration Systems, July 21 - 22, 2008, Patras, Greece. 

  • ECAI 2008, the 18th European Conference on Artificial Intelligence, July 21-25, 2008, Patras, Greece. 

  • AMAST 2008, 12th International Conference on Algebraic Methodology and Software Technology, July 28-31, 2008, Urbana-Champaign, Illinois, USA.

  • ARW'08, 2008 Workshop on Automated Reasoning: Bridging the Gap between Theory and Practice, 30th-31st July 2008, University of Birmingham. 

  • CoSyScaRe 08, Workshop on Combining Systems for Efficient and Scalable Reasoning, 10/11 August, 2008, Sydney, Australia.
  • CFV'08, Fifth International Workshop on Constraints in Formal Verification (a satellite event of IJCAR'08), August 11, 2008, Sydney, Australia.

  • CSLP2008, 5th International Workshop on Constraints and Language Processing (as part of the European Summer School on Logic, Language and Information ESSLLI 2008), August 11-15, 2008, Hamburg, Germany. 

  • ITC 2008, The Second International Timetabling Competition (held with PATAT 2008), August 19 - 22, 2008, Montreal, Canada.

  • PATAT 2008, The 7th International Conference on the Practice and Theory of Automated Timetabling, August 19 - 22, 2008, Montreal, Canada.

  • Third International CSP Solver Competition (competition workshop affiliated with CP 2008), September 14-15, 2008, Sydney, Australia. 
  • Soft'08, 9th Workshop on Preferences and Soft Constraints (in conjunction with CP 2008), Sept 15, 2008, Sydney, Australia.

  • Counting'08, First Workshop on Counting Problems in CSP and SAT, and other neighbouring problems (in conjunction with CP 2008), Sept 14, 2008, Sydney, Australia.

  • QiCP'08, Second International Workshop on Quantification in Constraint Programming--- "Beyond Existentially Quantified Variables" (held in conjunction with CP 2008), Sept 14, 2008, Sydney, Australia.

  • SymCon'08, The Eighth International Workshop on Symmetry in Constraint Satisfaction Problems (held in conjunction with CP 2008), Sept 14, 2008, Sydney, Australia.

  • COPLAS'08, CP/ICAPS 2008 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, September 14, 2008, Sydney, Australia.

  • ModRef'08, The 7th International Workshop on Constraint Modelling and Reformulation (held in conjunction with CP 2008), Sept 15, 2008, Sydney, Australia.

  • LSCS'08, The 5th International Workshop on Local Search Techniques in Constraint Satisfaction (held in conjunction with CP 2008), Sept 15, 2008, Sydney, Australia.

  • CP 2008, 14th International Conference on Principles and Practice of Constraint Programming (co-located with ICAPS'08), September 14 - 18, 2008, Sydney, Australia. 

  • S P A R K, Scheduling and Planning Applications woRKshop (an ICAPS'08 Workshop), Sept 15, 2008, Sydney, Australia.

  • ICAPS'08 Multiagent Planning Workshop, September 14 or 15, 2008, Sydney, Australia.

  • KEPS2008, Knowledge Engineering for Planning and Scheduling (an International Workshop to be co-located with ICAPS'08), September 14 or 15, 2008, Sydney, Australia.

  • A Reality Check for Planning and Scheduling Under Uncertainty (an ICAPS'08 Workshop), September 15, 2008, Sydney, Australia.

  • ICAPS'08 Oversubscribed Planning and Scheduling Workshop, September 14 or 15, 2008, Sydney, Australia.

  • ICAPS'08, International Conference on Automated Planning and Scheduling (co-located with CP 2008), September 14-18, 2008, Sydney, Australia.  

  • SCHEALS'08, International Workshop on Scheduling in Healthcare Systems (in conjunction with ICAOR'08), 15-16 September 2008, Yerevan, Armenia. 

  • ICAOR'08, 1st International Conference on Applied Operational Research, 15-17 September 2008, Yerevan, Armenia. 
  • CSL 2008, 17th Annual Conference of the European Association for Computer Science Logic, 15 - 20 September, 2008, Bertinoro (Bologna), Italy.

  • ANTS 2008, Sixth International Conference on Ant Colony Optimization and Swarm Intelligence, September 22-24, 2008, Brussels, Belgium. 

  • WLP 2008, 22nd Workshop on (Constraint) Logic Programming, September 30 - October 1, 2008, Dresden, Germany.  Paper submission deadline: July 20, 2008.
  • ICTAI 2008, The 20th IEEE INTERNATIONAL CONFERENCE on TOOLS with ARTIFICIAL INTELLIGENCE, November 3-5, 2008, Dayton, Ohio, USA. 
  • LaSh08, WORKSHOP ON LOGIC AND SEARCH: Computation of structures from declarative descriptions, November 6-7, 2008, Leuven, Belgium.  Paper submission deadline: August 15, 2008.

  • LPAR 2008, 15th International Conference on Logic for   Programming, Artificial Intelligence and Reasoning, November 22-27, 2008, Doha, Qatar. 

  • AI 2008, Twenty-first Australasian Joint Conference on Artificial Intelligence, 1 - 5 December, 2008, Auckland, New Zealand.   

  • Fourth Doctoral Consortium, ICLP'08, 24th International Conference on Logic Programming, December 9th-13th, 2008, Udine, Italy.  Submission deadline: August 25, 2008.

  • 15th RCRA workshop: Experimental evaluation of algorithms for solving problems with combinatorial explosion (co-located with ICLP'08), December 9th-13th, 2008, Udine, Italy.  Abstract submission deadline: 1 September, 2008.  Papers submission deadline: 15 September, 2008.

  • ICLP'08, 24th International Conference on Logic Programming, December 9th-13th, 2008, Udine, Italy. 

  • PRICAI 2008, Tenth Pacific Rim International Conference on Artificial Intelligence, 15-19 December, 2008, Hanoi, Vietnam. 

  • LION 3, Learning and Intelligent OptimizatioN Conference, 14-18 January, 2009. Trento, Italy.  Paper submission deadline: 15 October, 2008.

  • Track on Constraint Solving and Programming (part of the 24th Annual ACM Symposium on Applied Computing), March 8 - 12, 2009, Waikiki Beach, Honolulu, Hawaii, USA.  Paper submission deadline: August 16, 2008.

Career news


Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong.

We are looking for motivated Postdoc fellows to work on constraint projects related to problem modeling, local search, over-constrained problems, global constraints, etc.  The ideal candidate should hold a PhD or equivalent qualification, and should normally have no more than 5 years of post-doctoral experience. Good track record in constraint related research is desirable. 

If the fellow is not a Hong Kong resident, a valid visa to work in Hong Kong must be obtained before the appointment takes effect.

Monthly salary commences at HK$23,160 per month (US$1 = HK$7.8), i.e. HK$277,920 per annum, and commensurates with qualification.  Hong Kong also enjoys a low tax rate of 15% maximum.  The appointment will be initially for one year, but can be renewed for another year subject to satisfactory performance.  Other benefits include annual leave, out-patient, and dental benefits.

We have an active research group of moderate size working on constraint programming.  Current topics of interest include, but not limited to, search algorithms (systematic, local, hybrid), problem modeling, over-constrained CSPs, and real-life applications of the above.

The University is situated in Shatin, an outskirt area of Hong Kong with convenient transportation into the city.  The campus is built on a hill-side spanning 134 hectares of land with beautiful surroundings and landscape.

Interested candidates should contact Prof. Jimmy Lee with their updated CVs.

PhD opportunities at the KRDB Research Centre, Faculty of Computer Science, Free University of Bozen-Bolzano, Italy

The Faculty of Computer Science of the Free University of Bozen-Bolzano (Italy) offers regular openings for studentships for its PhD program. Up-to-date information about how to apply for the PhD program and the studentship - including deadlines, number of positions and necessary documents - can be found in the university PhD web page (see "Public Competition Announcement for PhD courses - 24th cycle") and in the faculty PhD web page.

The grant amounts roughly to 45,000 Euro over the three years of the PhD. Substantial extra funding is available for participation in international conferences, schools, and workshops. The faculty of Computer Science and its PhD program are entirely based on the English language.


The KRDB Research Centre for Knowledge and Data of the faculty of Computer Science invites applicants to the PhD program to get in touch with the research group, in order to have a better understanding of the possible research activities in which prospective students may be involved. Relevant research topics in the centre are the following:

* Computational Logic and Deductive Databases
* Computational Logic and Constraint Programming
* Data and Information Integration
* Description Logics and Ontology Languages
* Efficient Reasoning Algorithms for Description Logics
* Intelligent Access to Web Resources
* Logic Based Approaches to Natural Language Understanding
* Logic-Based Modelling of Biological Knowledge
* Natural Language Processing
* Ontology Development and Evaluation
* P2P Database Integration
* Query Answering in Distributed Environments
* Semistructured Data Management
* Temporal Logics and Temporal Databases

Other research topics are listed in the personal web pages of the members of the KRDB Centre.

The research activities in the KRDB research centre require good knowledge of Logic and of Foundations of Databases, and some knowledge of Artificial Intelligence and of Knowledge Representation. Good knowledge of English is also preferred.


In recent years, knowledge and data base applications have progressively converged towards integrated technologies which try to overcome the limits of each single discipline. To be useful in realistic applications, a modern knowledge representation and reasoning system must be able to handle large data sets, and to provide expressive query languages. On the other hand, the information stored on the Web, in digital libraries, and in data warehouses is now very complex and with deep semantic structures, thus requiring more intelligent modelling languages and methodologies, and reasoning services on those complex representations to support design, management, flexible access, and integration.

The KRDB Research Centre was founded in 2002, and it now comprises 12 research staff and 9 PhD students. The centre aims at being an international centre of excellence in basic and applied research on KRDB technologies and at proposing to selected enterprises innovative ideas and technologies based on the developed research. The KRDB centre participated in national and international projects, it is currently involved in two European projects and three European Networks of Excellence, and it is a member of the Advisory Committee of the World Wide Web Consortium (W3C). The international prestige of the centre is evidenced by the participation of its members as conference and PC chairs, editors of international journals, invited speakers at international events, and by their publication score in international journals and conferences.


To get in contact with the KRDB Research Centre, send an email to:

  Prof. Diego Calvanese
  Faculty of Computer Science
  Free University of Bozen-Bolzano
  Piazza Domenicani, 3
  I-39100 Bolzano, Italy

  Email: calvanese@inf.unibz.it
  Phone: +39-0471-016-160
  Fax: +39-0471-016-009

The current PhD students can be contacted for more information.


Applications are invited for a post-doctoral research position in the Department of Computer Science at Loughborough University, UK.  The post will be associated with the EPSRC project 'Designing Mechanisms for Automated Resource Allocation'. Research on this project lies at the intersection of computer science and game theory.  Specifically,  it aims to investigate computational aspects of economic mechanisms such as bargaining, auctions, and coalitions, and develop mechanisms for resource allocation in multi-agent systems.  This post is funded by EPSRC for 3 years and is available as soon as possible.

The project will be undertaken in the Department of Computer Science with Dr Shaheen Fatima, in collaboration with Professor Mike Wooldridge (University of Liverpool, UK) and Professor  Nicholas R. Jennings (University of Southampton, UK).

You should possess or be about to obtain a PhD in a relevant discipline (Computer Science, Engineering, Mathematics or Economics) and have a proven track record of excellence in research, as evidenced by publications in journals or conferences. In particular, expertise in one or more of the following areas will be an advantage: multi-agent systems, game theory, and/or machine learning.

Closing date    1 August 2008
Position Reference      CO/13034
Minimum start salary    GB Pounds 25,888 per annum

Informal enquires may be addressed to:

Dr S. Fatima
Department of Computer Science
Loughborough University
LE11 3TU
United Kingdom
Tel: +44 (0) 1509 222 677
Fax: +44 (0) 1509 211 586
Email: S.S.Fatima@lboro.ac.uk

NOTE: Curriculum Vitae will only be accepted when accompanied by a completed University application form. Full details and application pack can be found here.

** Please quote Ref: CO/13034 in all enquiries **

Open Position in Computational Social Choice at University of Munich
PhD Student or Post-Doc

The Computer Science Department at the University of Munich is seeking to hire a PhD Student or postdoctoral research fellow (three years) in computational social choice, an active research area at the intersection of computer science, mathematics, and economics.

The position is associated with a large international project on the "Computational Foundations of Social Choice" (CFSC). This project is part of the LogiCCC Initiative of the European Science Foundation on "Modelling Intelligent Interaction" and involves 12 partner universities in France, Germany, Israel, the Netherlands, Turkey, the UK, and the USA. The Munich subproject is funded by the DFG and led by Dr. Felix Brandt.

The overall project will address a number of key issues in computational social choice. It aims at deepening our understanding of algorithmic and complexity-theoretic issues in social choice, at developing logic-based languages for modeling preferences and social choice problems, and at applying established techniques from AI, such as preference elicitation and learning, to problems of collective decision making.

Prospective candidates should hold a degree in Computer Science or another field relevant to the project (e.g., Mathematics). They should furthermore have the ability to work rigorously on well-defined problems and be enthusiastic about being involved in what is a new and dynamic field of research. Post-Doc candidates should have a proven track record of excellence in research, as witnessed by publications in relevant conference proceedings or journals. Good communication skills in English, both oral and written, are essential.

Salary is according to German tariff E13 (formerly BAT IIa) and will be around 40k Euro per year. The Ludwig Maximilian University of Munich is one of Germany's leading universities and located in the center of a vibrant city.

To be considered for the position, please forward a detailed curriculum vitae and selected publications (master or diploma thesis when applying for the PhD position) to Felix Brandt. Please use "CFSC" in the subject line. Applications will be accepted until the position is filled.

Postdoc position at CWI, Amsterdam

The Algorithms, Combinatorics and Optimization group (PNA1) at the Centre for Mathematics and Computer Science (CWI) in Amsterdam, the Netherlands, has for a period of one year a postdoc position in mechanism design and/or (non-)cooperative game theory.

The position has to be filled by the end of this year. Research will take place in the nationally funded project “Distributed Implementations of Adaptive Collective Decision Making” (DIACoDeM). The project employs three postdocs from three groups at CWI: PNA1, Coordination Languages (SEN3) and Computational Intelligence and Multi-agent Games (SEN4).

Further information about the project can be obtained from Prof. Krzysztof R. Apt. More information about the research carried out in the PNA1 group can be found here. Applicants are expected to have a proven research experience in the mentioned research areas.

The salary and terms of employment are in accordance with the “CAO-onderzoekinstellingen” and are based on qualifications. Moreover, CWI offers attractive working conditions, including flexibility and initial help with housing for foreigners.  The initial salary for a `fresh' postdoc is about EUR 3000.

Applications, mentioning "DIACoDeM Project", with enclosures a curriculum vitae, a list of publications and a list of references should be sent to K.R. Apt.



Report on SAT-Race 2008
Carsten Sinz

The area of SAT solving has seen tremendous progress over the last years.  SAT solvers are nowadays used as core decision procedures in many tools and applications, especially in hard- and software verification.  The development of new algorithms and the invention of novel implementation techniques has been furthered by a series of competitions, in which SAT solving programs are compared on a set of benchmark instances.

Starting with a SAT solver competition in Paderborn in 1991/92 and the Second DIMACS Challenge held at Rutgers University in 1993, then followed by a SAT solver competition in 1996 held in Beijing, a continuous yearly series of contests called SAT Competitions has been launched in 2001. In 2006, as no SAT Competition was planned for this year, a new form of competitive event, called SAT-Race, was brought into life.  It specializes on industrial benchmark instances and was now held for the second time.

SAT-Race 2008 took place between February and May 2008. The results were presented at the Eleventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2008), that took place from May 12-15 in Guangzhou, P. R. China.

In SAT-Race 2008, solvers competed in three different tracks:

 - A main track, in which "traditional" (sequential, CNF) SAT solvers were admitted,
 - Special Track 1, in which---for the first time---parallel (multi-threaded) SAT solvers were compared, and
 - Special Track 2 for structural SAT solvers, which process non-CNF input formulas in AIG format.

Each solver had to tackle 100 SAT instances. These instances were selected at random from a larger pool of instances stemming mainly from previous SAT Competitions. New instances from the realm of software verification have also been added. The largest instance (which was successfully handled by a parallel solver) contained over 11 million variables and more than 32 million clauses. The same 100 instances were used for the main and parallel track.

Before the Race itself, there were two qualification rounds, in which solvers had to prove their correctness and efficiency. Out of 43 submitted solvers 25 were admitted for the Race (16 in the main track, 3 in the parallel track, and 6 in the AIG track). As computing environment we used a Linux cluster with 16 compute nodes, each equipped with 2 Intel Xeon 5150 processors running at 2.66 GHz and 8 GB of main memory.

The first three places in each track went to the following solvers:

Main Track:
 1. MiniSat 2.1 (by N. Sörensson and N. Een): 81 solved instances (out of 100)
 2. pMiniSat (by G. Chu; a parallel solver running in sequential mode): 79 solved instances
 3. Barcelogic (by R. Nieuwenhuis et al.): 77 solved instances

Parallel Track:
 1. ManySat (by Y. Hamadi): 90 solved instances
 2. pMiniSat (by G. Chu): 87 solved instances
 3. MiraXT (by T. Schubert et al.): 73 solved instances

AIG Track:
 1. MiniSat++ 1.0 (by N. Sörensson and N. Een): 74 solved instances
 2. picoaigersat (by A. Biere): 69 solved instances
 3. MiniCirc (by N. Een and N. Sörensson): 70 solved instances

Compared to last year's SAT Competition, a further step forward in implementing SAT solvers could be observed: last year's winner of the SAT+UNSAT Industrial Category (which most closely resembles SAT Race's setting) could solve six instances less that this year's winner.  The strongest solvers, however, turned out to be multi-threaded, parallel programs this year.

In 2009 there will be another SAT Competition, which will be organized in conjunction with the SAT 2009 conference to be held in Swansea, UK.

Further information on SAT-Race 2008 can be found on the web.

SAT-Race 2008 was organized by Carsten Sinz and Hendrik Post (both University of Karlsruhe, Germany) with support and advice from Nina Amla (Cadence Design Systems, USA), Himanshu Jain (Carnegie Mellon University, USA), Toni Jussila (OneSpin Solutions, Germany), Daniel LeBerre (University d'Artois, France), Panagiotis Manolios (Northeastern University, USA), and Lintao Zhang (Microsoft Research, USA).