Volume 7, Number 2, July 2011

Constraint Programming News

volume 7, number 2, July, 2011

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

Contents

News

REPORT FROM THE ASSOCIATION FOR CONSTRAINT PROGRAMMING

http://www.4c.ucc.ie/a4cp/

This is a short summary of activities within the ACP during the months April-June 2011.

The 2011 ACP Executive Committee comprises the following people, in alphabetical order (officers identified):

  • Yves Deville
  • John Hooker
  • Jimmy H.M. Lee - Secretary
  • Barry O'Sullivan - President
  • Thomas Schiex - Treasurer
  • Helmut Simonis
  • Peter Stuckey
  • Roland Yap
ACP.1. CP Conference 2011

The ACP EC would like to extend an invitation to all members of the CP community to attend the CP 2011 conference in Perugia, Italy. A sincere thanks goes to Jimmy Lee, whose job as PC Chair has taken much of his time recently as he finalised the conference proceedings. We wish Stefano Bistarelli, Conference Chair, and his team every success as they prepare for the conference in September.

Web: http://www.dmi.unipg.it/cp2011/

ACP.2. Advance Notice of the ACP General Assembly at CP 2011

The 2011 General Assembly of the Association for Constraint Programming will take place on Thursday 15th of September at 5:00pm, during the main CP conference programme. All members of the ACP are invited to attend.

ACP.3. ACP Summer School 2011

The Executive Committee of the ACP would like to congratulate Pierre Flener, Justin Pearson (both of Uppsala University, Sweden), and Christian Schulte (KTH - Royal Institute of Technology, Sweden) for organising an excellent ACP Summer School this year. The following report has been submitted by the organisers:

The ACP Summer School 2011, an advanced school on hybrid methods for CP, was held in Turunç (Turkey) from 27 June to 1 July 2011. The lecturers were Ian Gent (University of St Andrews, Scotland, UK), John Hooker (Carnegie Mellon University, USA), Laurent Michel (University of Connecticut, USA), and Michel Rueher (Université de Nice Sophia Antipolis, France), on the hybridisation of CP with SAT, MIP, SLS, and continuous optimisation, respectively. Lecture slides, photos & movies, and the participant list are uploaded at the school's website:

http://www.gecode.org/events/acp-summerschool-2011/

The school attracted 34 participants, including postdocs and industry practitioners in addition to PhD students, from all corners of the world. The all-in-one location and highly affordable rates of the Institute of Theoretical and Applied Physics (ITAP) were considered a key ingredient to the success of the school, due to the stupendous view from its lovely terrace, its succulent food and devoted personnel, and its sufficient (but not excessive) isolation from the distractions of minor and major beach resorts nearby. In addition to the daily lectures (interrupted mid-afternoon for a siesta or a quick swim), experiments were made with what was termed "intellectual nightcap", and a half-day boat cruise in the turquoise waters of the large bay provided the necessary idleness as well as material for legends...

The organisers were Pierre Flener, Justin Pearson (both of Uppsala University, Sweden), and Christian Schulte (KTH - Royal Institute of Technology, Sweden). The school benefitted from generous sponsorship of the ACP, AFCP, Cadence.com, NICTA.com.au, Quintiq.com, and SICS.se. The organisers are grateful to Barry O'Sullivan and Thomas Schiex for the generous administrative support from the ACP, to Yves Deville and Christine Solnon for all the advice they offered based on their 2010 school, and to the ITAP personnel for all the help.

ACP.4. ACP Research Excellence Award 2011

This year a strong field of nominees was received for the ACP Research Excellence Award. A committee established by the EC is responsible for selecting the winning candidate. This committee is chaired by the President of the ACP, Barry O'Sullivan. The other members of this year's committee are: Jimmy Lee (ACP Secretary and CP 2011 PC Chair), Rina Dechter, Alan Mackworth and Pascal Van Hentenryck.

ACP.5. ACP Doctoral Research Award 2011

A strong field of nominations has been received for the ACP Doctoral Research Award. A committee established by the EC is responsible for selecting the winning candidate for this award. Members from the general community are recruited to serve as reviewers and make recommendations on the overall winner. This year's committee is chaired by Roland Yap.

ACP.6. Association for Constraint Programming LinkedIn Group

The ACP have established a LinkedIn group for the association to help promote our research and activities through this professional social network platform. On behalf of the Association for Constraint Programming, the EC would like to invite everyone interested in our field to join this group. We hope it will provide you with an ideal forum for keeping people updated about what you're doing, and help you network with both academic and industry-based colleagues. We would like to acknowledge Guido Tack for the suggestion that we should create this group.

ACP.7. Call for Bids for CP-2013

We are issuing the Call for Bids for CP 2013.

CALL FOR PROPOSALS TO HOST CP-2013

We invite proposals to host the 19th International Conference on the Principles and Practice of Constraint Programming (CP-2013). Proposals are due on or before September 1st, 2011. These proposals will be evaluated by the Executive Committee of the Association for Constraint Programming and a decision made for the site shortly afterwards.

The CP conferences are the premier international conferences on constraint programming. They have been held annually since 1995. CP 2012 will be held in Quebec City (Canada), while CP 2011 will be held in Perugia (Italy). Previous CP conference have been held in St. Andrews (Scotland), Lisbon (Portugal), Sydney (AUS), Providence RI (USA), Nantes (France), Sitges (Spain), Toronto (Canada), Kinsale (Ireland), Cornell (USA), Paphos (Cyprus), Singapore, Alexandria (USA), Pisa (Italy), Schloss Hagenberg (Austria), Cambridge (USA), and Cassis (France).

Proposals should be up to two pages of plain text and should address the following numbered topics:

  1. Proposal for conference chair(s).
  2. Local CP community support.
  3. University, government and industry support, especially financial.
  4. Proposed dates, and flexibility around these dates.
  5. Co-located events that might be held alongside CP.
  6. Conference and exhibition facilities (CP typically attracts between 200 and 250 delegates).
  7. Accommodation and food services.
  8. Site accessibility, attractiveness, and desirability.
  9. Previous experience in running conferences and workshops.
  10. Provisional budget.

If available, please include URLs to any additional information (e.g. web site for the conference venue or hotel).

Guidelines for the CP conference organization, as well as the duties of the conference chair(s), can be found on the ACP web site.

Proposals should be sent to the secretary of the Association for Constraint Programming committee preferably by email to secretary@a4cp.org. In preparing a proposal, please feel free to address questions (e.g. regarding the suitability of the proposed dates) to the same address, or to any member of the ACP Executive Committee.

CP Standardization Efforts

The website http://cpstandards.org is devoted to CP Standardization and presents ongoing efforts in this direction. The latest noticeable progress has been done in two directions:

  1. Developing JSR-331, a Java CP API. JSR-331 has successfully passed the Public Review Vote - see http://jcp.org/en/jsr/results?id=5118. Now it has 3 working implementations based on open source CP solvers (Choco, Constrainer, and JaCoP) and many examples that explain how to use the standard to represent and solve different CSPs. These JSR-331 implementations currently support integer, boolean, and set constrained variables, and many popular binary and global constraints. The implementation of real constrained variables is under way. The latest User Manual can be found at http://4c110.ucc.ie/cpstandards/files/JSR331.UserManual.v072.pdf. To download and try JSR-331 with all examples and sources please send a request to jacobfeldman@openrules.com. The next step is to produce the JSR-331 Final Draft that will include an enhanced TCK (Technology Compatibility Kit) and more practical examples. Thanks to everybody who already contributed to creation of the JSR-331 - new comments and suggestions are very welcome.
  2. Developing a common CP XML format. A small group of ACP members (Julien Fischer, Peter Stuckey, Radoslaw Szymanek, Guido Tack with some moderation from Jacob Feldman) have modified FlatZinc XML, the XML version of FlatZinc to create a draft standard for CP solver interchange. When this standard is finalized, an ability to save/load constraint satisfaction problems in the CP XML format will be added to the common level of the JSR-331 implementation. Read more about CP XML in Peter Stuckey's post at the CP Standardization Discussion Forum and provide your comments and suggestions. A special CP Standardization discussion will be held again this year during CP 2011 in Perugia.

4C Announces Leadership Transition

The UCC Cork Constraint Computation Centre (4C) announces the retirement of its founding Director, Prof. Gene Freuder, and the appointment of a new Director, Prof. Barry O'Sullivan. 4C is a computer science research laboratory whose mission is to help computers help people make better decisions for more effective use of individual, industry and government resources.

Prof. Freuder has been appointed Emeritus Professor at UCC and will become Chair of the 4C Advisory Board. Prof. Freuder came to Ireland in the fall of 2001 as the recipient of one of the first Science Foundation Ireland (SFI) Fellow Awards. He was recruited by Prof. James Bowen of UCC, and 4C built upon Prof. Bowen's successful UCC Constraint Processing Group. 4C currently comprises around 50 academics, staff, and students, housed in the new UCC Western Gateway Building. Prof. Freuder also helped to establish the CTVR SFI CSET and the ITOBO SFI SRC. While in Ireland Prof. Freuder has been elected a Fellow of the American Association for the Advancement of Science and a Member of the Royal Irish Academy.

4C has received numerous awards for its academic achievements, and has been awarded close to 30M euro in research funding. It has worked with local industry, receiving two it@cork Awards for collaborative projects (with Abtran and TreeMetrics). It has worked with multi-national industry, helping to attract three research labs to Ireland (Bell Labs, EMC, and UTRC). It has spun off two companies (Keelvar and ThinkSmart).

Prof. O'Sullivan has long served as Associate Director of 4C, and was recently appointed UCC Professor of Constraint Programming. He is President of the international Association for Constraint Programming, Coordinator of the European ERCIM Working Group on Constraints, and Chairman of the Artificial Intelligence Association of Ireland. He is the Principal Investigator of an SFI project on New Paradigms in Constraint Programming: Applications in Data Centres, with supplementary funding for collaboration with the Health Service Executive, and the UCC Principal Investigator of a recently approved European FP7 project on Engineering the Policy-Making Life Cycle. Prof. O'Sullivan established the George Boole School Computer Laboratories project, which won an it@cork Excellence in Education Leaders Award for Scoil Chlochair Mhuire. Prof. O'Sullivan became Director of 4C on June 1, 2011.

Prof. Freuder: "UCC is very fortunate to have one of the world's top computer scientists in constraint programming to take over leadership of 4C. Prof. O'Sullivan played a key role in building 4C from the start, and I am confident that 4C will go on to even greater success under his leadership."

Prof. O'Sullivan: "4C is extremely grateful to Professor Gene Freuder, who has helped it achieve so much as its founding director. It will be a challenge to live up to his legacy, but I'm looking forward it. I'll also enjoy working on the next phase of 4C's evolution with the wonderful team of academics, principal investigators, support staff, researchers and students at the centre."

Journals

CONSTRAINTS Journal Accepted Papers

Volume 16, Number 3 / July 2011

Special Issue: Constraint Satisfaction for Planning and Scheduling Problems

Guest Editors: Roman Bartak and Miguel A. Salido

Constraint satisfaction for planning and scheduling problems
Roman Bartak and Miguel A. Salido
pp. 223-227

Hybrid search for minimal perturbation in Dynamic CSPs
Roie Zivan, Alon Grubshtein and Amnon Meisels
pp. 228-249

Explaining the cumulative propagator
Andreas Schutt, Thibaut Feydy, Peter J. Stuckey and Mark G. Wallace
pp. 250-282

Data transfer planning with tree placement for collaborative environments
Petr Holub, Hana Rudová and Miloš Liška
pp. 283-316

Constraint programming approach to a bilevel scheduling problem
András Kovács and Tamás Kis
pp. 317-340

Special Issues CFPs

OPTIMIZATION ON COMPLEX SYSTEMS, special issue on MEMETIC COMPUTING, Manuscript submission deadline: July 8, 2011.

Books

PHD/HDR

Bruno Zanuttini, HDR, Université de Caen Basse-Normandie (France), June 2011
Title: Computational Aspects of Learning, Reasoning, and Deciding
Thesis

Marie-José Huguet, HDR, LAAS-CNRS (Toulouse, France)
Title: Méthodes Arborescentes - Application à la résolution de problèmes d'ordonnancement et de transport

Book

"Constraint Programming in Music", Charlotte Truchet and Gérard Assayag editors

ISTE/Wiley, collection "Programmation par contraintes"

Abstract

Constraint Programming (CP) is a declarative programming paradigm with many academic and industrial applications (from n-queens to planning, vehicle routing, optimization, and other fields). Since the earliest works on automatic harmonization, Music Composition has been one of these applications, and a very special and challenging one due to its artistic (highly subjective) nature.

The early works on Constraint Programming (CP) in music were limited to classical music composition, as the harmonization and counterpoint rules naturally translate into constraints. Then contemporary composers began to be interested in constraints, and CP has now become an essential element in the toolbox offered by Computer-Assisted Composition systems. Several contemporary musical pieces have now been composed with constraints, but it is reasonable to ask why CP applies so naturally to music, and what are the particular features of musical problems?

This book presents information about recently developed musical CP systems, from both the scientists' and composers' points of view. It will therefore be of interest to all of the following: students and researchers of music technology; composers in the computer music scene; or music software companies, especially those trying to model high level musical behaviors (intelligent arpeggiation/arrangement on synthesizers, Band in a Box software, etc.), including music data mining and music taste engineering for online music delivery.

More information: http://iste.co.uk/index.php?f=x&ACTION=View&id=413

Tree-based Graph Partitioning Constraint

Author: Xavier Lorca
Collection "Programmation par contraintes" from ISTE/Wiley

Abstract: Combinatorial problems based on graph partitioning enable us to mathematically represent and model many practical applications. Mission planning and the routing problems occurring in logistics perfectly illustrate two such examples. Nevertheless, these problems are not based on the same partitioning pattern: generally, patterns like cycles, paths, or trees are distinguished. Moreover, the practical applications are often not limited to theoretical problems like the Hamiltonian path problem, or K-node disjoint path problems. Indeed, they usually combine the graph partitioning problem with several restrictions related to the topology of nodes and arcs. The diversity of implied constraints in real-life applications is a practical limit to the resolution of such problems by approaches considering the partitioning problem independently from each additional restriction.

This book focuses on constraint satisfaction problems related to tree partitioning problems enriched by several additional constraints that restrict the possible partitions topology. On the one hand, this title focuses on the structural properties of tree partitioning constraints. On the other hand, it is dedicated to the interactions between the tree partitioning problem and classical restrictions (such as precedence relations or incomparability relations between nodes) involved in practical applications.

Precisely, Tree-based Graph Partitioning Constraint shows how to globally take into account several restrictions within one single tree partitioning constraint. Another interesting aspect of this book is related to the implementation of such a constraint. In the context of graph-based global constraints, the book illustrates how a fully dynamic management of data structures makes the runtime of filtering algorithms independent of the graph density.

More information: http://iste.co.uk/index.php?f=x&ACTION=View&id=418

Events

Conferences

ICLP 2011, 27th International Conference on Logic Programming, July 6-10, 2011, Lexington, Kentucky, USA.

IFORS 2011, 19th Triennial Conference of the International Federation of Operational Research Societies, July 10-15, 2011, Melbourne, Australia.

Workshop on Evolutionary Computation Techniques for Constraint Handling, part of GECCO-2011, July 12-16, 2011, Dublin, Ireland.

SoCS-2011, Fourth installment of the The International Symposium on Combinatorial Search, July 15-16, 2011, Barcelona, Spain.

GKR 2011, The IJCAI-11 Workshop on Graph Structures for Knowledge Representation and Reasoning, July 16, 2011, Barcelona, Spain.

SARA 2011, Ninth Symposium on Abstraction, Reformulation, and Approximation, July 17-18, 2011, Parador de Cardona, Spain.

RCRA 2011, 18th RCRA workshop: Experimental evaluation of algorithms for solving problems with combinatorial explosion, July 17-18, 2011, Barcelona, Spain.

ICARIS 2011, 10th International Conference on Artificial Immune Systems, July 18-21, 2011, University of Cambridge, UK.

RuleML 2011@IJCAI, 5th International Symposium on Rules: Research Based, Industry Focused, July 19-21, 2011, Barcelona, Spain.

IJCAI 2011, 22nd International Joint Conference on Artificial Intelligence, July 19-22, 2011, Barcelona, Spain.

MIC 2011, 9th Metaheuristics International Conference, July 25-28, 2011, Udine, Italy.

CADE-23, 23rd International Conference on Automated Deduction, July 31-August 5, 2011, Wroclaw, Poland.

AAAI 2011, Twenty-Fifth Conference on Artificial Intelligence, August 7-11, 2011, San Francisco, California, USA.

GenPlan11, AAAI 2011 Workshop on Generalized Planning, August 8, 2011, San Francisco, California, USA.

ICAOR'11, 3rd International Conference on Applied Operational Research, August 24-26, 2011, Istanbul, Turkey.

OR 2011, International Conference on Operation Research, August 30-September 2, 2011, Zurich, Switzerland.

OR53, The 53rd Conference of the UK Operational Research Society, September 6-8, 2011, Nottingham, UK.

TIME 2011, Eighteenth International Symposium on Temporal Representation and Reasoning, September 12-14, 2011, Luebeck, Germany.

CP 2011, Seventeenth International Conference on Principles and Practice of Constraint Programming, September 12-16, 2011, Perugia, Italy.

SymCon'11, The 11th International Workshop on Symmetry in Constraint Satisfaction Problems, September 12, 2011, Perugia, Italy. Paper submission deadline: July 1, 2011.

ModRef 2011, The 10th International Workshop on Constraint Modelling and Reformulation, September 12, 2011, Perugia, Italy. Paper submission deadline: July 1, 2011.

MiniZinc 2.0 Workshop, September 12-16, Perugia, Italy.

SofT'11, 11th Workshop on Preferences and Soft Constraints, September 12-16, 2011, Perugia, Italy.

LSCS'11, 8th International Workshop on Local Search techniques in Constraint Satisfaction, September 12-16, 2011, Perugia, Italy. Paper submission deadline: July 6, 2011.

ORP3 2011, Operation Research Peripatetic Postgraduate Programme, September 13-17, 2011, Cadiz, Spain.

SLS 2011, Engineering Stochastic Local Search Algorithms - Designing, Implementing and Analyzing Effective Heuristics, September 15-17, 2011, Brussels, Belgium.

CSLP@Context'11, 6th International Workshop on Constraints and Language Processing at Context'11, September 27, 2011, Karlsruhe, Germany. Paper submission deadline: July 20, 2011.

KI 2011, 34th German Conference on Artificial Intelligence, October 4-7, 2011, Berlin, Germany.

ICTAI 2011, 23rd IEEE International Conference on Tools with Artificial Intelligence, November 7-9, 2011, Boca Raton, Florida, USA.

MIWAI 2011, 5th Multi-disciplinary International Workshop on Artificial Intelligence, December 7-9, 2011, Hyderabad, India.

LION 6, Learning and Intelligent OptimizatioN Conference, January 16-20, 2012, Paris, France. Paper submission deadline: October 14, 2011.

PADL 2012, 14th International Symposium on Practical Aspects of Declarative Languages, January 23-24, 2012, Pennsylvania, USA. Abstract submission deadline: September 10, 2011. Paper submission deadline: September 17, 2011.

Career news

Postdoctoral position at Örebro University

Center for Applied Autonomous Sensor Systems (AASS) Örebro University, Sweden

In Short

Applications are invited for a position as a post-doctoral researcher in the area of hybrid planning at Örebro University, Sweden. This is an initial 18 month appointment fully funded within the EU project GeRT -- "Generalizing Robot Manipulation Tasks". Interested candidates can apply now and until the position is filled.

About the GeRT Project

In order to work naturally in human environments such as offices and homes, robots in the future will need to be much more flexible and robust in the face of novelty than they are today. In the GeRT project we address this problem by developing new methods to cope with such novelty in manipulation tasks.

The overall aim of the GeRT project is to enable a robot to autonomously generalize its manipulation skills from a set of known objects to previously unmanipulated objects. To do so, the GeRT project includes research activities in the areas of hybrid planning (see below), perception, learning and grasping. The platform used within GeRT is the DLR robot Justin, a very advanced robot with two arms with four-fingered hands.

The GeRT consortium consists of four European partners: the German Aerospace Center (DLR) and the Max Planck Institute (Germany), the University of Birmingham (UK), and Örebro University (Sweden). More details on can be found on the project web site.

About the Position

The successful candidate will be employed as a postdoc with University for an expected duration of 18 months. The main task of the postdoc will be to perform world-class research on hybrid planning in the context of the GeRT project. Hybrid planning in this context means that, when planning for a task, the robot needs to reason both about the purposes of actions on a symbolic level, and about the kinematics and geometry of the robot and the objects it manipulates. The research is expected to involve a suitable combination of theoretical investigation, concrete implementation, and empirical validation on the Justin platform at DLR.

The postdoc will work within the local GeRT team at Örebro University, which currently includes two faculties, a postdoc and a PhD student. She or he will also collaborate with the other European partners in the GeRT project, both remotely and through physical meetings and research visits. A small amount of teaching may also be part of the postdoc's duties.

Prerequisites and Application Process

In addition to a clear interest in the research topic, the successful applicant must have a strong theoretical background in computer science, and solid programming skills. A PhD in computer science, computer engineering or comparable field is required. We particularly seek candidates with experience in artificial intelligence and planning, and with inclinations towards cross-disciplinary research. Knowledge of the Swedish language is not required, but proficiency in written/spoken English is mandatory.

To apply for the position, please send a motivation letter along with an updated CV (including at least two academic references) by email to Prof. Alessandro Saffiotti. Applications can be sent immediately, and they will be accepted until the position is filled. We are looking forward to receiving your application!

About the Place

Örebro University is a young university which currently enrolls more than 15,000 students. It is located in Örebro, a city of 130,000 inhabitants situated in central Sweden.

The Center for Applied Autonomous Sensor Systems (AASS) is one of the Strong Research Environments at Örebro University. It carries out multi-disciplinary research at the intersection of robotics, machine learning, artificial intelligence, computer vision, computer science, and measurement technology. The research and human environment at AASS is young and enthusiastic. Researchers come from a dozen different countries, in Europe and worldwide, and have different scientific and cultural backgrounds. AASS also frequently hosts international researchers and is involved in several international projects.

AASS is internationally renowned for its research in cognitive robotic systems, robot ecologies, and artificial olfaction. Further information can be found at www.aass.oru.se/Research/Robots/.

A $1M Prize for the Best Product Recommendation Algorithm

GeekWire (05/15/11) John Cook

RichRelevance and Overstock.com are offering the $1 million RecLab Prize to the developer team that builds the most powerful online recommendation engine. The companies want to create advanced algorithms that help online retailers more accurately show products that individual shoppers might be interested in. "We want to advance the state of the art by enabling really smart people in academia to work on some very interesting real-world problems," says RichRelevance scientist Darren Vengroff. The prize will be awarded to the team that builds an algorithm that provides a 10 percent or greater boost over existing product recommendations on Overstock.com. Vengroff says researchers often work on the best approximations to the real world that they can find, but in many instances those situations miss key contact and feedback components. "The RecLab approach finally solves this problem by bringing their code to the data rather than releasing the data into the wild," he says.

http://www.geekwire.com/2011/1-million-prize-product-recommendation-algorithm

Post-doctoral position in risk management

Seeking highly qualified candidates for post-doctoral position in Risk Management at University College Cork, Ireland

STOCHASTIC CONSTRAINT PROGRAMMING FOR MINIMISING RISK

Stochastic Programming is a subfield of Operations Research that can solve multi-stage decision problems. Constraint Programming is a younger subfield of Artificial Intelligence aimed at deterministic (non-stochastic) problems, with a rich modelling language and a large family of powerful solution algorithms. Stochastic Constraint Programming (SCP) is a recent hybrid of the two frameworks, designed to compactly model and efficiently solve problems involving both constraints and uncertainty. However, SCP requires further development in order to be a useful real-world tool, as most current solution algorithms do not scale up to large applications.

This project will develop SCP for risk management. It is part of a project jointly funded by the Irish Research Council for Science and Engineering Technology (IRCSET) and IBM. Three different strands will work alongside IBM in carrying out new research to make users better informed about risk, through a wide variety of mathematical and AI instruments. Its overarching objective is to bring together complementary approaches to risk assessment and delivery.

Principal Investigator: Dr S. Prestwich (s.prestwich@cs.ucc.ie)

Candidates should have a recent Ph.D. in Computer Science or Operations Research, with strong programming skills and experience in constraint programming and/or stochastic optimization.

Thesis proposal at LAAS-CNRS, Toulouse, France

Thesis proposal

Satisfiability Modulo Theories for Scheduling

General context

This thesis topic is part of a CNRS-Google project and will be hosted in a French laboratory in Toulouse: LAAS.

Contacts

Emmanuel Hebrard: emmanuel.hebrard@laas.fr
Christian Artigues: christian.artigues@laas.fr
Pierre Lopez: pierre.lopez@laas.fr

Abstract

The objective is to develop a new framework inspired from the Satisfiability Modulo Theories framework for solving scheduling problems. The main idea is to emulate the key features of satisfiability solvers - clause learning and conflict directed backjumping - whilst providing data structures and inference mechanisms from linear and constraint programming, hence adapted to temporal problems.

Description

Scheduling has been a rich application domain for a number of combinatorial optimization paradigms. Integer Linear Programming (ILP), Constraint Programming (CP), and Metaheuristics have all yielded successful methods for these problems. Recently, however, approaches inspired by the Boolean Satisfiability (SAT) world have been proven to be extremely successful for a wide range of scheduling problems [1][2]. The key-feature of these methods is to learn, during search, new clauses corresponding to inconsistent sub-problems. Adding these newly learnt clauses progressively tightens the model and therefore reduces the search space.

However, there is currently no method for resource scheduling that takes full advantage of SAT-based conflict analysis while using dedicated data structures and dedicated algorithms for reasoning about resource and temporal constraints. Indeed, the methods introduced in [3] and [4] require discretizing the time horizon, which is often impractical. On the other hand, the approach used in [5] only learns a very restricted form of clauses and do not use them to backjump.

Satisfiability Modulo Theories (SMTs) is a framework that precisely allows the association of various domain specific algorithms (denoted theories) with a SAT-based search procedure [6].

In this PhD, we propose to study Sat Modulo Theories as framework to solve scheduling problems. The "scheduling theory" will encapsulate known constraint programming methods. A first important venue of research is to develop new filtering algorithms or to improve existing ones for global constraints corresponding to recurring patterns in scheduling problems. See for instance [7] for this type of results on a global filtering procedure for problems with maximum time-lag constraints, or [8] for problems with cumulative resources and non-uniform consumption. A second important problem is to compute "explanations" of inconsistent states, or of domain reductions due to the constraints. Indeed, these explanations are the central element of communication between the theory (constraint programming part) and the Boolean Satisfiability search algorithm. Computing short explanations efficiently is therefore critical to the overall efficiency of the system.

Required skills

Applicants should have an outstanding academic record and a bachelor-level degree in computer science. They should have good programming skills, an interest as well as a good understanding of Combinatorial Optimization, and should be knowledgeable in at least some of the methods that will be investigated: Constraint Programming, Boolean Satisfiability, Integer Programming, and Satisfiability Modulo Theories. Prior knowledge of French is a plus though not mandatory.

Working environment

The student will work on this project in collaboration with Emmanuel Hebrard, Christian Artigues, and Pierre Lopez, and more generally with members of the MOGISA group at LAAS. The scientific activities of the group are focused on scheduling, transportation, discrete optimization, and constraint satisfaction.

This project is in collaboration with Google, however it is not an industrial project. In other words, there are no precise deliverables, and the student is on the contrary encouraged to develop is own original research path. In particular, we aim at balancing theoretical (algorithm design, complexity analysis, etc.) and applied research, the focus will depend on the preferences and skills of the student.

The PhD is partly funded by the "Région Midi-Pyrénées".

Expected starting date for the PhD

October-November 2011

Application process

Please send the following documents to Emmanuel Hebrard (hebrard@laas.fr) straightaway:

  • A detailed curriculum vitae;
  • The results and ranking in the last two years of academic studies;
  • A motivation letter;
  • (optional) Reference letters from at most three referees.

Selected candidates are expected to be interviewed (in the lab or by visioconference).

Bibliography

[1] J. Coelho and M. Vanhoucke. Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers. European Journal of Operational Research, 213(1):73-82, 2011.

[2] A. Horbach. A Boolean satisfiability approach to the resource-constrained project scheduling problem. Annals of Operations Research, 181:89-107, 2010.

[3] N. Tamura, A. Taga, S. Kitagawa, and M. Banbara. Compiling Finite Linear CSP into SAT. In Frédéric Benhamou, editor, Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP-06), pages 590-603, Nantes, France, 2006.

[4] T. Feydy and P. J. Stuckey. Lazy Clause Generation Reengineered. In Ian Gent, editor, Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP- 09), Lecture Notes in Computer Science, pages 352-366, Lisbon, Portugal, September 2009. Springer-Verlag.

[5] D. Grimes, E. Hebrard, and A. Malapert. Closing the Open Shop: Contradicting Conventional Wisdom. In Ian Gent, editor, Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP-09), Lecture Notes in Computer Science, pages 400-408, Lisbon, Portugal, September 2009. Springer-Verlag.

[6] R. Nieuwenhuis, A. Oliveras, and C. Tinelli. 2006. Solving SAT and SAT Modulo Theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). J. ACM 53, 6 (November 2006), 937-977.

[7] C. Artigues, M.-J. Huguet, and P. Lopez. Generalized Disjunctive Constraint Propagation for Solving the Job Shop Problem with Time Lags. Engineering Applications of Artificial Intelligence, 24(2):220-231, 2011.

[8] C. Artigues, P. Lopez, and A. Haït. The energy scheduling problem: Industrial case-study and constraint propagation techniques. International Journal of Production Economics, to appear.

One year postdoc position at LAAS in Toulouse

We are seeking applicants for a one year postdoc position at LAAS in Toulouse on a collaborative project with the Centre National d'Etudes Spatiales (CNES) on scheduling maneuvers and scientific experiments of the Rosetta/Philae spacecraft. Rosetta is a mission of the European Space Agency (ESA) and will involve the first ever landing on a Comet (67P / Churyumov - Gerasimenko). The postdoc will start at the earliest in September 2011, and at the latest in January 2012.

PROJECT

The project is concerned with developing algorithms for scheduling the various activities of the lander (Philae) in three phases. First, in the Separation, Descent and Landing (SDL) phase, the lander will be separated from the orbiter module and will land on the surface of the comet. Second, during the First Science Sequence (FSS), the main scientific experiments will be run using the onboard batteries as energy source. This phase should last three to four days, depending on the load of the batteries and on the quality of the schedule. Finally, during the Long Term Science phase, scientific activities will be resumed at a much slower pace, using the lander's own solar panels to partially reload the batteries.

The experiments of the FSS and LTS -- and to some extent the maneuvers of the SDL -- need to be scheduled to satisfy a number of constraints involving the concurrent use of energy (batteries), and of the main CPUs as well as each instrument's memory. Another important constraint concerns the transfer of data and the notion of "visibility", that is, the availability of the orbiter to act as relay to transmit the data back to earth, which depends on its orbit and on the length of a cometal day. A tool developed using Ilog Scheduler and Solver (MOST) is currently used to model this problem and to generate feasible plans. Every instrument, subsystem and experiment has been modeled with this library, and it is therefore possible to verify solutions with a great degree of confidence of its feasibility. However, the complexity of the problem, in particular during the FSS phase, makes it difficult to find solutions in a reasonable time.

The role of the recruited researcher will be to explore ways of obtaining better solutions quicker, and to develop prototypes to assess the gain. This might be done by improving the model, the propagation algorithms and the search strategies currently employed, or by developing radically new models whose solutions can then be fed back to MOST.

WORKING ENVIRONMENT

The project is expected to be carried out in collaboration with Pierre Lopez, Christian Artigues and Emmanuel Hebrard (MOGISA group), and in constant contact with the SONC team of the CNES.

APPLICATION

We are seeking applicants with an outstanding cv and a thesis related to scheduling and/or combinatorial optimization. A good experience of IBM/Ilog products would be a great plus, however it is not necessary.

Please send the following documents to Emmanuel Hebrard (hebrard@laas.fr) straightaway:

  • A detailed curriculum vitae;
  • A motivation letter;
  • Abstract of the PhD thesis;
  • The three most relevant publications;
  • (optional) Reference letters from at most three referees.

UNIVERSITY OF YORK, Postdoctoral Research Fellow

Application deadline: 29 July 2011

I'm looking for an energetic and creative Postdoctoral Research Fellow to work on a Medical Research Council funded project: "A graphical model approach to pedigree reconstruction using constrained optimisation". This research is at the intersection of constrained optimisation techniques (particularly integer linear programming) and machine learning of Bayesian networks (BNs) within a Bayesian framework. The goal of the project is to learn BN representations of pedigrees ('family trees') from genetic data and prior information. Pedigrees are useful for uncovering genetic factors in disease and more generally for investigating gene-gene and gene-environment interactions.

The project is in collaboration with the Dept of Genetics at the University of Leicester and the Dept of Social Medicine at the University of Bristol. The project will run from 3 October 2011 for 3 years. Salary in the range GBP 35,788 - 44,016

For further details and details of how to apply please go to:
https://www22.i-grasp.com/fe/tpl_YorkUni01.asp?newms=jj&id=45117

For informal enquiries, please email:jc@cs.york.ac.uk

James Cussens
Dept of Computer Science & York Centre for Complex Systems Analysis
University of York
http://www.cs.york.ac.uk/~jc

PhD position on weighted constraint solving in Toulouse/Montpellier, France.

A doctoral (PhD) position in the area of (weighted) constraint solving and optimization is available in the framework of a ANR (french NSF) funded project, including the LIRMM (C. Bessiere), IRIT (MC Cooper), GREYC (S. Loudni) and INRA-BIA (T. Schiex) labs. The PhD will be involved in the development of new algorithms for solving weighted constraint networks (WCSP) and other related graphical models.

Applicants should have (or in the process of getting) a Master degree in Computer Science or related discipline. Experience with software development is desirable.

More information is available at the project web site. The deadline for application is mid July, 2011 but applications will be considered as they come. Informal enquiries should be directed to Thomas Schiex ( http://www.inra.fr/mia/T/schiex ).

PhD position proposal - October 2011 - Adaptive Metaheuristics applied to Multi-objective and Bi-level Transportation Problems

The Dolphin project-team (INRIA Lille-Nord Europe, France) is seeking applications for a full-time PhD studentship on metaheuristics for combinatorial, multi-objective and bi-level optimization, starting in October 2011.

More info and application : http://www.inria.fr/

2 PhD scholarships in Operational Research

Heuristic strategies for structured combinatorial optimisation problems

CODeS KAHO Sint-Lieven, K.U.Leuven

Research group

CODeS -Combinatorial Optimisation and Decision Support- is a research group at the Department of Computer Science, K.U.Leuven (Flanders/Belgium). The group consists of two research labs, one located in Gent, the other one in Kortrijk. CODeS conducts research in modelling and algorithm development for complex scheduling, personnel rostering, vehicle routing, cutting stock and packing problems. The research group intensively cooperates with industry and has access to relevant data taken from practice.

Research project

The project focuses on developing new optimisation approaches to problems that combine characteristics of problems taken from various domains. As is well known, combinatorial optimisation problems which, for example, combine packing and scheduling decisions can be notoriously hard to solve to optimality. We refer to this type of combinatorial optimisation problems as structured. This problem class warrants an integrative approach that exceeds recognised good quality algorithms. State of the art methods have not yielded satisfactory solutions. Indeed, traditional solution approaches for this type of problems use a general purpose heuristic solver, combined with an integer programming formulation. The result is that the optimality gap usually remains unknown. Therefore, in the present research project we will develop heuristic strategies for the class of problems that integrate elements from different combinatorial optimisation problems. The strategies contain 1) a phase where, inspired by Benders decomposition idea, the structure is used to decompose the problem into (known) subproblems; 2) a composition phase in which (existing) solutions to subproblems are integrated towards solving the original problem. Two particular cases will be investigated in the project: the lock scheduling problem (scheduling and packing) and the homecare scheduling problem (routing and rostering). The research will be conducted in full cooperation with ORSTAT, K.U.Leuven.

Practical

PhD Supervision

Candidates should hold a master degree and possess excellent skills in mathematics, computer science and operational research.

Location: CODeSs research premises in Gent, Belgium (Technology Campus KAHO Sint-Lieven)

Application: please provide by 15 July CV and recommendation letters to greet.vandenberghe@kahosl.be

Greet Vanden Berghe
CODeS - KAHO Sint-Lieven
Tel +32 9 265 86 10
greet.vandenberghe@kahosl.be
http://www.kahosl.be

Postdoc position "declarative approaches for interesting pattern mining problems" CRIL - CNRS (UMR 8188)

A postdoc position (12 months) on "declarative approaches for interesting pattern mining problems" is available from the beginning of October 2011 at the CRIL Lab.- UMR 8188 CNRS (Lens, France) in the "Inference and decision process" group (www.cril.fr).

This postdoc is part of the national project DAG (Declarative approaches for enumerating interesting pattern in databases) under the ANR DEFIS 2009 program. This project explores the cross-fertilization between constraints programming, combinatorics, and databases to bring original and modular solutions to pattern mining problems. The partnership consists of 3 research groups: Database group at LIRIS (Lyon), algorithmic group at LIMOS (Clermont-Ferrand) and constraint programming/Satisfiability group at CRIL (Lens). Work will be realized in close cooperation with the partners. Regular visits at LIRIS laboratory (University Claude Bernard, Lyon) will be particularly envisaged. More details on: http://liris.cnrs.fr/dag/

The selected researcher will investigate the following aspects:

  • High-level declarative languages (logical or algebraic) for expressing interesting complex patterns enumeration problems
  • Mining complex patterns using constraint (logic) programming, Satisfiability (modulo theory), Integer Linear programming,...

Applicants must have PhD in computer sciences in one of the following areas:

  • data mining,
  • logic, satisfiability, constraint programming,
  • algorithmic,
  • or theoretical computer science in general.

Applications should include the following materials:

  • a motivation letter
  • a detailed CV (with publication list)
  • two or three references

The position is open from the 1st of October 2011, the funding is available for up to 1 year (at least 2000 euros net monthly salary). The starting date will be extended until a suitable candidate will be found. The position is located at Lens in the north of France within 40mn by train from Lille.

Application material should be sent to Lakhdar Sais (sais [at] cril [dot] fr) and Emmanuel Coquery (emmanuel [dot] coquery [at] univ-lyon1 [dot] fr). The deadline for applications is September 3, 2011. Selected candidates will be interviewed by phone or visio-conference as soon as we receive their applications.

Post-doc announcements, Microsoft-INRIA Joint Lab

Sept. 2011 - Aug. 2013

Two 24-months post-doctoral positions concerned with the application of Machine Learning methods for Search are opened. The positions will be held at the Microsoft-INRIA laboratory at Saclay, (20km south of Paris), France.

Topic

The context of the work is to learn efficient solving strategies on top of existing Constraint-based or Meta-heuristics optimization algorithms.

A key challenge today for Constraint solvers is to be able to reformulate an existing CSP efficiently until the problem becomes obviously solvable or unsolvable. One possible topic of the post-doc will be to turn the reformulation of a given CSP into a reinforcement learning problem: define the state and actions spaces, and investigate the feasibility of learning a good reformulation strategy.

Another possibility is to identify the context of competence of specific heuristics within the search, and to use the gained knowledge to define heuristics selection strategies.

Profile

We are looking for PhD computer scientists with strong knowledge in at least one the following fields: Machine Learning and Data Mining (Reinforcement Learning, Monte-Carlo Tree Search, ...), Constraint Solving (exact and stochastic Optimization, Meta-Heuristics, ...). Strong programming skills are mandatory. A sound experience of existing CSP solvers will be appreciated.

Duration and remuneration

  • 12+12 months contract, starting from September 2011.
  • net salary: around 2100 Euros per month (health insurance included).
How to apply

Please send your application (PDF format) as soon as possible.

Screening of applications starts immediately and continues until the position is filled.

Send cover letter including names of at least two references, CV and links to PhD dissertation (or draft) and up to three most relevant publications to the following emails:

  • youssefh[at]microsoft[dot]com
  • marc[dot]schoenau[at]inria[dot]fr
  • michele[dot]sebag[at]lri[dot]fr

MSc in Computational Intelligence

Computational intelligence is an umbrella term covering advanced artificial intelligence techniques based on nature-inspired problem solving. It deals with the theory, design, application, and development of biologically, socially and linguistically motivated computational paradigms. There is emphasis on genetic algorithms, evolutionary programming, fuzzy systems, neural networks, connectionist systems, and hybrid intelligent systems in which these paradigms are contained.

Our unique MSc Computational Intelligence covers the theoretical, applied and practical aspects of this subject area. You will study the various disciplines of computational intelligence with a particular focus on linking computational intelligence techniques to real world applications and projects, including computational intelligence in business and financial applications, computational intelligence in games, computational intelligence in biological sciences and medicine, computational intelligence in industrial control and natural language engineering and intelligent Web search. Our School of Computer Science and Electronic Engineering is internationally leading within the three main areas of computational intelligence - fuzzy systems, neural networks and evolutionary computation - and recently launched the Computational Intelligence Centre to further our reputation as a world class centre of excellence in this subject. Optional modules from Essex Business School will enable you to broaden your studies.

Graduates of this course will understand the various disciplines of computational intelligence with a particular focus on linking techniques to real-world applications and projects including computational intelligence in business and financial applications, computational intelligence in games, computational intelligence in biological sciences and medicine and computational intelligence in industrial control.

http://www.essex.ac.uk/csee/pg_taught/msccompintelligence/index.aspx

UNIVERSITY OF YORK - Postdoctoral Research Fellow

Application deadline: 29 July 2011

I'm looking for an energetic and creative Postdoctoral Research Fellow to work on a Medical Research Council funded project: "A graphical model approach to pedigree reconstruction using constrained optimisation". This research is at the intersection of constrained optimisation techniques (particularly integer linear programming) and machine learning of Bayesian networks (BNs) within a Bayesian framework. The goal of the project is to learn BN representations of pedigrees ('family trees') from genetic data and prior information. Pedigrees are useful for uncovering genetic factors in disease and more generally for investigating gene-gene and gene-environment interactions.

The project is in collaboration with the Dept of Genetics at the University of Leicester and the Dept of Social Medicine at the University of Bristol. The project will run from 3 October 2011 for 3 years. Salary in the range GBP 35,788 - 44,016

For further details and details of how to apply please go to: https://www22.i-grasp.com/fe/tpl_YorkUni01.asp?newms=jj&id=45117

For informal enquiries, please email: jc@cs.york.ac.uk

A postdoc position on declarative approaches for interesting pattern mining problems

A postdoc position (12 months) on "declarative approaches for interesting pattern mining problems" is available from the beginning of October 2011 at the CRIL Lab.- UMR 8188 CNRS (Lens, France) in the "Inference and decision process" group (www.cril.fr).

This postdoc is part of the national project DAG (Declarative approaches for enumerating interesting pattern in databases) under the ANR DEFIS 2009 program. This project explores the cross-fertilization between constraints programming, combinatorics, and databases to bring original and modular solutions to pattern mining problems. The partnership consists of 3 research groups: Database group at LIRIS (Lyon), algorithmic group at LIMOS (Clermont-Ferrand) and constraint programming/Satisfiability group at CRIL (Lens). Work will be realized in close cooperation with the partners. Regular visits at LIRIS laboratory (University Claude Bernard, Lyon) will be particularly envisaged. More details on: http://liris.cnrs.fr/dag/

The selected researcher will investigate the following aspects:

  • High-level declarative languages (logical or algebraic) for expressing interesting complex patterns enumeration problems
  • Mining complex patterns using constraint (logic) programming, Satisfiability (modulo theory), Integer Linear programming,...

Applicants must have PhD in computer sciences in one of the following areas:

  • data mining,
  • logic, satisfiability, constraint programming,
  • algorithmic,
  • or theoretical computer science in general.

Applications should include the following materials:

  • a motivation letter
  • a detailed CV (with publication list)
  • two or three references

The position is open from the 1st of October 2011, the funding is available for up to 1 year (at least 2000 euros net monthly salary). The starting date will be extended until a suitable candidate will be found. The position is located at Lens in the north of France within 40mn by train from Lille.

Application material should be sent to Lakhdar Sais (sais@cril.fr) and Emmanuel Coquery (emmanuel.coquery@univ-lyon1.fr). The deadline for applications is September 3, 2011. Selected candidates will be interviewed by phone or visio-conference as soon as we receive their applications.

PhD scholarships on Constraints

Title: Tractable classes for extending constraint satisfaction solvers

Laboratory: Laboratoire des Sciences de l'Information et des Systèmes (LSIS) UMR CNRS 6168

Advisors: Philippe Jégou, Cyril Terrioux

Abstract:

The implementation of constraint satisfaction solvers, including SAT solvers for propositional logic (the NP-complete problem of reference), has lead to spectacular results in the last years, proved by their ability to treat industrial instances of huge size. However, the community seems to have reached a plateau that is now difficult to cross.

A significant jump with respect to the current state of the art would likely require the study of two complementary issues:

  • The first one is the study of existing solvers, including CDCL-based systems or systems making use of filtering techniques by propagation and exploiting the topological structure of instances, such as bounded tree-width. A theoretical explanation of their practical efficiency is currently lacking. The point here is to develop a theoretical analysis - based on complexity theory (the parameterized complexity seems to be a relevant notion) in order to provide an explanation of their behavior.
  • The second issue focuses on integrating tractable fragments handled by the current systems, to the aim of discovering new tractable fragments. These new fragments are intended to cover large classes of benchmarks, and at the same time being suitable for efficient implementation (recognizing and solving algorithms must have an almost linear time complexity).

The thesis will deal with the above issues and will comprise both a theoretical investigation and an experimental analysis.

This research will be undertaken within the TUPLES programme, which is funded by the French National Research Agency (ANR) and it associates four laboratories: namely the IRIT (Toulouse with Martin Cooper and Pierre Régnier), the CRIL (Lens with Pierre Marquis, Lakhdar Sais, Daniel Le Berre and Bertrand Mazure), the GREYC (Caen with Bruno Zanuttini) and the LSIS (Marseille). TUPLES is the acronym for Tractability for Understanding and Pushing forward the Limits of Efficient Solvers. The applicant will integrate INCA team at LSIS. The INCA team has been ranked A+ (the best possible ranking) by the French National Agency for Evaluation of Research (AERES).

Keyword: CSP, SAT, complexity, algorithmic, tractable classes, solving systems (solvers).

Location: Paul Cézanne University (Aix-Marseille III), Faculty of Sciences and Techniques, Marseille, France

Funding: the Ph.D. fellowship is funded for 3 years and is monthly funded about €1632,22 before taxes (or €1998,61 before taxes if included missions other than research activities as teaching) under Decree No. 2009-464 of April 23rd 2009 on doctoral contract of public higher education or research.

Candidate Profile: Applicants should have (or in the process of getting) a M.Sc. in Computer Science, Computer Engineering or a closely-related discipline (such as Discrete Mathematics). Strong algorithmic and mathematical skills are required. C++ or C development skills are desirable. Note that the knowledge of French is not required.

Start date: the position starts preferably in September / October 2011.

Application and contacts: Candidates must send their application before July 1st 2011 midnight, including:

  • CV (at most 3 pages)
  • Results and ranking for the M.Sc. (join a copy of marks)
  • a motivation letter,
  • reference letters.

Send your applications by email with attached pdf files to: philippe.jegou@univ-cezanne.fr and cyril.terrioux@univ-cezanne.fr

One year postdoc position at LAAS in Toulouse

We are seeking applicants for a one year postdoc position at LAAS in Toulouse on a collaborative project with the Centre National d'Etudes Spatiales (CNES) on scheduling maneuvers and scientific experiments of the Rosetta/Philae spacecraft. Rosetta is a mission of the European Space Agency (ESA) and will involve the first ever landing on a Comet (67P / Churyumov - Gerasimenko) http://sci.esa.int/science-e/www/area/index.cfm?fareaid=13. The postdoc will start at the earliest in September 2011, and at the latest in January 2012.

PROJECT

The project is concerned with developing algorithms for scheduling the various activities of the lander (Philae) in three phases. First, in the Separation, Descent and Landing (SDL) phase, the lander will be separated from the orbiter module and will land on the surface of the comet. Second, during the First Science Sequence (FSS), the main scientific experiments will be run using the onboard batteries as energy source. This phase should last three to four days, depending on the load of the batteries and on the quality of the schedule. Finally, during the Long Term Science phase, scientific activities will be resumed at a much slower pace, using the lander's own solar panels to partially reload the batteries.

The experiments of the FSS and LTS -- and to some extent the maneuvers of the SDL -- need to be scheduled to satisfy a number of constraints involving the concurrent use of energy (batteries), and of the main CPUs as well as each instrument's memory. Another important constraint concerns the transfer of data and the notion of "visibility", that is, the availability of the orbiter to act as relay to transmit the data back to earth, which depends on its orbit and on the length of a cometal day. A tool developed using Ilog Scheduler and Solver (MOST) is currently used to model this problem and to generate feasible plans. Every instrument, subsystem and experiment has been modeled with this library, and it is therefore possible to verify solutions with a great degree of confidence of its feasibility. However, the complexity of the problem, in particular during the FSS phase, makes it difficult to find solutions in a reasonable time.

The role of the recruited researcher will be to explore ways of obtaining better solutions quicker, and to develop prototypes to assess the gain. This might be done by improving the model, the propagation algorithms and the search strategies currently employed, or by developing radically new models whose solutions can then be fed back to MOST.

WORKING ENVIRONMENT

The project is expected to be carried out in collaboration with Pierre Lopez, Christian Artigues and Emmanuel Hebrard (MOGISA group: http://www.laas.fr/MOGISA-EN/), and in constant contact with the SONC team (http://smsc.cnes.fr/ROSETTA/GP_contacts.htm) of the CNES.

APPLICATION

We are seeking applicants with an outstanding cv and a thesis related to scheduling and/or combinatorial optimization. A good experience of IBM/Ilog products would be a great plus, however it is not necessary.

Please send the following documents to Emmanuel Hebrard (hebrard@laas.fr) straightaway:

  • A detailed curriculum vitae;
  • A motivation letter;
  • Abstract of the PhD thesis;
  • The three most relevant publications;
  • (optional) Reference letters from at most three referees.

PhD grant from Microsoft Research, for GREYC (Caen, France)

Subject : Multi-Stage Constraint Programming.

Constraint solving is a set of techniques for solving combinatorial and optimization problems. In this thesis, we propose to study an extension called Quantified Constraint Programming (QCSP), which is an extension of constraint programming in which some of the variables are universally quantified. For example, the formula exists x in {1, 2, 3}, forall y in {3, 4}, exists z in {4, 5, 6} . x < y and x+y = z and z ? 3x defines a quantified constraint program. The most intuitive way of entering the new scenario is by thinking of it as a game between two players. One player is associated to the existential quantifier, the other is related to the universal quantifier. The goal of the existential player is to satisfy each constraint, hence to satisfy the whole CSP. The goal of the universal player is to violate at least one constraint, thus overcoming the opponent's effort. The two players play against each other in turn, for a finite and fixed number of rounds. The solution of such a problem is a tree called strategy and assigns a value for each existential variable in function of its preceding universal ones. Finding a strategy is a complex problem since QCSP have been proven to be Pspace-complete. The purpose of this thesis is to leverage QCSP techniques in order to build an environment to solve efficiently multi-stage optimization problems.

The candidate should have an outstanding degree in computer science, a solid background in artificial intelligence and algorithms. A first experience in research and/or in constraint programming is highly recommended. In addition, strong coding skills in C++ are required. Prior knowledge of french is not mandatory.

Applicants should submit in a zip file their CV, copy of their university degrees, a list of publications if any, a cover letter and the name of three referees by email to Arnaud Lallouet, arnaud.lallouet@unicaen.fr, http://users.info.unicaen.fr/~alalloue/. Selected candidates are expected to come for an interview in the lab or by visio-conference. Interviews will continue until a suitable candidate has been found.

Post-doc positions at Microsoft-INRIA Joint Lab., Saclay, France Sept. 2011 - Aug. 2013

Two 24-months post-doctoral positions concerned with the application of Machine Learning methods to Search and Optimization are opened. The positions will be held at the Microsoft-INRIA joint laboratory at Saclay, (20km south of Paris), France.

Topic

The context of the work is to learn efficient solving strategies on top of existing Constraint-based or Meta-heuristics optimization algorithms.

A key challenge today for Constraint solvers is to be able to reformulate an existing CSP efficiently until the problem becomes obviously solvable or unsolvable. One possible topic of the post-doc will be to turn the reformulation of a given CSP into a reinforcement learning problem: define the state and actions spaces, and investigate the feasibility of learning a good reformulation strategy.

Another possible research direction is to identify the context of competence of specific heuristics within the search, and to use the gained knowledge to define heuristics selection strategies.

Profile

We are looking for PhD computer scientists with strong knowledge in at least one the following fields: Machine Learning and Data Mining (Reinforcement Learning, Monte-Carlo Tree Search, ...), Constraint Solving (exact and stochastic Optimization, Meta-Heuristics, ...). Strong programming skills are mandatory. A sound experience of existing CSP solvers will be appreciated.

Duration and remuneration
  • 12+12 months contract, starting from September 2011.
  • net salary: approx. 2100 Euros per month (health insurance included).
Application

Please send your application (PDF format) as soon as possible. Screening of applications starts immediately and continues until the position is filled.

Send cover letter including names of at least two references, CV and links to PhD dissertation (or draft) and up to three most relevant publications to the following emails:
youssefh[at]microsoft[dot]com
marc[dot]schoenauer[at]inria[dot]fr
michele[dot]sebag[at]lri[dot]fr

Candidates for PhD proposal

We are looking for candidates for the following PhD proposal. Please contact us urgently (contact me directly).

Title: Hybrid Global Constraints (and applications in autonomous robotics)

Remark: Background in robotics not mandatory.

Abstract:

The goal of this thesis is to define and make operationnal a new class of constraints that play a key role in an upgrowing area of artificial intelligence: autonomous robotics. The constraints under interest are bottle-necks for the self-localization based on observations of an (a priori) unknown environment.

These constraints are called "global" constraints because they have a high-level semantics (interpretation) that allow a much more efficient processing than resorting to a simple logical and algebraic decomposition. They are also hybrid because they involve both discrete variables (typically, status of objects) and continuous variables (their physical states).

See for examples works:

There are three challenges in one: enrich the constraint programming formalism, create a new branch at the interface of discrete and continuous communities and address a strongly innovative application field.

Keywords: global constraints, continuous constraints, autonomous robotics

Sincerly,
Gilles Chabert & Nicolas Beldiceanu
Task Team - Mines de Nantes - LINA INRIA CNRS UMR 6241