Constraint programming is an area of Artificial Intelligence which has many applications. This thesis applies its techniques to a new kind of problem - the rendering of online retailer websites.
First, in-depth introductions to constraint programming and the problem of
rendering a shop website will be given. A prototypical implementation of a
constraint problem solver and a system to solve and illustrate the problem will
be described.
The architecture of the prototypical implementation and specific features, algorithms, and design decisions will be detailed, analysed, and illustrated. An overview of related work both in the fields of constraint programming and website generation will be presented and existing technologies evaluated.
Features and concepts unique to this thesis, like real-time constraint satisfaction, will be introduced and discussed.
Finally, a comprehensive example will illustrate the problem, means of modelling it, and possible solutions. An outlook to future work and a summary conclude the
thesis.
Constraint Programming ist ein Teilgebiet der künstlichen Intelligenz mit vielen praktischen Anwendungen. Diese Diplomarbeit wendet die Techniken auf eine neue Art von Problem an - das Rendern von Webseiten von Internetshops.
Zuerst wird eine detaillierte Einführung zu Constraint Programming und dem Problem die Webseite eines Online-Shops zu rendern gegeben werden. Eine Beispielimplementierung eines Constraint Problem Solvers und eines Systems um das Problem zu lösen und illustrieren werden beschrieben werden.
Die Architektur der Beispielimplementierung und spezielle Eigenschaften, Algorithmen und Implementierungsentscheidungen werden genau beschrieben, analysiert und illustriert werden. Ein Überblick von ähnlichen Arbeiten sowohl im Bereich des Constraint Programming als auch im Bereich des Generierens von Webseiten wird dargestellt und vorhandene Technologien bewertet werden.
Besonderheiten und Konzepte, die in dieser Diplomarbeit erarbeitet wurden, wie Echtzeit-Constraint Satisfaction, werden eingeführt und diskutiert werden.
Schließlich wird ein ausführliches Beispiel das Problem, Arten der Modellierung und mögliche Lösungen veranschaulichen. Ein Ausblick auf zukünftige Forschung und eine Zusammenfassung beschließen diese Diplomarbeit.
Contents
Introduction
Motivation
Aim and Scope
Related Work
I Modelling of the Problem
1 Description of the Problem
1.1 Personalised Content
1.2 Generating Personalised Content
1.3 Constraints to consider
2 Constraints
2.1 Introduction
2.2 Constraint Satisfaction Problems
2.3 Solution Process
2.3.1 Arc Consistency
2.4 Constrained Optimisation Problems
2.4.1 Extended Constrained Optimisation Problems
2.5 Soft Constraints
2.6 Real-time Constraint Satisfaction
2.6.1 Analysis of the Function ψ
3 Constraint Problem Model
3.1 Slots and Campaigns
3.2 Values of Campaigns
3.3 Values of Slots
3.3.1 Example
3.4 Relaxation of Constraints
3.5 Duplicate Content
3.5.1 Example
3.6 Forced Promotions
3.6.1 Example
3.7 Real-time Problem Solution
II Prototypical Implementation
4 Overview
4.1 System Architecture
4.1.1 Distributed Approach
4.1.2 Web Interface
4.1.3 Web Service
4.2 Implementation Language
4.2.1 Documentation
4.2.2 Testing
4.2.3 Packaging
4.3 Version Control System
4.4 Test Machine Setup
5 Constraint Problem Solver Library
5.1 Overview of existing Constraint Problem Solvers .
5.2 Architecture
5.2.1 Domain
5.2.2 Variable
5.2.3 AbstractConstraint
5.2.4 BinaryConstraint
5.2.5 BinaryRelation
5.2.6 AllDi erentConstraint
5.2.7 TupleConstraint
5.2.8 OneOfEqualsConstraint
5.2.9 ConstraintList
5.2.10 Problem
5.2.11 Solution
5.2.12 ConstraintSolver
5.2.13 Ruby Extensions
5.3 Constraint Problem Solution
5.3.1 Solution Process
5.3.2 Modi cations for Soft Constraints
5.3.3 Constraint Satisfaction with Time Limit
5.3.4 Variable and Value Ordering
5.4 Constraint Revision
5.4.1 Binary Constraints
5.4.2 All Di erent Constraints
5.4.3 Tuple Constraints
5.4.4 One-of-equals Constraint
5.5 Tests and Package Management
5.6 Limitations
6 Constraint Problem Solver SOAP Wrapper
6.1 Architecture
6.1.1 Library Script
6.1.2 WSDL
6.1.3 Control Scripts
6.2 Tests and Package Management
6.3 Limitations
6.4 Use of the Interface
7 Web User Interface
7.1 Architecture
7.1.1 Data Model
7.1.2 Controller
7.1.3 View
7.2 Interface to Amazon.com
7.3 Tests and Package Management
7.4 Full Example
8 Summary
8.1 Future Work
8.1.1 Constraint Model
8.1.2 Constraint Solver
8.2 Conclusion
III Appendix
A Performance Evaluation of Consistency Algorithms
A.1 Binary Constraints
A.1.1 Methodology
A.1.2 Results
A.2 All Di erent Constraints
A.2.1 Methodology
A.2.2 Results
A.3 The Di erence All Di erent makes
B E ectiveness of Real-time Constraint Satisfaction
B.1 Methodology
B.2 Results
B.2.1 Time Limit after rst Solution
B.2.2 Time Limit before rst Solution
C Installation Instructions and Software Versions
C.1 General
C.2 Constraint Problem Solver Library
C.3 Constraint Problem Solver SOAP Wrapper
C.4 Web User Interface
Glossary
Bibliography
Abstract
Constraint programming is an area of Arti cial Intelligence which has many applications. This thesis applies its techniques to a new kind of problem the rendering of online retailer websites.
First, in-depth introductions to constraint programming and the problem of ren- dering a shop website will be given. A prototypical implementation of a constraint problem solver and a system to solve and illustrate the problem will be described.
The architecture of the prototypical implementation and speci c features, algorithms, and design decisions will be detailed, analysed, and illustrated. An overview of related work both in the elds of constraint programming and website generation will be presented and existing technologies evaluated.
Features and concepts unique to this thesis, like real-time constraint satisfaction, will be introduced and discussed.
Finally, a comprehensive example will illustrate the problem, means of modelling it, and possible solutions. An outlook to future work and a summary conclude the thesis.
Zusammenfassung
Constraint Programming ist ein Teilgebiet der künstlichen Intelligenz mit vielen praktischen Anwendungen. Diese Diplomarbeit wendet die Techniken auf eine neue Art von Problem an das Rendern von Webseiten von Internetshops.
Zuerst wird eine detaillierte Einführung zu Constraint Programming und dem Problem die Webseite eines Online-Shops zu rendern gegeben werden. Eine Beispielimplementierung eines Constraint Problem Solvers und eines Systems um das Problem zu lösen und illustrieren werden beschrieben werden.
Die Architektur der Beispielimplementierung und spezielle Eigenschaften, Algorithmen und Implementierungsentscheidungen werden genau beschrieben, analysiert und illustriert werden. Ein Überblick von ähnlichen Arbeiten sowohl im Bereich des Constraint Programming als auch im Bereich des Generierens von Webseiten wird dargestellt und vorhandene Technologien bewertet werden.
Besonderheiten und Konzepte, die in dieser Diplomarbeit erarbeitet wurden, wie Echtzeit-Constraint Satisfaction, werden eingeführt und diskutiert werden. Schlieÿlich wird ein ausführliches Beispiel das Problem, Arten der Modellierung und mögliche Lösungen veranschaulichen. Ein Ausblick auf zukünftige Forschung und eine Zusammenfassung beschlieÿen diese Diplomarbeit.
Acknowledgements
I would like to thank Prof. Dr. Gerhard Brewka for supervising this thesis and providing me with valuable feedback. Many thanks also go to Matthew Round and Karl McCabe of Amazon.com for reviewing the description of the problem of rendering a website.
List of Figures
1 Non-personalised Website
2 Personalised Website
3 Possible Solution for the N-Queens Problem for n = 4
4 Constraint Network Graph for the 4-Queens Problem
5 Example Search Tree built during the Solving of the 4-Queens Problem
6 Solution Process for the 4-Queens Problem with Constraint Propagation
7 Search Tree built during the Solving of the 4-Queens Problem with Pruning
8 Example Orders for the Steel Mill Slab Problem
9 Solution to the Steel Mill Slab Problem in Figure 8
10 Example Soft Constraint Network Graph for an inconsistent Problem
11 Example Curve of ψ with tl = 1, T = 1, and a = 100 · tl = 100
12 Constraint Network Graph for Example 3.3.1
13 System Architecture of prototypical Implementation
14 Structure of the Constraint Solver Library
15 Actions performed during the Solving of a Constraint Problem
16 High-Level Actions performed while solving a Soft Constraint Problem
17 Solving of a Constraint Problem with Time Limit
18 Architecture of SOAP Server
19 Entity-Relationship Diagram [Che76] of the Data Model of the Web User Interface
20 Form to specify Problem to solve
21 Result Page with rendered Solution for Input in Figure 20
22 Activity Diagram for the Web User Interface
23 Binary Constraint Performance for Solution of pathological Problems
24 Binary Constraint Performance for Solution of Identity Problems
25 Binary Constraint Performance for Solution of Ordering Problems
26 All Di erent Performance for Solution of dense Problems
27 All Di erent Performance for Solution of random Problems
28 All Di erent Performance for Solution of pathological Problems
29 All Di erent and Binary Constraint Consistency Performance for So- lution of pathological Problems
30 Deviation from the Time Limit after a Solution has been found for all di erent Problems with hard Constraints
31 Deviation from the Time Limit after a Solution has been found for all di erent Problems with soft Constraints
32 Deviation from the Time Limit after a Solution has been found for Identity Problems with hard Constraints
33 Deviation from the Time Limit after a Solution has been found for Identity Problems with soft Constraints
34 Deviation from the Time Limits before a Solution has been found for all di erent Problems with hard Constraints
35 Deviation from the Time Limits before a Solution has been found for all di erent Problems with soft Constraints
36 Deviation from the Time Limits before a Solution has been found for Identity Problems with hard Constraints
37 Deviation from the Time Limits before a Solution has been found for Identity Problems with soft Constraints
List of Tables
1 Overview of Arc Consistency Algorithms for Binary Constraints
2 Overview of Consistency Algorithms for the All Di erent Constraint
3 XML based Web Service Protocols considered for the Web Service
4 Overview of Constraint Problem Solvers
List of Definitions
1 Constraint Satisfaction Problem
2 Constraint
3 Partial Assignment
4 Complete Assignment
5 Solution to a Constraint Satisfaction Problem
6 Problem Class
7 Problem Instance
8 Constraint Network
9 Search Tree
10 Constraint Propagation
11 Consistency Properties
12 Local Consistency
13 Support
14 Pruning
15 Constraint Revision
16 Global Consistency
17 Constrained Optimisation Problem
18 Solution to a Constrained Optimisation Problem
19 Optimal Solution to a Constrained Optimisation Problem . .
20 Extended Constrained Optimisation Problem
21 Solution to an Extended Constrained Optimisation Problem
22 Soft Constraint
23 Valuation Structure
24 Soft Constraint Network
25 Soft Constraint Problem
26 Solution to a Soft Constraint Problem
27 Constraint Satisfaction Time
28 Real-time Constraint Problem
29 Solution to a Real-time Constraint Problem
30 Campaign
31 Slot
32 Page
33 Problem of Rendering a Page
34 Value of a Page
35 Problem of Rendering a Page with Page Value
36 Value of a Page
37 Relaxed Constraint
38 Problem of Rendering a Page with relaxed Constraints
39 Value of a relaxed Page
40 Places in Slots
41 Allowed Tuples for a Slot - Place Pair Constraint
42 Problem of Rendering a Page with Time Limit
Introduction
In today's fast-moving society, electronic commerce environments become increas- ingly popular. The websites of large online retailers serve a vast number of customers who prefer shopping online from the comfort of their home to traditional shopping. Every second, thousands of transactions are handled, putting an enormous load on the backend systems.
At the same time, the requirements increase even further. Stores with personalised pages for every individual customer and targeted recommendations prove valuable for both retailers and customers. Supplying these personalisations does not only demand more from the backend systems, but also from the designers and programmers of websites. They have to take more and more factors into account and handle increasing complexity of the systems and their interaction.
The problem of generating personalised stores is a problem of combining website components such that a number of constraints are satis ed and the value for the retailer and customer is maximised. There are a lot of constraints to take into account and variables to consider. Has the customer visited the store previously, maybe bought something? Is the content reasonably varied? Has the content been generated within reasonable time?
There are established methods for solving problems which involve constraints in the eld of Arti cial Intelligence. These algorithms can be applied to any problem which is modelled appropriately, and separate the problem from the process of solving it. Additional variables, such as the maximisation of a value of usefulness , can be taken into account. Most of the algorithms have been optimised such that they are able to solve even large problems in acceptable time.
The problem remains to model the generation of a website with constraints such that it can be solved e ectively and e ciently. Most processes cannot directly be expressed as constraints. Global state cannot easily be expressed. The satisfaction of some constraints is optional, of others elementary.
This work will investigate the problems and variables to consider when personalising websites. It will use constraints to model the problem and present, investigate, and evaluate solution procedures. The problem, the modelling, the solution procedures, and their interaction will be researched and explored.
Amazon.com will be used as an example of an online retailer who aims to personalise its content.
This document is organised into two parts. In the rst part, the problem is exam- ined, explained and modelled. The rst chapter looks at the problem of rendering a website, explains personalised content and the constraints involved. The second chapter gives an overview and de nitions of constraint satisfaction and optimisation problems, representations and solution procedures. The third chapter models the problem described in chapter 1 by means of constraints introduced in chapter 2.
The second part is concerned with a prototypical implementation of the model. It will explain the approach taken to implement it, details of the implementation,
and how to solve the problem of rendering a website with it.
Motivation
The main point of motivation for the work carried out in this thesis is to create a means of tackling the increasing complexity of web site design and explore new applications of Arti cial Intelligence. The speci cation of constraints to generate a web site does not require programming or computer science skills, the problem and means of solving it are cleanly separated.
A useful approach in software design is to separate design and implementation of the system [Zhu06]. The separation of problem and means of solving it takes this approach a step further [Fre97]. It enables the expression of hard problems in easy terms and is a exible and intuitive way of problem solving.
Currently the constraints involved in web site generation are usually handled in specialised code. This code becomes more complex and di cult to maintain as constraints are added and change. Making even minor changes involves redeploying whole subsystems and increases the risk of outages.
In a constraint-based framework, the constraints can change permanently without any disruption.
Aim and Scope
The aim of this work is to provide a proof of concept and prototypical implementation of a system to generate web sites on the y using constraint programming. In particular, the constraints for a site are assembled into a problem to be solved at run time. The constraints may be di erent for each problem; the problem and means of solving it are completely separate.
Providing a system which is ready for deployment in industry is beyond the scope of this thesis.
Related Work
Although the design and implementation of web sites and online portals as well as Arti cial Intelligence methods are both areas of very active research, there exists only very little work relating the two elds.
Among the related work is a study to design websites using analytical approaches [YHW07], a dynamic programming approach to bandwidth constraints [JLC06], and several studies investigating the integration of soft constraints with semantic web approaches [PCM+06a] [PCM+06b]. Arti cial Intelligence methods have also been applied in the areas of web security [Hua06] and generic business processes [LSPG06] [Tsa02].
The speci c application of Arti cial Intelligence techniques which is subject to this thesis has never been investigated before.
Part I.Modelling of the Problem
1. Description of the Problem
1.1. Personalised Content
Nowadays, online retailers aim to provide personalised content to their customers to maximise their pro ts and improve the shopping experience. Personalisation uses data which is known about the customer to make recommendations. Previous purchases, items the customer has looked at before, and searches can be compiled into a customer pro le.
illustration not visible in this excerpt
Figure 1.. Non-personalised Website
Figure 1 shows an example of generic content on the Amazon.com gateway page. The promotions are unrelated and o er shoes, popular electronics and watches. The content is very easy to generate and can be created o ine by a designer. Displaying it is simply a matter of fetching the stored page fragment.
Figure 2 shows content which takes into account previous activities. It gives an overview of the user's history by displaying recently viewed products. There are also helpful pointers to products the customer did not take a look at but might be interested in. The interest pro le is derived from a search query.
Personalised pages are signi cantly more useful to customers than unpersonalised ones. They provide a starting point to revisit items one is considering buying, assist in exploring the store and nding the product one is looking for, discovering products one did not know about, and omit promotions one is not interested in.
illustration not visible in this excerpt
Figure 2.Personalised Website
1.2. Generating Personalised Content
O ering personalised content introduces new problems. Designers cannot create websites o ine anymore, because the static content they can provide is not personalised. The website needs to be created as it is requested; dynamically. Computers have to generate content according to the information available. Programmers adopt the responsibilities of designers and develop systems which present personalised pages. This complex task requires knowledge of what information is available, how to use it, and how to show it.
There are more factors to take into account. Dynamic components do not only need to know what the customer is doing, but also what the other dynamic components which render the same page are doing. The result needs to be free of duplication and other bad content. The generator must lter any items which have already been bought, are unavailable, or are too similar to items the customer already owns, even if they t the customer's pro le.
Another issue is how items to promote are chosen. An item which has been released recently can be promoted as new and interesting, but if the customer has already taken a look at it, it is no longer new to him. Not all data is equally valuable when generating personalised content. Considering recent activities may result in better promotions than considering an item which was viewed a year ago.
Further di culties arise when products customers bought as presents for relatives or friends are considered. These purchases should not be used to personalise pages, as they do not re ect the interests of the customers. On the other hand, the content generated from this data will be of interest if they are looking for a present for the same person again.
Depending on the amount of data available which needs to be considered for each individual customer and the number of dynamic components which make up the page, the generation of personalised content becomes almost arbitrarily complex. As the number of involved constraints increases, errors are more likely to occur in the model because the number of possible interactions between the constraints increases exponentially.
1.3. Constraints to consider
The most important constraints are summarised below. Depending on the speci c retailer and web site there might be many more to consider. Not all constraints can be modelled appropriately within the scope of this thesis. It is meant to be a proof of concept and general guideline rather than an exhaustive and accurate model.
no duplicate content Any content shown on a page must be free of duplicates. Not only does this create a bad impression with the customer, but also uses space which might instead be used to promote di erent products and increase the chances of showing something the user is interested in.
no bad recommendations Bad recommendations are promotions for products the customer has already bought or is not interested in. The chances of selling the promoted item are very small, and maybe the customer will be annoyed and lose interest in the page.
maximisation of page value The value of a page is determined by the content shown and how it is shown. Personalised content is more valuable than non- personalised content. Showing something valuable on top of the page is better than showing it at the bottom, such that the customer has to scroll down to notice it. Further di culties arise because the value of content is not known or not known exactly. Di erent customers prefer di erent types of content and therefore the content does not have an intrinsic value.
limited time The page must be presented to the customer before he loses interest the time which can be spent generating it is limited. This does not only include the time to compute what to show where, but also the time the page fragments need to render themselves.
available data Depending on the data available, the content which can be gener- ated is di erent. The value of the page has to be maximised regardless of this. There always has to be something to display, even if there is no data available at all.
external events External events, such as the completion of service calls to backend systems, must be considered when generating the page. A service call may not successfully retrieve content and void the current con guration.
forced promotions Sometimes it is desirable not to maximise the value of the page, but to display xed content. This might for example be a paid advert or the promotion of a new product nobody knows about yet.
legal issues In some countries, it might be illegal to promote certain items on cer- tain pages.
retailer policy The online retailer might have a policy which types of products to promote on which types of pages, at which time, and to which customers.
2. Constraints
This chapter introduces constraints and constraint problems. It gives de nitions needed to model problems and illustrates the concepts.
2.1. Introduction
Constraints and constraint satisfaction problems occur in many everyday situations. Scheduling rooms to courses, buses to routes, or workforce to projects are typical examples [GNT04]. Constraint problems are not limited to scheduling however, fur- ther applications include information retrieval, resource allocation, and even games such as Sudoku. Constraint programming has a wide range of applications [Pug95] [Wal96].
Investigating constraints and their properties has long been a part of Arti cial Intelligence research. For more than 30 years, scientists have described and improved methods to solve constraint problems, model them more e ectively, and apply them to real-world problems, e.g. [GLSS79].
The notion of a constraint is simple and intuitive something is required to adhere to external conventions and can therefore not be in arbitrary states. Complex states are characterised by sets of constraints.
The following sections introduce the concepts of constraint problems by presenting examples, analysing them, and formalising the informal notion of constraints and constraint problems through de nitions. Most of the de nitions follow the standard conventions [Mig06] [Dec03].
2.2. Constraint Satisfaction Problems
A popular problem to introduce the concepts of constraint programming is the n- queens problem. The aim is to place n queens on an n × n chessboard such that no queen is attacking another queen [RN02]. The problem is illustrated in gure 3.
illustration not visible in this excerpt
Figure 3.Possible Solution for the N-Queens Problem for n = 4
Each queen must be in a di erent row and column of the board and must not be diagonally in a line with any other queen. The queens are the variables q1, q2, . . . , qn of the problem. The positions on the board each queen may take comprise the set of values each variable may have, its domain. The domain of each queen is the set {1, . . . , n} to designate the position in its row. The problem is modelled with each queen being in a di erent row.
The analysis of the n-queens problem leads to the following de nition.
Def inition 1 (Constraint Satisfaction Problem). A constraint satisfaction prob- lem P is a tuple 〈X, D, C〉. X = 〈x1, . . . , xn〉 is a tuple of n variables and D = 〈d1, . . . , dn〉 is a tuple of n domains. Each domain di ∈ D belongs to the variable xi ∈ X. C = {c1, . . . , cm} is a set of constraints over the variables from X.
This de nition is di erent from the ones usually found. Instead of sets of variables and domains, the mapping is made explicit by tuples. As sets are not ordered, it would be unclear which domain belonged to which variable. Furthermore, no two variables could have a common domain, but this is often the case in constraint satisfaction problems.
The notions of variables and their domains have already been illustrated in the previous paragraph. The requirements for the values of the variables can be formalised as constraints.
Def inition 2 (Constraint). A constraint c(xi, . . . , xj ) constrains the assignment of values to the variables xi, . . . , xj ∈ X. The arity of a constraint is the number of variables it constrains. The constraint speci es a subset of the Cartesian product di × . . . × dj of the domains of the variables xi, . . . , xj that constitutes an allowed assignment.
Constraints can be represented extensionally and intensionally. The extensional representation speci es all tuples which are allowed assignments explicitly, the intensional representation speci es them implicitly. In some cases, the disallowed assignments are speci ed instead of allowed assignments.
The n-queens problem requires all queens to be in a di erent column. This is achieved by introducing a constraint of arity n over all variables which requires them to have di erent values. The extensional representation of this constraint is the set of all the tuples of allowed values, i.e. {〈1, 2, . . . , n〉 , 〈1, 3, . . . , n〉 , . . . }. The intensional representation AllDif f erent(x1, . . . , xn) is much shorter and easier to understand.
The requirement that any queen must not be on a diagonal line with any other queen is harder to represent. For each variable, 2(n − 1) binary constraints are introduced which require the value of the rst variable to be di erent from the value of the other variable plus or minus the di erence in rows between the queens; {q1 = q2 − 1, q1 = q2 + 1, q1 = q3 − 2, q1 = q3 + 2, . . .}.
To solve the n-queens problem, the queens are placed on the board one at a time. When a queen is positioned on the board, a value is assigned to the variable which describes the queen.
Def inition 3 (Partial Assignment). A partial assignment assigns a value to one or more xi ∈ X from their respective domains di ∈ D.
Positioning the rst queen on the leftmost eld of the board is an example of a partial assignment for the n-queens problem.
Def inition 4 (Complete Assignment). A complete assignment assigns a value to every xi ∈ X from their respective domains di ∈ D.
In a complete assignment for the n-queens problem, all queens are positioned somewhere on the board. The positions do not necessarily ful l the constraints. If they do, a solution has been found.
Def inition 5 (Solution to a Constraint Satisfaction Problem). A solution to a con- straint satisfaction problem P is a complete assignment that satis es all constraints c∈C.
Constraint problems can be organised into problem classes and problem instances.
Def inition 6 (Problem Class). A problem class is a problem speci ed with one or more parameters.
The n-queens problem constitutes a problem class. It has one parameter, the number of queens.
Def inition 7 (Problem Instance). A problem instance is an instance of a problem class where all parameters of the problem class have concrete values assigned.
The 4-queens problem illustrated in gure 3 is a problem instance of the n-queens problem class. The parameter n = 4 and determines the number of queens and the size of the board.
Constraint problems can be represented graphically as constraint networks.
Def inition 8 (Constraint Network). The nodes in a constraint network represent variables, edges represent constraints over the variables they are connecting. Edges can be directed or undirected. They are also referred to as arcs.
An example network for the 4-queens problem is depicted in gure 4. The 4-ary constraint which requires the assignments to all variables to be di erent has been decomposed into binary constraints because four-dimensional hyper arcs are hard to draw on two-dimensional paper. Likewise, the constraints that no queen must be on a diagonal line with any other queen has been omitted.
2.3. Solution Process
There are several approaches to solving constraint problems. The most established and wide-spread algorithm is branch-and-bound search [LW66]. The variables are successively assigned values until a solution is found or it becomes clear that no solution is possible with the current partial assignment. This process builds up a search tree which explores the space of possible solutions.
illustration not visible in this excerpt
Figure 4.. Constraint Network Graph for the 4-Queens Problem
Def inition 9 (Search Tree). Each node except the root in a search tree corresponds to an assignment of a value to a variable. The instantiation order is the order in which assignments are made. The level in a search tree corresponds to the number of assignments made; it is also known as the search depth. A branch of the search tree represents a partial assignment, a branch of depth n represents a complete assignment.
An example search tree for the 4-queens problem is depicted in gure 5. Dashed circles represent violated constraints and double circles solutions. The descent into the search tree stops when a constraint is violated or a solution found. The diagram shows only the exploration until the rst solution is found.
illustration not visible in this excerpt
Figure 5.. Example Search Tree built during the Solving of the 4-Queens Problem
Algorithms which check constraints after each assignment until a constraint is violated or a solution found are usually referred to as backtracking algorithms [DF97]. To speed up the solution process, techniques to reduce the size of the search tree can be applied.
Def inition 10 (Constraint Propagation). Constraint propagation is deduction via a subset of the set of constraints. The deduced information is recorded as changes to the problem and usually simpli es the problem by reducing the search space of possible solutions. The new problem is equivalent to the old problem, i.e. both have the same set of solutions.
Constraint propagation becomes intuitively clear when looking at the search tree in gure 5. After 1 has been assigned to q1, it is not necessary to assign 1 to q2 and check the constraints because this assignment cannot be part of a solution.
The notion of consistency is introduced to formalise the process of constraint propagation [Mac75].
Def inition 11 (Consistency Properties). A consistency property holds when constraint propagation of a certain kind reaches a xed point, i.e. no new information can be deduced from the subset of constraints.
The assignment of 1 to q1 allows not only the deduction that q2 = 1, but also that q3 = 1 and q4 = 1. Even more information can be deduced from the other constraints that no two queens must be on a diagonal line. Only after all these restrictions have been deduced, the problem is consistent again.
Def inition 12 (Local Consistency). A unary constraint c(xi) is locally consistent if and only if for every value of the variable xi from its domain dj ∈ Di, c(xi) is satis ed if xi = dj .
A constraint of arity n + 1, c(xa, . . . , xb), is locally consistent if and only if all n-ary constraints over the variables xa, . . . , xb are locally consistent and for every domain value of xi, dj ∈ Di, there is at least one tuple of assignments 〈dc, . . . , dd〉 to the variables 〈xa, . . . , xb〉 \ xi such that c(xa, . . . , xb) is satis ed if xi = dj .
The constraint that all queens must be in di erent columns is locally consistent if after the assignment of a position to a queen this horizontal position has been excluded from the domains of all other queens.
Def inition 13 (Support). A value dj in a domain Di is supported if and only if all constraints over the variable xi are locally consistent. The set of assignments which support dj for a constraint c contains all tuples of values which can be assigned to the other variables constrained by c such that c holds if xi = dj .
Support is bi-directional, i.e. if value di of a variable supports the value dj of another variable for a constraint c, then dj also supports di for c.
The value 3 in the domain of the second queen is supported after the rst queen has been placed in the leftmost upper corner of the board, because only 1 and 2 are forbidden by constraints.
The following de nitions formalise the notions of excluding values from a domain after an assignment and consistency of a problem.
Def inition 14 (Pruning). The pruning of a set of values S from a domain D denoted by Dp = D \ S is the removal of all s ∈ S from D such that Dp ∩ S = ∅. If Dp = ∅ after the pruning, a domain wipe out has occurred.
Def inition 15 (Constraint Revision). Constraint revision is the process of enforcing local consistency for a constraint.
Def inition 16 (Global Consistency). A problem is globally consistent if and only if all constraints are locally consistent.
The de nitions are illustrated in gures 6 and 7 which show the allowed positions on the board and the search tree for the solution of the 4-queens problem, respectively. Dashed elds on the board designate forbidden positions.
illustration not visible in this excerpt
Figure 6.. Solution Process for the 4-Queens Problem with Constraint Propagation
Search algorithms which enforce consistency after an assignment to reduce the size of the search tree are usually referred to as forward checking algorithms [HE80]. They are extended backtracking algorithms which only backtrack when the domain of a variable is wiped out after enforcing consistency.
Both search algorithms are complete, i.e. if a solution to the problem exists, it will be found.
2.3.1. Arc Consistency
Local consistency or arc consistency for binary constraints is the best studied area of constraint revision and propagation. There are many di erent algorithms to achieve arc consistency on networks of binary constraints.
illustration not visible in this excerpt
Figure 7.Search Tree built during the Solving of the 4-Queens Problem with Pruning
The algorithms can be separated into two basic classes coarse grained and ne grained algorithms. Fine grained algorithms keep track of the support for every domain element of every variable and enforce consistency when individual domain values are removed or added, while coarse grained algorithms do not keep track of individual values and enforce consistency on arcs if the domains of the involved constraints change.
Coarse grained algorithms are generally preferred because they are easier to im- plement and often exhibit a better run-time behaviour than ne grained algorithms with a lower complexity due to fewer data structures and hence less overhead.
Table 1 presents an overview of algorithms to enforce arc consistency. It is not meant to be complete or exhaustive, but to show the most important algorithms and their characteristics.
Arc consistency algorithms are often integrated with forward checking algorithms and referred to as maintaining arc consistency (MAC) algorithms [SF94].
There are also arc consistency algorithms for constraints of higher arity. The all di erent constraint is the most popular and best studied non-binary constraint and several algorithms have been developed to enforce di erent levels of consistency on it. Table 2 shows an overview of some algorithms [vH01]. Several studies have extended the classic notion of the all di erent constraint to more sophisticated ltering algorithms [KH06] or di erent kinds of domains [QW05].
Recent research has focused on generalised or hyper arc consistency for higher arity constraints [Rég96] [Rég02] [KT05] [KT03] [QGLOB05].
illustration not visible in this excerpt
e is the number of edges in the constraint graph, m is the maximum domain size, and n is the number of variables.
Table 1.. Overview of Arc Consistency Algorithms for Binary Constraints
illustration not visible in this excerpt
n is the number of variables involved in the all di erent constraint and m is the maximum of the cardinalities of the domains.
Table 2.Overview of Consistency Algorithms for the All Di erent Constraint
2.4. Constrained Optimisation Problems
Constraint satisfaction problems are a kind of constraint problems where a solution which satis es all of the constraints needs to be found. Another kind of constraint problems, constrained optimisation problems, requires not only a solution, but as- signs a value of goodness to every solution, and seeks to nd the best one.
The steel mill slab problem is an example for a constrained optimisation problem [FMW01]. A simpli ed version will be presented here to illustrate the concepts of constrained optimisation problems.
The steel mill slab problem class consists of n orders, each of a particular size. The steel mill is able to produce m di erent sizes of slabs. The objective is to assign the n orders to slabs such that the total waste is minimised. The problem can be modelled with n variables designating the maximum number of slabs to be produced. The domain of each variable consists of the sizes the steel mill is able to produce and 0, designating that the slab is not needed to ful l the order. Additionally, one variable for each order is required. The domain consists of the identi ers of the slabs the order may be assigned to. The constraints require each order to be assigned to a slab and the sizes of the slabs to be at least as big as the sum of the sizes of the orders assigned to it. The goodness of a solution is the sum of the sizes of the produced slabs minus the sum of the sizes of the orders.
An example is given in gure 8. The steel mill can produce slabs of size 5, 4, and 2.
illustration not visible in this excerpt
Figure 8.Example Orders for the Steel Mill Slab Problem
Def inition 17 (Constrained Optimisation Problem). A constrained optimisation problem P = 〈X, D, C, f 〉 is a constraint satisfaction problem with an objective function f which determines the goodness of a solution.
The solution to the example pictured in gure 8 is given in gure 9. The orders are packed onto two slabs of size 4 each.
illustration not visible in this excerpt
Figure 9.Solution to the Steel Mill Slab Problem in Figure 8
Def inition 18 (Solution to a Constrained Optimisation Problem). A solution to a constrained optimisation problem P is a solution to the contained constraint satisfaction problem which maximises or minimises the objective function f .
The solution to the example problem does not produce any waste, therefore, it is optimal.
Def inition 19 (Optimal Solution to a Constrained Optimisation Problem). An optimal solution to a constrained optimisation problem P is a solution to the con- strained optimisation problem for which the objective function f takes a global extremum.
Solving constrained optimisation problems is much more di cult than solving constraint satisfaction problems not only a solution, but the optimal solution, or at least a solution which is good enough, has to be found. To reduce the size of the search tree, the notion of a lower bound is introduced. If a subtree can not contain any solution which is better than the current best one, it can be skipped [IMMH83]. The lower bound speci es the goodness a partial assignment must have for the subtree to be explored. Existing algorithms to solve constraint problems can be extended to provide such bounds [SFV95] [DKL01], but the quality of the bounds is often poor and leads to a lot of unnecessary work [BO03].
There are more sophisticated algorithms to determine better bounds, e.g. Russian Doll Search [VLS96], which solves increasingly large subproblems starting with a problem containing only the last variable.
The de nitions given so far provide su cient means to represent and solve numerous problems as constraint satisfaction or constrained optimisation problems. In some cases however, the de nitions are too limited to support the appropriate representation of a problem.
2.4.1. Extended Constrained Optimisation Problems
Constrained optimisation problems allow to specify a function which determines the goodness of a solution (cf. de nition 17). The function is limited to giving static values for assignments though; it cannot return di erent values depending on which variable xi has been assigned which value dj ∈ Di.
The de nition of an extended constrained optimisation problem addresses this issue by retaining the objective function, but introducing an additional function g which determines the goodness of variables.
Def inition 20 (Extended Constrained Optimisation Problem). An extended constrai- ned optimisation problem P = 〈X, D, C, f, g〉 is a constrained optimisation problem with a function g which maps each variable xi ∈ X to a merit. The objective function f is modi ed to take the merit of each individual variable into account.
Def inition 21 (Solution to an Extended Constrained Optimisation Problem). A solution to an extended constrained optimisation problem P is a solution to the contained constraint satisfaction problem which maximises the objective function f .
2.5. Soft Constraints
Constraint satisfaction and constrained optimisation problems require a solution to satisfy all constraints. Many real-life problems however are over-constrained, some constraints are more important than others, or the solution has to be computed in real-time and does not need to be perfect, but good enough. These kinds of problems can be modelled with soft constraints.
Def inition 22 (Soft Constraint). A soft constraint is a constraint which does not necessarily need to be satis ed in a solution.
Soft constraints are a recent development in the constraint programming community and not as well researched as hard constraints. One of the rst studies on soft constraints is [Fre89]. Usually, the theoretical framework for soft constraint problems is the Maximal Constraint Satisfaction Problem framework introduced in this study, which attempts to maximise the Where the simple approach of minimising constraint violations is not su cient, other frameworks have been derived from it. There are also completely di erent paradigms, such as the introduction of meta constraints to model violation [PRB00].
For a very in-depth overview of soft constraints, see [Sch05].
There are several di erent ways to model soft constraints. These approaches include [Bar03]
- hierarchical models [BDFB+87] [BMMW89],
- partial models [Fre89],
- models which introduce additional variables and hard constraints to model soft constraints [RPP02],
- fuzzy, preference, possibilistic, weighted, or valued models [Rut94] [Sch92] [FL93] [DFP94], and
- semiring-based models [BFM+96] [BMR+99] [BMR97].
In this work, a weighted approach has been chosen. The weights are applied to constraints however, not to allowed tuples as usually assumed. This change allows constraints to be represented intensionally, but restricts the conversion into a semiring-based approach and application of consistency properties [BFM+96]. A valuation structure is introduced to model the cost of violating constraints.
Def inition 23 (Valuation Structure). A valuation structure V is a tuple 〈E, ⊕, ≼, ⊥, ⊤〉. E is the set of valuations which describe the cost of violating constraints. The val- uations are totally ordered by the relation ≼, the minimum element is ⊥, and the maximum element is ⊤. E is closed over the binary operation ⊕ which is commu- tative, associative, monotone, and has the neutral element property. Informally, the basic elements of E are the costs of violation for individual con- straints. They can be combined to calculate costs for violations of more than one constraint using the ⊕ operator. The minimum element ⊥ denotes no constraint violations and the maximum element T denotes that all constraints are violated.
The relation 4 orders the costs of violations, i.e. A 4 B i the sum of violation costs in A is less than or equal to the sum of violation costs in B.
Def inition 24 (Soft Constraint Network). A constraint network with a valuation structure V is called a soft constraint network. The set E of V is the set of levels of the network.
An example of a soft constraint network is given in gure 10. The edges are annotated with the relation that constrains assignments to the connected vertices and the cost of violating the constraint.
illustration not visible in this excerpt
Figure 10.. Example Soft Constraint Network Graph for an inconsistent Problem
The basic idea for incorporating soft constraints is to extend constraint problems with a cost of violation for every constraint and a maximum violation for the problem [SFV95]. In the approach chosen in this work, the valuation structure is de ned on the system of positive real numbers R+. The minimum element is 0, the maximum element is a value k speci c to the particular problem. The ordering relation is the less-than-or-equal-to ≤ relation and the binary operator to combine numbers is the + operator.
Def inition 25 (Soft Constraint Problem). A soft constraint problem P is denoted by the tuple 〈X, D, C, V, ϕ, v, f 〉. X is a tuple 〈x1, . . . , xn〉 of n variables and D is a tuple 〈d1, . . . , dn〉 of n domains. Each domain di ∈ D belongs to the variable xi ∈ X. C is a set {c1, . . . , cm} of m constraints over the variables from X. V is a valuation structure 〈E ⊂ R+, +, ≤, 0, k〉. The function ϕ is a projection from C to E ⊂ R+, i.e. ∀c ∈ C : ϕ(c) ∈ E is the valuation of c. The maximum allowed cost of violation for solutions to P is denoted by v. The function f assesses the goodness of a solution.
The de nition of a solution to a soft constraint problem follows the paradigm of maximal satisfaction of constraints [Fre89].
Def inition 26 (Solution to a Soft Constraint Problem). A solution to a soft con- ∑ straint problem P is a complete assignment such that ci is unsatis ed ϕ(ci)≤v, i.e. the sum of the costs of violation for all unsatis ed constraints ci ∈ C is at most as big as the maximum allowed cost of violation v.
The usual de nition of weighted soft constraint problems is extended with a limit for the cost of violation any solution may have, v. While soft constraints express preferences and do not necessarily have to be satis ed, solutions may be required to be of a certain minimum quality . Furthermore, there are fewer solutions to a problem and the search space is reduced.
Another di erence to the usual de nition of soft constraint problems is that a valuation, or cost of violation, is associated with a constraint, not with an allowed tuple of variable assignments.
Soft constraint problems are inherently constrained optimisation problems, as each solution has a cost of violation. The optimisation is split into satisfaction of constraints and optimisation of the solution [SW05].
The notions of local consistency and arc consistency can be extended to soft constraint problems [BMR95] [SFV95] [Sch00]. In most cases, the algorithms to enforce and maintain arc consistency on problems with hard constraints can not be applied without modi cation to soft constraint problems. There are approaches to modify soft constraint problems to be able to apply arc consistency algorithms for constraint satisfaction problems however [RPBP01] [RPP02]. As weighted soft constraint problems are equivalent to constrained optimisation problems, the search techniques which use lower bounds can be applied as well (cf. section 2.4).
Several algorithms have been developed to use the speci c properties of soft constraints to lter domain values. These include the ones described in [PRB01] [CS04] [CdGS07] [vH04].
2.6. Real-time Constraint Satisfaction
In some applications of constraint programming, the time available to nd a solu- tion to a problem is limited. Such applications include interactive con gurations, monitoring systems, and autonomous devices. The availability of a solution after the time limit elapsed is crucial, sometimes more crucial than satisfying all of the constraints.
Although modern constraint problem solvers are fast and scalable, e.g. Minion [GJM06], and able to deliver solutions quickly, real-time constraint satisfaction is an area of constraint programming where very little research has been done.
The approaches found in the literature add a preprocessing step to the solving of a constraint problem. This usually involves nding a solution to the problem and compiling it into a form which can be used to quickly nd the other solutions to the problem in real time [WF99]. Other algorithms prune values from the domains of the variables such that no backtracking is required [BCFR04]. Heuristics can be applied to speed up the solution process [SW98].
All these approaches share a common pattern in a preprocessing step, which is not limited in time, the problem is presolved by removing domain values, adding constraints, computing a seed solution, or similar. Usually, a trade-o between space complexity of the intermediate representation and loss of solutions is involved. In most cases, it is not necessary to nd all solutions to a problem, the rst one is enough.
In this work, a di erent and new approach has been chosen. The problem is not known a priori, but generated when a solution is needed. Preprocessing the problem is as di cult as solving it; therefore the preprocessing step is omitted completely. Instead, the real-time requirement is integrated with soft constraints (cf. section 2.5). Soft constraints are represented in this thesis with a weighted approach. The weights encode preferences. To integrate this with real-time constraint satisfaction, constraints are dropped as time runs out. The constraints with the lowest preference are dropped rst. With fewer constraints, there are more solutions, so the time to nd a solution decreases. Furthermore, less work has to be done revising constraints. When the time available to solve the problem has elapsed, all the constraints are dropped and the solver generates a solution by just assigning the rst domain value to every unassigned variable.
Dropping constraints to enable real-time solving of constraint problems represents a trade-o between time required to solve a problem and quality of the solution. If the problem is complex and only very little time is available, most of the constraints might be dropped and the quality of the solution might be very poor. If on the other hand the time limit is just below what would be needed to solve the problem without dropping any constraints, this approach provides a solution which is not signi cantly worse than a solution obtained without time limit instead of no solution at all. The key point is that the solver will always provide a solution within the time bounds. For many applications, this is more crucial than satisfaction of all constraints.
Another important observation about the proposed algorithm is that constraints are dropped while the problem is solved. This means that the constraints which will not be considered in the future have been considered in the past, i.e. they have been revised and domain values have potentially been pruned because of them. The quality of the resulting solution to the problem will therefore be between the quality of a solution which does not consider any of the dropped constraints and a solution which considers all constraints. In some cases, the quality of a solution will not be a ected at all when a constraint is dropped because all the values which can be pruned because of it are pruned already.
Before real-time constraint satisfaction problems can be de ned, the notions of time and time limit have to be formalised.
Def inition 27 (Constraint Satisfaction Time). Let P be a constraint problem and M a machine which is able to solve P. The time M takes to solve P is denoted by ts. The current time t is the run time of M since the start of the computation. The time limit tl is an upper bound for ts on M .
The notion of a machine includes both the implementation of a constraint solver and the hardware the solver is running on. It also incorporates all environment conditions which might have an impact on the run time, e.g. operating system and other programs running at the same time. The constraint solver machine abstracts from speci c implementations and computers; all parameters which in uence the run must be the same to be able to compare two di erent machines.
The integration of soft constraint problems and real-time constraint satisfaction is formalised in the following de nition.
Def inition 28 (Real-time Constraint Problem). A real-time constraint problem P is a tuple 〈X, D, C, V, ϕ, ψ, v, tl, f 〉. X is a tuple 〈x1, . . . , xn〉 of n variables and D is a tuple 〈d1, . . . , dn〉 of n domains. Each domain di ∈ D belongs to the variable xi ∈ X. C is a set {c1, . . . , cm} of m constraints over the variables from X. V is a valuation structure 〈E ⊂ R+, +, ≤, 0, k〉. The function ϕ is a projection from C to E ⊂ R+, i.e. ∀c ∈ C : ϕ(c) ∈ E is the valuation of c. The maximum allowed cost of violation for solutions to P is denoted by v. ψ is a projection from E ⊂ R+ to a number from the interval [0..tl] and denotes the time when a constraint of a certain valuation should be dropped, i.e. a constraint c is valid and will be considered i the current time t < ψ(ϕ(c)). The symbol tl denotes the time available for nding a solution to the problem. The function f assesses the goodness of a solution to P .
The de nition of a soft constraint problem (cf. de nition 25) is extended with the projection ψ and the time limit tl. ψ is used to determine which constraints need to be considered at time ti ∈ [0..tl] by mapping valuations to points in the interval [0..tl].
No distinction can be made between di erent constraints with the same cost of violation and therefore the same validity interval. The constraints are grouped into preference classes, constraints in the same class are not distinguishable in this frame- work. This is a drawback of the model, but simpli es the handling of the constraints, because apart from the function ψ no extra structures are required and it builds on the soft constraint framework. In most practical applications, constraints with the same cost of violation will be equal to some extent, e.g. expressing a preference for the same property for di erent sets of variables. Therefore the current model is reasonable despite its simplicity.
The de nition of the solution to a real-time constraint problem extends the de - nition of the solution of a soft constraint problem (cf. de nition 26) as well.
Def inition 29 (Solution to a Real-time Constraint Problem). A solution to a realtime constraint problem P is an assignment S to the variables in X which satis es the following conditions, S is a complete assignment, the time ts required to nd S is less than or equal to the time limit tl, and ∑ ∑ ci is unsatis ed ϕ(ci) ≤ v + cj: ψ(ϕ(cj))≤ts ϕ(cj),i.e.thesumofthecostsof violation for all unsatis ed constraints ci ∈ C is at most as big as the maximum allowed cost of violation v plus the costs of violation of the constraints dropped during the solution process.
In other words, the third condition requires a solution to ful l all constraints which are valid at ts to be satis ed except the ones violated in the framework of soft constraint problems. The maximum allowed cost of violation v is augmented by the cost of violating the invalid constraints cj : ψ(ϕ(cj )) ≤ ts. Thus a solution S may have a total cost of violation higher than v after constraints have been dropped.
2.6.1. Analysis of the Function ψ
The function ψ is crucial to the de nition of real-time constraint problems. It de- termines when a constraint will be dropped. ψ should have the following properties,
1. injective, i.e. every valuation is mapped to a time,
2. monotonically increasing, i.e. the constraints with a low valuation are dropped rst and the constraints with a high valuation last,
3. ψ(0) = 0 and ψ(⊤) = tl, i.e. at the beginning only constraints with the valuation 0 are dropped and when the time limit is reached all constraints are dropped, and
4. non-linear, i.e. the constraints with a high valuation are dropped when there is only very little time left.
The last property might be optional depending on the problem, the other prop- erties must be satis ed by all functions used in this framework however. Property 3 assumes that the valuations are positive numbers. The minimum value was speci cally chosen to be returned for 0 and not for ⊥. If all constraints have a level of preference greater than zero, they should all be considered in the beginning. Furthermore, if ⊥ = T, all constraints would be dropped before the solving of the problem started.
The function ψ(x) = satis es above properties. The parameters a and b are problem-speci c and ensure properties 4 and 3, respectively. The value of b can be computed, the value of a must be estimated. a controls the steepness of the function curve for a particular time limit tl; a good rule of thumb is a = 100 · tl. T ln a · +1 Given property 3, b can be computed as b = gure 11.
An example is shown in Until half the time available to solve the problem has passed, only the constraints up to a tenth of the valuation of the most important constraint are dropped. The more important constraints are only dropped when more than 90% of the available time has elapsed.
Increasing a leads to a more conservative behaviour, i.e. constraints are dropped later, while decreasing a leads to constraints being dropped earlier.
The model also extends to hard constraint problems. All constraints have the maximum valuation and are dropped when the time to solve the problem is up. The solver proceeds normally until the time limit is reached and then assigns the rst value in the respective domain to all unassigned variables.
Real-time constraint satisfaction introduces an important aspect into constraint programming Quality of Service. The framework guarantees that a complete assignment will be computed within the speci ed time. It is possible that the time limit is big enough to solve the problem without dropping any constraints. Still the speci cation of the limit guarantees that, even if the conditions change and more time is required to nd a solution, the limit will not be exceeded.
illustration not visible in this excerpt
b = 4.6151205168 computed with previous parameters. The dashed curves show di erent values of a.
Figure 11.. Example Curve of ψ with tl = 1, ⊤ = 1, and a = 100 · tl = 100
3. Constraint Problem Model
This chapter introduces ways to model the problems described in chapter 1 with constraints. The rst simple models will be improved, re ned and extended in later sections.
3.1. Slots and Campaigns
To model a problem as a constraint satisfaction problem, the variables, their domains, and the constraints have to be speci ed (cf. chapter 2).
Def inition 30 (Campaign). A campaign c is a component which returns content. The content can be personalised and dynamic or non-personalised and static. A set of campaigns is a domain d.
Def inition 31 (Slot). A slot x is a part of a page which can hold exactly one campaign. A slot is a decision variable.
Def inition 32 (Page). A page p contains a tuple X of n slots.
Def inition 33 (Problem of Rendering a Page). The problem of rendering a page p is the constraint satisfaction problem P = 〈X, D, C〉, where X is the tuple of slots which make up p and D is the tuple of domains. The number of slots and domains is equal. The domain di for slot xi is the set {c1, . . . , cm} of campaigns which are scheduled in the slot. C is the set of constraints.
The only constraint in this model is the AllDif f erent constraint which ensures that there are no duplicate campaigns on the page. Thus, C = {AllDif f erent(x ∈ X)}.
A solution (cf. de nition 5) to P is an assignment of campaigns to slots such that no campaigns shows up twice.
3.2. Values of Campaigns
Each campaign has a number associated with it which determines how valuable the campaign is. Introducing this parameter requires only slight modi cations of the model, but turns the constraint satisfaction problem into a constrained optimisation problem.
Def inition 34 (Value of a Page). The value of a page p is determined by the function v;
[Abbildung in dieser Leseprobe nicht enthalten] value(assignment(xi)).
Def inition 35 (Problem of Rendering a Page with Page Value). The problem P of rendering a page can be rede ned as P = 〈X, D, C, v〉, where v is the objective function to maximise. The set of constraints C and the set of domains D remain the same.
The extension of the existing model with the introduction of values has changed the type of the problem. It is no longer enough to nd campaigns for all slots which satisfy the constraint, the value of the page has to be optimised. Therefore, nding one solution to the problem does not mean that it can be returned. There may be a better solution. The best solution remains unknown until the search space is exhausted, which adds signi cantly to the required resources.
The search for solutions can not terminate before every possible solution has been explored because the value of the objective function has to be maximised and there is no upper bound. If the maximum value was known, the search could terminate as soon as this value was reached because any other solution could not be better, only as good. Determining the maximum value of a page is as di cult as solving the problem of assigning campaigns to slots however.
3.3. Values of Slots
The association of values with slots can not be adequately represented by classical constraint optimisation problems. They do not allow values which determine the importance or usefulness of uninstantiated decision variables. The model has to be changed to extended constrained optimisation problems (cf. de nition 20).
Def inition 36 (Value of a Page). The value of a page p is determined by the function v;
illustration not visible in this excerpt
De nition 34 has been changed to include the value of the slot xi, value(xi), in the calculation of the value of the page.
The de nition of the problem p remains unchanged. The addition a ects only the function v.
3.3.1. Example
Let p be a page consisting of three slots;
X = 〈left,center,right〉.
Let there be three campaigns;
d={recentlyViewed,recommendations,cerealPromotion}.
[...]
- Citar trabajo
- Lars Kotthoff (Autor), 2007, Using constraints to render websites, Múnich, GRIN Verlag, https://www.grin.com/document/83438
-
-
-
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X.