Events
Invited Talks
-
Constraint-based
Schedulers, do they really work?
by Philippe
Baptiste, Ecole Polytechnique, CNRS LIX (see bio) Tuesday, 22
September, 9:00
-
Challenges for Constraint Reasoning and
Optimization in Computational
Sustainability
by Carla Gomes, Cornell
University Monday, 21 September, 10:00
-
Observations on Symmetry
Breaking
by Barbara Smith,
University of Leeds Thursday, 24 September, 9:00
Tutorials
-
Exploiting Fixed-Parameter Tractability in
Satisfiability and Constraint Satisfaction
by Barry
O'Sullivan and Igor Razgon Monday, 21 September,
14:00
Many problems we attempt to solve
using satisfiability or constraint programming techniques are
NP-Complete or harder. The field of parameterised complexity
provides an orthogonal view to classical complexity theory. It
attempts to deal with NP-Hardness by identifying problems whose
exponential worst-case behaviour is, in fact, only polynomially
dependent on the size of the problem n, but exponentially
dependent on a parameter k, independent of n. Ideally we wish to
identify fixed-parameter algorithms for solving such problems
that rely on parameters that tend to be small in
practice.
The field of parameterised complexity has many
similarities with the areas of satisfiability and constraint
solving from both the conceptual point of view as well as
through its results. The methodologies of reformulation and
preprocessing in parameterized complexity are very similar to
what we understand as reformulation and preprocessing in
constraint programming.
In this tutorial we will: provide an
overview of the field; survey the work that has been done in the
area of parameterised complexity for satisfiability and
constraint solving; and present an in-depth analysis of one
challenging open problem that was recently resolved by the
tutorialists that is of interest in satisfiability and
constraint optimization.
-
Soft
Global Constraints
by Willem-Jan van Hoeve Tuesday,
22 September, 14:00
Some 10 years ago, the first soft
global constraints appeared that could be applied to model and
solve over-constrained problems. Since then, efficient domain
filtering algorithms for several soft global constraints have
appeared, including the soft alldifferent constraint, the soft
global cardinality constraint, the soft regular constraint, the
soft cumulative constraint, and many others. In this tutorial we
will outline the basic concepts of soft global constraints,
discuss various violation measures on which soft global
constraints can be based, and describe in detail domain
filtering algorithms for some soft global constraints such as
the soft alldifferent constraint.
-
Amortized and Expected Case Analysis of
Constraint Propagation Algorithms
by Chris Jefferson,
Meinolf Sellmann Wednesday, 23 September, 14:00
Filtering problems, as they arise within a constraint
propagation engine, often change only marginally between
subsequent calls to a filtering algorithm. Consequently,
traditional one-time invocation, worst-case complexity analysis
is of limited value. In practice, we rely on incremental
filtering algorithms which work well on average. This tutorial
is meant to provide an overview of the most common techniques
when analyzing incremental filtering algorithms in a more
detailed and practically relevant way. In particular, our
objective is to demonstrate the use of amortized runtime
analyses and to discuss ways to make theoretical claims in
regard to the expected-case performance of filtering algorithms
rather than their worst-case complexity only.
Doctoral Program
As part of CP'2009, PhD students are
invited to apply for the Doctoral Program. This program provides an
opportunity for current PhD students to meet each other as well as
researchers in the field. Participants will also present their work
via both a poster and a talk. Participation in the Doctoral Program
will involve:
-
Talks from researchers in the field
about career opportunities
-
Presentation of talks and
posters
-
Discussions with a mentor with
similar research interests
The program is open to all PhD students
involved in Constraint Programming or related fields at any
level.
Details of the Doctoral Programme and
how to apply can be found here
.
There are funds available to support
students by providing accomodation and free conference
registration.
The Doctoral Program Chairs are Karen
Petrie and Olivia Smith
Workshops
Sunday, 20 September
Faculty of Economics
Social Events
Opening
Reception
Towh
Hall (©José Barbosa)
There will be a reception with
Port wine in the Town Hall, on Monday, September 21, at around 7pm.
After the reception the participants may go to Bairro
Alto, a nearby "bohemian" area
with lots of restaurants and have dinner there. (Locate it in CP'09
map
.)
Guided Tour and
Conference Dinner
25 de Abril
Bridge and Cristo-Rei
monument (© Pedro Hipólito)
On Wednesday, September 23, there will
be 1 hour guided tours for groups of about 30 people to Museu Nacional de Arte
Antiga (Ancient Art National Museum) starting at 18:00,
expectedly. (see map,
and English site (goLISBON) about the Museum here)
Afterwards, by 19:30 we meet at the Real
Jardim Botânico da Ajuda (botanical garden) for a nice promenade
and drink, followed by a banquet at its restaurant, Estufa Real.
(Locate
these sites in CP'09
map.)
|
