Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms, and Complexity

Challenges in Automated Configuration

Flexibility and efficiency in the customization of products and services - rather than series production - has become a key factor of competitiveness in the post-industrial economy. This flexibility is made possible through the use of so-called configurators, that is, software packages that automatically construct feasible configurations of components meeting a given set of requirements and preferences. Automated configuration can be seen as one of the major success stories of applied artificial intelligence methods and of constraint satisfaction techniques, in particular.

Developing such a product configuration system is a challenging task in many ways. Product configuration tools should be designed to encode the complex knowledge from domain experts, such as the characteristics of the different components involved in the customization and the restriction on how these components can be combined with each other. However, this might be very difficult in general, because customization is a generative process, where both the number of the involved components and the types of components themselves may be unknown at the beginning.

The second challenge in building automatic configurators concerns the efficiency of the algorithms supporting the customization. In fact, product configuration in real scenarios is likely to involve a large number of components and hundreds of associated variables, whose alues have to be dynamically determined based on the customer's needs. For instance, telephone switching systems often consisting of several hundreds of racks, thousands of frames, and dozens of thousands modules. Given the huge size of the problems to be treated, a major requirement is to develop and integrate efficient algorithms for building the configuration that best matches with the customer's desires or the technological requirements.

The Research Agenda

In order to achieve significant progress, we will first study existing approaches and compare them formally and request feedback from the industrial advisory board. We propose to investigate a formalism suited to the cope with the above mentioned challenges, called the extensible constraint satisfaction problem (ECSP). We will study the expressive power and the complexity of decision and computational problems related to this formalism. We also propose to investigate the complexity issues in the presence of value-generating constraints, which is a well-known type of constraints used in database theory, but has not been investigated in the context of CSPs so far. Once the framework for extensible CSPs has been layed out, our plan is to investigate decomposition techniques, to find tractable subclasses of ECSPs. Finally, we will implement and test a configurator system, based on our framework, and using our decomposition algorithms.

The project is organised into four main work packages. WP1 systematically studies the relevant problems to configuration, both by formally comparing existing approaches in the literature and by receiving feedback from the industrial advisory board. WP2 focuses on the extensible constraint satisfaction problems (ECSPs). Particular focus will be given to complexity analysis of the relevant decision and computational problems. WP3 consists of a comprehensive study of decomposition methods suitable to ECSPs to identify tractable subclasses. In WP4, we will implement and test a proof-of-concept configuration system, based on ECSP and on the decomposition methods developed in WP3.

Milestones

A formal comparison of existing configuration formalisms was presented in the doctoral program of CP'10, while our work on structural problem decomposition methods and parameterized complexity has resulted in publications at ICALP'09, MFCS'10, STACS'11, and SAT'12 as well as in the Journal of the ACM. Our work on a new configuration formalism has been presented at LoCoCo'11 and ECAI'12. We have also been working on the Partner Units Problem, a specific hard industrial configuration problem, resulting in papers at CPAIOR'11, IJCAI'11 and ICTAI'12. Next in the course of the project a longstanding open problem concerning the effect of compilation on the tractability of CSP has been settled (best paper award at CP'11/accepted for the AIJ). Finally, our efforts in a joint initiative to unify software and product configuration are witnessed by a ConfWS'12 paper.

 

Events

On February 26th/27th 2013 Siemens Austria in Vienna have hosted a joint workshop on our project and the RECONCILE project run by the university of Klagenfurt. The agenda of this event may be found here.

On January 12th/13th 2012 we have run the Oxford Configuration Workshop, bringing together researchers and practitioners from academia and industry.

On December 15/16th 2010 we have run a small-scale precursor event, the programme of which may be found here.