CP 2003: Invited Lecture Programme

The list of invited lectures is given below. The times at which these lectures will be delivered can be found here.

• Languages versus Packages for Constraint Problem Solving

  Mark Wallace
  IC PARC

  One strand of CP research seeks to design a small set of primitives and operators that can be used to build an appropriate algorithm for solving any given combinatorial problem. The aim is to "package" CP, simplifying its use, in contrast to current systems which offer application developers a full constraint programming language. In this talk we examine the risks of this line of research, and argue that our field is still too immature to be ready for "packaging".

• Constraint Patterns

  Toby Walsh
  4C

  Many patterns occur in constraint programs. In this talk, I will argue that we need to identify, formalize and document these patterns in a similar way to the patterns identified by the software engineering community. The result will be a systematic and comprehensive methodology for modelling an informal problem. Such a methodology will permit us to tackle the modelling "bottleneck" that hinders the uptake of constraint programming. This is an ambitious project - modelling is not a problem which lends itself to a piecemeal approach as even the smallest modelling decision can have far reaching consequences. However, we have made some progress and I will describe some of the more interesting constraint patterns which have already been identified. I will also discuss the different ways that we can exploit such patterns (for example, by extending the constraint language).

• Automated Mechanism Design: A New Application Area for Search Algorithms

  Tuomas Sandholm
  Carnegie-Mellon

  Mechanism design is the art of designing the rules of the game (aka. mechanism) so that a desirable outcome (according to a given objective) is reached despite the fact that each agent acts in his own self-interest. Examples include the design of auctions, voting protocols, and divorce settlement procedures. Mechanisms have traditionally been designed manually for classes of problems. In 2002, Conitzer and Sandholm introduced the automated mechanism design approach, where the mechanism is computationally created for the specific problem instance at hand. This approach has several advantages:

  1. it can yield better mechanisms than the ones known to date,
  2. it applies beyond the problem classes studied manually to date,
  3. it can circumvent seminal economic impossibility results, and
  4. it shifts the burden of design from man to machine.
  In this write-up I overview the approach, focusing on problem representations, computational complexity, and initial applications. I also lay out an agenda for future research in this area.

• Planning and Learning with SAT: Why it Works When it Works

  Henry Kautz
  University of Washington

  The techniques of clause learning and randomize restarts have proven to be surprisingly effective in improving the performance of the DPLL procedure on SAT encodings of state-space reachability problems, such as occur in planning and verification. I will show how recent work on proof complexity can illuminate both the potential power and fundamental limitations of the techniques.