5.66. cond_lex_cost

DESCRIPTIONLINKSAUTOMATON
Origin

Inspired by [WallaceWilson06].

Constraint

πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝(πš…π™΄π™²πšƒπ™Ύπš,π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,π™²π™Ύπš‚πšƒ)

Type
πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Arguments
πš…π™΄π™²πšƒπ™ΎπšπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšπšžπš™πš•πšŽ-πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚)
π™²π™Ύπš‚πšƒπšπšŸπšŠπš›
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚,πšŸπšŠπš•)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄π™²πšƒπ™Ύπš,πšŸπšŠπš›)
|πš…π™΄π™²πšƒπ™Ύπš|=|πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,πšπšžπš™πš•πšŽ)
πšœπšŠπš–πšŽ_πšœπš’πš£πšŽ(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,πšπšžπš™πš•πšŽ)
πšπš’πšœπšπš’πš—πšŒπš(π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄,[])
πš’πš—_πš›πšŽπš•πšŠπšπš’πš˜πš—(πš…π™΄π™²πšƒπ™Ύπš,π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄)
π™²π™Ύπš‚πšƒβ‰₯1
π™²π™Ύπš‚πšƒβ‰€|π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄|
Purpose

πš…π™΄π™²πšƒπ™Ύπš is assigned to the π™²π™Ύπš‚πšƒ th item of the collection π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.

Example
0,1,πšπšžπš™πš•πšŽ-1,0,πšπšžπš™πš•πšŽ-0,1,πšπšžπš™πš•πšŽ-0,0,πšπšžπš™πš•πšŽ-1,1,2

The πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 constraint holds since πš…π™΄π™²πšƒπ™Ύπš is assigned to the second item of the collection π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.

Typical
|πšƒπš„π™Ώπ™»π™΄_𝙾𝙡_πš…π™°π™»πš‚|>1
|πš…π™΄π™²πšƒπ™Ύπš|>1
|π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄|>1
Symmetries
  • Items of πš…π™΄π™²πšƒπ™Ύπš and π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ are permutable (same permutation used).

  • All occurrences of two distinct tuples of values in πš…π™΄π™²πšƒπ™Ύπš or π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ can be swapped; all occurrences of a tuple of values in πš…π™΄π™²πšƒπ™Ύπš or π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄.πšπšžπš™πš•πšŽ can be renamed to any unused tuple of values.

Usage

We consider an example taken fromΒ [WallaceWilson06] were a customer has to decide among vacations. There are two seasons when he can travel (πšœπš™πš›πš’πš—πš and πšœπšžπš–πš–πšŽπš›) and two locations π™½πšŠπš™πš•πšŽπšœ and π™·πšŽπš•πšœπš’πš—πš”πš’. Furthermore assume that location is more important than season and the preferred period of the year depends on the selected location. The travel preferences of a customer are explicitly defined by stating the preferences ordering among the possible tuples of values βŒ©π™½πšŠπš™πš•πšŽπšœ,πšœπš™πš›πš’πš—πšβŒͺ, βŒ©π™½πšŠπš™πš•πšŽπšœ,πšœπšžπš–πš–πšŽπš›βŒͺ, βŒ©π™·πšŽπš•πšœπš’πš—πš”πš’,πšœπš™πš›πš’πš—πšβŒͺ and βŒ©π™·πšŽπš•πšœπš’πš—πš”πš’,πšœπšžπš–πš–πšŽπš›βŒͺ. For instance we may state within the preference table π™Ώπšπ™΄π™΅π™΄πšπ™΄π™½π™²π™΄_πšƒπ™°π™±π™»π™΄ of the πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 constraint the preference ordering βŒ©π™½πšŠπš™πš•πšŽπšœ,πšœπš™πš›πš’πš—πšβŒͺβ‰»βŒ©π™·πšŽπš•πšœπš’πš—πš”πš’,πšœπšžπš–πš–πšŽπš›βŒͺβ‰»βŒ©π™·πšŽπš•πšœπš’πš—πš”πš’,πšœπš™πš›πš’πš—πšβŒͺβ‰»βŒ©π™½πšŠπš™πš•πšŽπšœ,πšœπšžπš–πš–πšŽπš›βŒͺ, which denotes the fact that our customer prefers π™½πšŠπš™πš•πšŽπšœ in the πšœπš™πš›πš’πš—πš and π™·πšŽπš•πšœπš’πš—πš”πš’ in the πšœπšžπš–πš–πšŽπš›, and a vacation in πšœπš™πš›πš’πš—πš is preferred over πšœπšžπš–πš–πšŽπš›. Finally a solution minimising the cost variable π™²π™Ύπš‚πšƒ will match the preferences stated by our customer.

See also

attached to cost variant: πš’πš—_πš›πšŽπš•πšŠπšπš’πš˜πš—Β (π™²π™Ύπš‚πšƒ parameter removed).

common keyword: πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›, πšŒπš˜πš—πš_πš•πšŽπš‘_πšπš›πšŽπšŠπšπšŽπš›πšŽπšš, πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœ, πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπššΒ (preferences).

specialisation: πšŽπš•πšŽπš–πšŽπš—πšΒ (πšπšžπš™πš•πšŽ of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ replaced by single πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

characteristic of a constraint: vector, automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: order constraint.

filtering: arc-consistency, cost filtering constraint.

modelling: preferences.

symmetry: lexicographic order.

Automaton

FigureΒ 5.66.1 depicts the automaton associated with πšŒπš˜πš—πš_πš•πšŽπš‘_πš•πšŽπšœπšœπšŽπšš constraint. Let πš…π™°πš k denote the πšŸπšŠπš› attribute of the k th item of the πš…π™΄π™²πšƒπ™Ύπš collection. FigureΒ 5.66.2 depicts the reformulation of the πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 constraint.

Figure 5.66.1. Automaton of the πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 constraint given in the example
ctrs/cond_lex_cost1
Figure 5.66.2. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš˜πš—πš_πš•πšŽπš‘_𝚌𝚘𝚜𝚝 constraint
ctrs/cond_lex_cost2