2.1. Description of the vacation example

The problem consists of configuring a vacation package composed of a set of destinations. For each destination, a set of activities involving sports and visits has to be selected. All the selections are constrained by the period when the travel is scheduled, the level of quality expected by the customer, the budget, and the global purpose of the package (relaxation, culture, or recreation). Depending on the season, some destinations are possible or not. Depending on the season and on the destination, some activities are impossible and the price and the quality will be different. A catalog of destinations and activities with their respective compatibilities, prices, and levels of quality is available in the form of an external database that is loaded dynamically when the vacation advisor server application is launched. Table 1 gives an example of a compatibility table, which will be used in Section 3.

Example of compatibility table

In our model, we have defined one subclass for each valid combination of destination and season. Each such combination determines the values for the price and quality attributes. For example, we find Majorca/summer, but not Majorca/winter. Furthermore, Florence/winter is cheaper than Florence/summer.

This example can easily be turned into a real-world application by adding more components. The real-world application should furthermore allow the selection and configuration of an accommodation for each stop and also permit the selection of flights or trains to travel from one stop to the next one. For the sake of simplicity, we omit these issues in this paper.

Figure 1 shows the object model of the problem in the form of a UML diagram. Depending on the purpose of the package, some activities are automatically selected or removed. For example, if the purpose is “relaxation,” all sports are removed from the set of activities, and if the purpose is “culture,” at least one visit to a museum or medieval castle is selected per stop.

A vacation adviser class diagram.

The vacation example has been completely formulated in a constraint-based configuration tool (ILOG, 2002).

2.2. Preferences for the vacation example

A catalog of vacation destinations usually contains many possibilities, and user preferences are important to choose among them. The following kinds of user preferences and wishes are natural:

• preferences based on numerical criteria, such as the total price, the average quality, or the maximum distance to a destination. People may want to minimize price, maximize quality, and/or minimize distance.
• preference about attributes with a discrete domain, such as the activities. For example, the user may prefer visits to attraction parks to visits to museums. Furthermore, a user may prefer canyoning to wind-surfing.
• wishes, such as spending at least one night in a luxury hotel.

Preferences among multiple criteria can easily be in conflict, meaning that it is not possible to choose the best value for all criteria simultaneously. In this case, preferences between criteria and wishes specify how to resolve those conflicts:

• The user prefers maximizing the quality to minimizing the price of the vacation.
• The user wants to spend at least one night in a luxury hotel even if the total price is minimized.

These user preferences and wishes can either be specified individually or be generic and depend on the characteristics of a user or the vacation:

• For a student, minimizing price is more important than maximizing quality. For a manager, the inverse is the case.
• If the purpose of the vacation is cultural, then the user would like to visit a museum in each vacation stop, if this is possible.

Although the class diagram of the vacation example is not very complex, it is still necessary to make choices in an adequate order when configuring a vacation package. The following preferences should be respected by the search procedure:

• The activities of the vacation package should be chosen completely before assignment and configuration of the vacation stops.
• The activities of a vacation stop should be chosen before its type and destination, because a given combination of activities usually permits only certain destinations.

These preferences influence the order in which attributes are assigned. There are also preferences among the different values of an attribute:

• If the total price should be minimized, then cheaper hotels should be considered first.
• The strategy should assign as many activities to a vacation stop as possible.
• There may also be dynamic preferences. For example, the user may prefer Hawaii to Florida if wind-surfing has been selected for a vacation stop.

This list shows that user preferences as well as preferences for search control arise naturally in this domain.

3.1. Decisions

Traditionally, search procedures such as A^* define search as a method for exploring a state space consisting of a set of states and their successor relation. Such a search procedure does not make any assumptions about the structure of the state and is thus quite general. In particular, a search state does not reflect knowledge about the choices or decisions that need to be made to produce the state. A decision corresponds to a choice a search procedure makes when moving from one state to a successor state. Representing states as sets of decisions has several advantages. For example, the order of decisions can easily be controlled, and it becomes possible to determine conflicting decisions if the search procedure runs into a dead end. This alternative way of representing search states has therefore been adopted by approaches based on truth-maintenance systems.

To solve configuration problems, a configurator typically tries out different value assignments to attributes and relations of components. Hence, it adds assignment constraints to the original problem. In order to describe this process, we consider decisions based on constraints. Each decision has an associated constraint and will be explored by a specific search procedure in a task-specific way. For example, a configuration strategy will create two successor states when exploring a decision. In the left successor state, it adds the constraint of the decision, whereas it adds the negation of the constraint in the right successor state. Typically, we will use chronological backtracking to explore the resulting search tree. Hence, the search procedure will first explore the left successor and its subtree. If this subtree does not contain a solution, it backtracks to the right successor state.

Formally, a decision is specified by an identifying term t (e.g., a name) and a constraint φ. It is written in the form decision t:φ;. We can also consider decisions as named or labeled constraints. The name belongs to a new set of symbols used for naming decisions. (In later sections, we also introduce other terms for identifying decisions.) Different decisions must have different identifying terms. Hence, we cannot have two decisions of same name.

The constraint φ may not only be a value assignment form f = v where f is an attribute or relation¹

In our example, we model the selected visits and sports by two set variables (i.e., constrained variables that are assigned a set of values instead of a single value). In order to select visits to museums, we add the membership constraint member (Museums, visits) to the configurator. For each possible visit and sports activity, we introduce a decision consisting of such a membership constraint and a name:

A configuration problem is now specified by a (finite) set

of constraints and a (finite) set

of possible decisions.

3.2. Decision-making process

A search procedure explores the given decisions one after the other. We can also say that it determines a total order among the decisions. This order greatly influences the problem-solving behavior and is an important part of a search strategy. The order may be static (i.e., specified initially) or dynamic (i.e., depending on decisions that have been executed successfully). In this section, we make this order explicit, a tactic that allows us to influence it by constraints.

Suppose our configuration problem has a set

of n decisions. We can define the order in which the decisions are explored by assigning a position π(δ) to a decision δ ∈

. The ith decision obtains the position i. Hence, π is a mapping from

to {1,…, n}. Different decisions obtain different positions:

Initially, the π(δ) values are not known, but their possible domain is reduced as the search occurs. After exploring the kth decision, the unexplored decisions can only get the positions in {k + 1,…, n}. Conceptually, we can consider the π(δ) values as constrained variables, a consideration that enables us to formulate constraints on the order in which decisions are explored. As a consequence, the search procedure cannot assign any arbitrary position to any arbitrary decision, but must make assignments in a way that respects these constraints.

In the ith step, the search procedure has already assigned the position 1 to i − 1 to decisions. It now selects one of the decisions that can have position i and explores it. This exploration can occur in various ways and depends on the concrete task:

1. Search strategy: When a decision δ is being explored, a (binary) choice point is set up. In the left branch, the decision δ is added to the current set
   
   of constraints and we say that the decision has succeeded. In the right branch, the negation of δ is added to
   
   and we say that the decision has failed. In both branches, constraint propagation is applied after adding a constraint. If the propagation fails, backtracking occurs.
2. Preference Satisfier: When exploring a decision δ, we check whether it is consistent w.r.t.
   
   (i.e., whether there exists a solution). If this is the case, the decision δ is added to
   
   and we say that it has succeeded. Otherwise, it is dropped. Hence, decisions are tried out in increasing order, and only successful decisions are added to
   
   . In this approach, decisions are made whenever possible. In this respect, they behave exactly as defaults.

The first procedure assigns the positions in a greedy fashion and uses them to define a complete search tree that allows us to enumerate all solutions. Because the values of the positions are chosen dynamically, they can differ in different branches of the search tree.

The second procedure considers alternative values for the positions π(δ) (i.e., alternative decision orders) but executes the decisions in a greedy fashion once these positions are determined. We can enumerate all solutions in this way if all orders are allowed. (In the next section, we impose constraints on the order.) In this case, we eliminate certain solutions and enumerate only so-called preferred solutions. At first glimpse, it seems that the basic complexity of this approach is much worse than that of the first approach (O(n!) orders instead of O(2ⁿ) leaves in the search tree), although fewer solutions may be obtained if the order is constrained. Indeed, many orders produce the same solutions. Junker (2000) showed how irrelevant orders are avoided and how the effort can be reduced to a binary tree of depth n. Furthermore, it is possible to prune certain parts of the search tree that do not contain preferred solutions.

The basic idea of this preference-based search (PBS) is as follows: PBS searches through a binary search tree as a complete search. In each search node, a decision δ is explored. In the left subtree, the constraint φ of the decision is added to the current set of constraints and the current position k is assigned to δ. Instead of adding the negation of φ in the right subtree, PBS requires that φ is refuted by subsequent decisions. If the negation of φ can indeed be deduced in a subsequent step k + l (where l ≥ 1) then δ is explored in this state and obtains the position k + l. However, if PBS reaches a state such that no further decision can be selected (i.e., δ is preferred to all remaining decisions in this state) and φ is consistent in this state, then PBS cannot extend the current state to a preferred solution and backtracks. We refer the interested reader to Junker (2002) for a detailed description of the PBS algorithm that is used by the preference satisfier.

We give a simple example for determining a preferred solution. Suppose the set

contains the compatibility constraint between the five vacation destinations and the six vacation activities that was introduced in Section 2. As long as there are no constraints on the order of decisions, we can introduce them in any order. Once the order of decisions is determined, we explore the decisions in a greedy fashion. The first decision Attraction-d succeeds and allows Florida as single destination. Florida is compatible only with attractions and wind-surfing. Hence, only those activities succeed:

3.3. Preferences as constraints on the decision order

Preferences between decisions are a convenient way to specify which decisions should be kept if several decisions are in conflict. More preferred decisions are kept, whereas the less preferred decisions may be removed in case of such a conflict. Following (Brewka, 1989; Junker, 1997), we use preferences of the form prefer(t,u) as constraints on the order of decisions. If the term t refers to the decision δ_t and the term u refers to the decision δ_u, then a preference imposes the following constraint on the positions of the decisions:

In our example, we use the following preferences:

Decision orderings that violate those preference constraints can no longer be used to generate solutions of our configuration problem. For each solution X, we require that there is an order of decisions that satisfies the preferences and that is able to produce the solution by a selection mechanism. When we use the approach of a search strategy, any order is able to produce any solution. For a preference satisfier, preferences that are implied by a solution eliminate certain orders. If we can find an admissible order such that the preference satisfier produces X, then X is called a preferred solution. Junker (1997) showed how preferred solutions can be constructed incrementally.

Below, we give the two preferred solutions of our example. The first decision is either MedievalCastle-d or WindSurfing-d and determines which of the two preferred solutions is obtained. For each of them, we give one of the following (justifying) orders:

If a new constraint is added, preferred solutions can become inconsistent and nonpreferred solutions can become preferred ones. For example, if Bavaria is not possible (e.g., overbooked), then our first solution becomes inconsistent and a new preferred solution is obtained. Hence, additional constraints can change the set of solutions in a nonmonotonic way:

3.4. Structured preferences

In certain cases, several preferences can be replaced by a single one if decisions are grouped together. In our example, we want to express the idea that all visit decisions are preferred to all sports decisions. In order to express this idea, we introduce two groups of decisions. A group of decisions is specified by providing a unique identifying term (e.g., a name):

A decision group is simply a set of decisions (or of other decision groups). Elements of decision groups are stated via containment constraints of the form contains(g, d). If g is a term referring to a decision group g′ and d is a term referring to a decision d′, then contains(g, d) implies that d′ is a member of g′. In our example we introduce the following containment statements:

We can now introduce preferences between two decision groups g₁ and g₂, meaning that all elements of g₁ are preferred to all elements of g₂:

We have thus expressed the following preferences in a more compact form.

If the first group has n₁ elements, and the second group has n₂ elements, we thus replace n₁·n₂ preference statements by n₁ + n₂ containment statements, two groups, and a single preference statement. If the groups are large, this replacement leads to large gains in the size of the preference specifications.

Decision groups can be arbitrarily nested, a fact that allows us to formulate strategies for configuring components. In Section 4.3, we will map each component to a decision group, a mapping that easily permits us to influence the order in which those components are configured.

3.5. Dynamic preferences

Configuration sales strategies can depend on the customer profile, the time period, special offers, and the available stock. Hence, they lead to preferences that are context dependent and that will be activated dynamically during the decision-making process if certain conditions are satisfied. Because preferences are constraints, we can represent these dynamic preferences by logical implications of the form

We can distinguish dynamic preferences that depend on data and dynamic preferences that depend on other decisions. Preferences that depend on data can be completely determined in the root state of the search tree, that is, before the configurator makes any decisions. Preferences that depend on other decisions are generated during search and are effective only if they concern decisions that have not been explored so far.

We consider some examples of dynamic preferences. Depending on the purpose of the vacation, the customer may prefer visits to sports activities or vice versa:

• If the purpose is culture, then prefer visits-g to sports-g.
• If the purpose is recreation, then prefer sports-g to visits-g.

Because the purpose is given initially, these preferences depend only on data.

We also give an example of preferences that depend on decisions. For this purpose, we additionally introduce decisions for choosing the destination, a choice which is necessary if the same sets of activities are possible at different destinations. For each possible destination, we suppose that there is a decision such as

Furthermore, we suppose that all these additional decisions have been added to a decision group called destination-g which is considered after the visit group and the sports group. This arrangement is made sure by the following preferences:

We are now able to state that Hawaii is preferred to Florida if wind-surfing has been selected:

Because sports activities are chosen before the destination, this dynamic preference is generated before the destinations are chosen. In fact, the preferences between the sports group and the destination group make sure that this dynamic preference is only applied to decisions that are not yet explored when the dynamic preference is generated.

3.6. Inconsistent and metapreferences

The preferences that are obtained from the various statements given above risk being inconsistent. A set of preferences is inconsistent if there is no total order of the decisions that respects all of them. For example, the following preferences are cyclic and therefore inconsistent. In this case, there is no preferred solution:

If the number of decisions is finite, then inconsistent preferences are obtained only if there are cyclic preferences. In all other cases, it is possible to assign a position number to the unexplored decisions that respects the preferences. In contrast to preferences, decisions with an inconsistent constraint φ do not provide any problem since they immediately fail when being explored by the search procedure. As a consequence, the search procedure backtracks to the previous search state and thus removes the inconsistent constraint.

In order to make preference statements robust, preferences should be introduced themselves as decisions, as the following example shows:

Then metapreferences can be used to resolve potential conflicts between those preference rules:

It is important that a decision d that consists of a preference between two decisions d₁ and d₂ has a higher priority than the decisions d₁ and d₂. A simple way to achieve this condition is to create two decision groups g^p and g^d, where the first one contains the preference decisions and the second one contains the decisions to which the preferences are applied. Furthermore, we specify that g^p is preferred to g^d by a hard preference.

Thus, metapreferences can control which elements in a set of cyclic preferences can be retracted and which should be kept. Future work is needed to investigates which cases can be adequately treated by this approach and which cases may require alternative approaches such as removing all the preferences that are in conflict.

4.1. Configuration language

In order to state configuration problems, we need a formalism for knowledge representation that is sufficiently rich to support composed components as instances of classes and concepts as well as rules and constraints (Soininen et al., 2000). In the literature, different approaches for solving configuration problems have been developed. Most approaches are based on or evolved from a single knowledge representation paradigm (e.g., description logic, rules, logic programming, constraint satisfaction, or constraint programming), but have been extended in order to cover the full range of configuration knowledge. In this paper, we focus our discussion on a constraint-based configuration approach that has been extended by an object language and logical rules formulated on constraints, following the line of Haselböck and Stumptner (1993) and Mailharro (1998). However, parts of our discussion may also be relevant for other approaches that support composed components, rules, and constraints.

We briefly outline our configuration language (ILOG, 2002) before discussing which form of decisions and preferences are needed for it. The language supports classes, objects, attributes, relations, expressions, constraints, and rules. Given concrete classes can be organized as subclasses of mutually exclusive abstract classes, an organization that leads to a forestlike class taxonomy. This class hierarchy is used in two ways. On the one hand, it defines the domain for unknown component types. On the other hand, it defines the inheritance scheme for the instances of classes.

Each class can have a set of field declarations consisting of a field name and a domain. The domains can be refined by subclasses. Fields can represent attributes (e.g., in the case of a string, integer, or floating-point domain) or relations between the given class and a target class. Relations include assignment as well as partonomic relations. We distinguish fields containing individual parts and fields containing anonymous instances of a class. In the first case, the field value is a single instance of the target class or a set of such instances. In the second case, the field value is a concrete subclass of the target class or a set or bag of those subclasses.

Components are represented by objects that are instances of classes and that inherit attributes and relations from them. Instances of abstract classes can be classified dynamically to a concrete class. This process will complete the instances by the additional fields of the subclass and impose the domain restrictions of the subclasses. In order to state constraints on arbitrary instances of a class, we introduce logical variables for objects.

There is a rich layer to formulate expressions, constraints, and rules. Expressions are of different types, namely integer, floating-point, object, object-set, class, class-set, or class-bag. There are constant expressions (e.g., integer number, floating-point number, objects, classes); field expressions of the form f (e) or e.f, where f is a field and e is an object expression; arithmetic expressions, such as e₁ + e₂; set expressions; and sophisticated expressions over sets, such as sum-over-set. Constraints cover comparison expressions, set operators, compatibility, exclusion, requirement constraints, and Boolean combinations of constraints (including negation and implication). Logical rules can be formulated as universally quantified constraints of the form forall x in C:φ(x) where x is a logical variable, C is a class, and φ(x) is a constraint containing x as a free variable.

4.2. Which preferences are needed for configuration?

We now investigate how to apply decisions and preferences to configuration problems. As mentioned in the introduction, we want to use preferences for different aspects of configuration problems, such as user preferences and search control. User preferences about choices, such as the destination of a vacation, or about defined criteria, such as the total price of the vacation, are an adequate way to pick out interesting solutions among an often very large solution set. Similarly, user wishes or desiderata represent conditions that should be satisfied whenever possible.

A second application of decisions and preferences consists of controlling the search process in a user-friendly way. In order to find a configuration, a search procedure needs to determine the types and field values of all relevant components. It usually starts to configure a root component by choosing its type and its field values. This process is repeated recursively for each subpart. The resulting search behavior rather depends on the form of the search decisions that are explored and on the order in which they are made. If chronological backtracking is used in a systematic tree search, then a bad search order can easily lead to thrashing. In our vacation example, it is important to choose the type of a vacation stop before making any decision about its price. Furthermore, a bad search order can produce very bad solutions first. For example, if we want to minimize price, the search strategy should choose cheaper hotels first instead of considering first-class hotels.

In addition to this consideration, a configuration strategy needs decisions that follow the partonomic structure of a configuration and that take into account parts that are generated dynamically. Hence, strategies need to be applied to an unknown number of instances of a given class. Moreover, strategies need to be open and to cope with fields that are dynamically added to a component when it is classified.

Although the basic preference programming layer of Section 3 could, in principle, be used to formulate user preferences and search strategies, it would not be efficient in time and space. For example, the strategy would need n := f·d decisions for f fields and d values in the field domains, a need that is not affordable for realistic problems. To handle this situation, the basic idea is to introduce higher level primitives that behave as an aggregate of basic decisions and preferences but have internally more efficient data structures and efficient algorithms. We thus follow the example of constraint programming, where global constraints, such as allDiff, combine a clean modeling facility with an efficient algorithm from graph theory.

In order to produce these high-level primitives of preference, we exploit the different forms of configuration knowledge, such as objects, constraints, and rules. Figure 2 shows this plan. We first apply the concepts of decisions and preferences to constraint programming. Each field has a domain, and it is natural to represent an order for the domain values in a compact form. Similarly, we represent all search decisions for assigning a value to this field in the form of a compact decision set. For example, we generate the set of assignment decisions for the destination field of a stop-object by the statement assign(Stop.destination). A decision set is similar to a decision group, although its elements are not added explicitly but are generated implicitly when needed. For example, a decision

is generated if Hawaii is a best value w.r.t. a given domain order. Domain orders can be specified by priorities of values or by preferences between values, as illustrated in the following examples for the domains of visit and sports activities²

The preferences for configuration.

There are also predefined domain orders, namely, the decreasing and increasing orders of integers. We directly use the field as the identifier for the decision set. Thus, we can easily reference the decision set in preference and contains statements. We simply write prefer(Stop.destination, Stop.price) to indicate that the destination of the stop needs to be chosen before its price.

The next step is to assemble these elements in order to get a complete configuration strategy for composed components. In the next section, we discuss in detail how the structure of components is exploited to set up configuration strategies. We also introduce primitives for configuring components as soon as they are assigned to the current configuration.

Finally, we also apply the concepts of decisions and preferences to rule programming, as indicated in the left branch of Figure 2. Logical rules of the form forall x in C:φ(x) are true for all instances of C. However, rules can also be used to express user wishes that can be satisfied for some instances, but not for all. For example, the application developer may write a rule stating that each vacation stop should include a visit to a museum. This rule may succeed for some destinations, but not for those that have no museums. We call those rules decision rules.

4.3. Configuration strategies

In this section, we discuss how a configuration strategy can be built upon decisions and preferences. For this purpose, we exploit the structure of the given configuration problem.

In order to determine a configuration, a search strategy typically starts to configure a root component and then follows a part-of hierarchy or other relations between components. When configuring a component, it tries out different value assignments to the fields of the component, including an implicit classification field. We can model such a strategy as follows:

1. For each object i, we introduce a decision group group(i). All decisions needed for configuring this object are contained in its decision group. As the identifier for the decision group, we directly use the object i, which allows us to refer to the group in containment and preference statements. For example, the order for configuring objects can be influenced easily in this way.
2. For each field f of the object i, we add a decision set of the form assign(f) or assignElements(f) to the group i.
3. In order to influence the order of the decisions, we apply a domain order o to a field f by using a statement of the form preferValues(f,o). Furthermore, we can influence the order in which fields are configured by preference statements between fields.

Typically, such a strategy will not be formulated for individual objects, but for arbitrary instances of a class. This formulation can easily be achieved by rules, such as the following strategy for instances of vacation stops:

Preferences about field values may be parameterized independently of the basic strategy by formulating separate rules:

We thus obtain a convenient way for formulating strategies for configuring an object. However, one element is missing. When assigning objects to selected relations, the strategy needs to configure the assigned objects as well. We achieve this behavior by using modified versions of the decision sets assign(f) and assignElements(F). For example, when we assign vacation stops to a vacation object, these stops need to be configured as well. In the following strategy, the configureElements statement will add the decision groups of assigned vacation stops, an addition that means that they will be configured as well:

We are now able to formulate complete configuration strategies sophisticated enough to allow us to configure complex components. There is also a user-friendly way to specify those strategies. The user only needs to indicate how the strategy should traverse a given class diagram by specifying field priorities and by selecting object and object-set fields for which the elements should be configured as well. The field priorities will be used to influence the order of the fields inside an object group. The other information, namely, decision sets and domain orders, is completed by default choices or can be specified differently.

This approach for treating configuration strategies has several advantages for configuration. First of all, the approach is user friendly. It is very easy to specify or parameterize such a strategy in terms of field priorities. Hence, the application developer can program complex search strategies without needing special skills in constraint and search programming. Second, the approach is open: new decisions can be inserted at any place in the object-oriented decision structure. New preferences between fields can be added easily. Hence, the configuration strategies are well adapted to configure fields and objects that do not exist initially but are generated during search. Third, it is possible to specify the search strategy in the form of rules, as shown above. The application developer can write rules that complete information depending on the given context. For example, the domain order for choosing the destination of a vacation can depend on the chosen activity. We offer such a rule-based search-programming facility in a more high-level business-rule language. Finally, complex multiphase strategies can be obtained easily. We introduce multiple strategies and encapsulate each of them inside a decision group.

4.4. Wishes and user preferences

Many configuration problems, such as product and service configurations, involve large catalogs and usually have many solutions. In order to find configurations that are interesting for the user, a configurator has to take into account user preferences and wishes (or desiderata). For example, the user might prefer canyoning to wind-surfing and hiking. The user may also prefer cheaper vacations and may have desiderata or wishes such as visiting an attraction park in each stop. Multiple preference criteria, such as minimizing price and maximizing quality, may be in conflict. In such a case, the user may specify which criterion is more important by specifying a preference between them.

It is interesting that we can already use our abstract preference programming language to write down preferences about and between criteria. We use the same syntax as for search strategies, namely, decision sets and domain orders, but change their search behavior. For example, we formulate user preferences such as minimizing the price and maximizing the quality of myVacation as follows:

These statements are now created with the help of a preference satisfier instead of a configuration strategy. Instead of trying out one value assignment after the other (e.g., to compute the price), the preference satisfier determines the best value assignment by solving an optimization subproblem. This subproblem can, for example, be solved by a constraint-based branch and bound procedure that uses the corresponding criterion as an optimization objective. Once the best value v is found for the price, we create a decision assigning v to the price. This decision is either executed (meaning that the price is constrained to v) or needs to be refuted by first optimizing other criteria, such as the quality. We thus obtain extreme solutions, where either the price is minimized first and then quality is maximized or the quality is maximized first and the price is minimized as a second criterion. Preferences between criteria constrain those orders and state which criteria are more important. These preferences may depend on given characteristics of the user, such as the profession:

For a student, the price will always be minimized as the first criterion in this case. For a manager, only quality can be maximized first. Following the approach in Ehrgott (1997) and Junker (2002), it is also possible to find compromises with such a lexicographical approach, assuming that the criteria are expressed on the same scale. This kind of compromise is achieved by minimizing the maximum of two criteria, fixing it to the best value, and then minimizing the minimum of the two criteria.

Individual wishes or desiderata can be directly formulated in our existing preference programming language. For example, the user wants to visit an attraction park if this is permitted by the other criteria. We add a decision for this purpose:

In contrast to the configuration strategy, a preference satisfier tries to satisfy this wish whenever possible. Hence, if there is a solution permitting the visit of an attraction park, then it will only produce those solutions. However, a satisfiable wish may be in conflict with other wishes or other criteria. If the preference satisfier treats these other decisions first, then it will not satisfy the given wish. Preferences between wishes and criteria again permit the user to state which of them is more important.

Some wishes apply to arbitrary instances of a class and will be satisfied for some of them, but not for others. In order to express them in our preference programming language, we introduce a decision rule, which has syntax similar to the default rules in Poole (1988). An example is to visit an attraction park at each vacation stop:

Instances of logical rules must always be satisfied. In contrast, instances of decision rules are handled as basic decisions. Some of them may be satisfied, whereas others can fail. For example, consider three vacation stops with already chosen destinations, such as Paris, Venice, and Vienna. If Venice has no attraction park but the other two destinations do offer attraction parks, then the second decision will not be satisfied but it will not prevent the satisfaction of the other decisions.

The decision rule is a kind of decision group, the elements of which are not explicitly added. In fact, the elements of the decision rule are the decisions created for its instances. A decision rule has a name as identifier (such as attraction-rule in the rule above). Instances of decision rules are identified by terms such as attraction-rule(Paris). It is thus possible to refer to decision rules and their instances in containment and preference statements.

4.5. Semantics of high-level configuration preferences

In the previous sections, we introduced high-level primitives for stating decisions and preferences in a compact form and thus obtained an abstract preference programming language. The same language can be used for different tasks, such as satisfying user preferences or controlling search. Figure 3 shows this principle. The tasks themselves differ in the way the basic decisions and preferences interact with the constraint solver. Each task can associate a different search algorithm with the abstract decisions and preferences. Having a common abstract language for preference programming has several advantages: first, a uniform syntax is used; second, the mapping of high-level decisions and preferences is independent of the given tasks; third, new possibilities are obtained (e.g., we can use decision rules as search directives); and fourth, new kinds of tasks can easily be added without requiring the development of a new preference language. Of course, task-specific short-cuts or synonyms can always be added.

Preference-based problem solving.

In this section, we show how these primitives can be mapped to basic preferences and decisions that are treated as specified in Section 3.2. This translation itself is valid for all tasks. However, tasks determine how decisions are executed, that is, which choice points are generated. The semantics of the basic decisions and preferences is thus task dependent. We now complement the semantics for high-level primitives by describing their mapping to basic decisions and preferences.

We present semantics that interpret the syntactical language constructs by an adequate mathematical structure. This structure consists of several components. First of all, it contains

• a set
  
  of decisions and
• a binary preference relation
  
  on decisions

that correspond to the basic decisions and preferences we want to obtain in the end. Decision rules, decision groups, and decision sets all regroup several basic decisions. Therefore, we interpret such a decision expression e by a subset D_e of

. For reasons of uniformity, we also treat basic decisions in this way. A domain order o for domain Dom is interpreted by a preference relation [pr ]_o ⊆ Dom × Dom. We do not require that this relation be transitive, but we expect that its transitive closure is irreflexive, that is, it represents a strict partial order.

Hence, we consider a mathematical structure consisting of a set

, a relation [pr ], a set D_e for each decision expression, a relation [pr ]_o for each domain order, and a function p_o for each prioritized domain order. Such a structure is an interpretation of a preference program if it satisfies several rules. First of all, a decision d is interpreted by a singleton containing d. A decision rule r on class C is interpreted by the set of all its instances r(i). An assignment decision set for field f is interpreted by a set containing an assignment decision a(f,v) for each domain value v. Table 2 summarizes these rules and also indicates the constraint of the chosen decisions.

Decisions

Domain orders have to respect the rules in Table 3. The predefined domain orders minFirst and maxFirst have a fixed interpretation, namely, the increasing or decreasing order on the supplied integer domain. The preference relation for prioritized domain orders is obtained by comparing the priorities of the domain values.

Domain orders

Preference and containment statements impose additional conditions that are listed in Table 4. A containment statement between a decision group g and a decision expression e means that all elements of D_e are also in D_g. A preference between two decision expressions e₁ and e₂ means that all elements of D_e1 are preferred to all elements of D_e2. When we apply a domain order o to a field f, we lift the preference relation of o to the assignment decisions of f. Because there is a single assignment decision for each domain value, this lifting is straightforward. Finally, statements specifying priorities of domain values or preferences between domain values constrain the priority function or preference relation of a domain order in an obvious way.

Preference and containment constraints

Finally, we consider only interpretations that are minimal w.r.t. the sets

, D_e, [pr ], and [pr ]_o in order to avoid the choice of irrelevant decisions and preferences. Furthermore, we introduce some pragmatic restrictions to make sure that preference statements do not change the solutions of the underlying constraint-satisfaction problem (CSP). For this purpose, we assume that the constraints are formulated in conjunctive normal form (i.e., each constraint is a disjunction of basic constraints or of their negations). We require that each of those constraints contains at most one containment-, preference-, or preferValue-constraint, and we also forbid negated occurrences of those constraints. Hence, we forbid disjunctive preferences of the form prefer(a,c) or prefer(b,c). Thus, we can guarantee that preferences do not introduce additional solutions and that their interpretation uniquely depends on the chosen solution of the underlying CSP (i.e., the problem that is obtained by removing all preference statements). However, inconsistent preferences can lead to a loss of solutions.