| During the technical program |
|---|
|
Preference Representation and Constrained Optimization with CP-Nets. Ronen Brafman, Carmel Domshlak
|
|
Randomized Backtrack Search Methods:
Extending the reach of complete backtrack search.
Carla P. Gomes
|
|
Dynamic Constraint Solving.
Gérard Verfaillie, Narendra Jussien
|
|
Configuration as a challenging application for CP technology.
Daniel Mailharro, Ulrich Junker
|
Preference Representation and Constrained Optimization with CP-Nets.Constraints Programming provides an attractive formalism for specifying and solving many real-world problems. However, in many contexts, simply outputing some feasible solution is not an acceptible approach. Rather, the user has preferences (either implicit or explicit) over the feasible solutions or the feasible relaxations of the problem. In the CSP community, this problem has been addressed mostly using the formalism of soft-constraints. An alternative approach that has been gaining momentum in recent years is the decoupled constrained optimization approach based on CP-networks, which is particularly suitable for configuration problems in which we have a set of fixed hard constraints, posed by the producer, together with a unique combination of hard constraints and preferences posed by each consumer.Work on CP-networks concentrates on providing an intuitive graphical tool for eliciting preference information from users -- a notorious bottleneck for decision support systems -- together with matching algorithms for constrained optimization. CP-networks are an attractive formalism because they are based on a small set of preference statements that people can easily understand and express. We have a good understanding of some of their computational properties, and how they be combined with constraints in a process of constrained optimization. On the other hand, CP-networks are a relatively new development, and they open up an interesting direction for promising new research. The tutorial will begin with some background on preference representation and a general overview of the corresponding research in AI, economics, and philosophical logic. We will then consider the soft-constraints approach for constrained optimization. The central part of the tutorial will present and discuss the CP-nets and TCP-nets models. These models represent qualitative preference statements under a ceteris paribus (all else being equal) assumption, such as: "Among flights leaving two days before the conference I prefer an evening flight, but among flights leaving a day before the conference I prefer a morning flight", or "On a KLM day flight, it is more important to me to have an intermediate stop in Amsterdam than to fly in business class". In this part of the tutorial we introduce the relevant models and discuss their computational properties. In particular, we consider the problem of preferential, constraint-based optimization which is central to important applications such as product configuration. This tutorial is suitable for a general CS/AI audience. It is intended to introduce non-specialists to an AI area of emerging importance. It should be of interest to researchers and practitioners working in areas such as product configuration, soft constraints, constrained optimization, user modeling, automated decision making. |
Randomized Backtrack Search Methods: Extending the reach of complete backtrack search.Randomized search methods have greatly extended our ability to solve hard computational problems. In general, however, we think of randomization in the context of local search. While local search methods have proven to be very powerful, in some situations they cannot supplant complete or exact methods due to their inherent limitation: local search methods cannot prove inconsistency or optimality. In recent years, we have seen the emergency of an active research area focusing on the study and design of complete randomized search procedures.In this tutorial I will provide an overview of the state-of-the-art of randomized approaches to complete backtrack search methods. I will introduce the ideas and concepts underlying such randomized procedures. In particular I will describe a new generation of backtrack style methods that exploit randomization, while guaranteeing completeness. The run time distributions of such methods quite often exhibit heavy and fat tails. Heavy tailed distributions are non-standard distributions that have infinite moments (e.g., infinite mean or variance, etc. Such non-standard distributions have been observed in areas as diverse as economics, statistical physics, and geophysics. The understanding of the heavy and fat-tailedness of complete backtrack search methods has led to the design of more efficient procedures. In particular, I will present different ways of randomizing complete backtrack style methods and show how restart and portfolio strategies can increase performance and robustness of such methods. I also provide formal models of heavy-tailed behavior in combinatorial search and results on performance guarantees for restart strategies. |
Dynamic Constraint Solving.The objective of this tutorial is to present, mainly for people who are new in the area of Constraint Programming and Constraint Solving, why it is often necessary to consider constraint solving in a dynamic context, what are the main requirements that appear in such a context, and what are the main techniques that have been proposed so far to meet these requirements.The tutorial will involve five parts:
|
Configuration as a challenging application for CP technology.Today, the number, the diversity and the complexity of configurable products available on the market is growing, expanding from conventional equipment configuration to software configuration, or to service configuration, such as loans, insurance, mobile phone packages, travel packages, and so forth.Configuration is more than ever a challenging area for applying novel Constraint Programming techniques since more and more sophisticated reasoning tasks are delegated to the configurator software; the software must thus integrate product-assembly knowledge along with customer classification, adaptive sales strategies, and customer assistance. This integration becomes particularly critical for e-business applications where customers directly configure products through the Web with no human assistance and without a deep knowledge of the products they are buying. Classical CSP provides a powerful knowledge representation and problem solving framework but it must be extended to answer the particularities of the configuration tasks such as taxonomic and partonomic reasoning, generative process, interactivity, preference solving and scalability. This tutorial is an opportunity to understand what are configuration problems, why and how constraint programming technology can be extended in order to capture these particularities. |
Tutorial Chair: Christian Bessiere (bessiere@lirmm.fr )