5.234. link_set_to_booleans

DESCRIPTIONLINKSGRAPH
Origin

Inspired by πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš.

Constraint

πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ(πš‚πš…π™°πš,π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚)

Arguments
πš‚πš…π™°πšπšœπšŸπšŠπš›
π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš‹πš˜πš˜πš•-πšπšŸπšŠπš›,πšŸπšŠπš•-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚,[πš‹πš˜πš˜πš•,πšŸπšŠπš•])
π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚.πš‹πš˜πš˜πš•β‰₯0
π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚.πš‹πš˜πš˜πš•β‰€1
πšπš’πšœπšπš’πš—πšŒπš(π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚,πšŸπšŠπš•)
Purpose

Make the link between a set variable πš‚πš…π™°πš and those 0-1 variables that are associated with each potential value belonging to πš‚πš…π™°πš: The 0-1 variables, which are associated with a value belonging to the set variable πš‚πš…π™°πš, are equal to 1, while the remaining 0-1 variables are all equal to 0.

Example
{1,3,4},πš‹πš˜πš˜πš•-0πšŸπšŠπš•-0,πš‹πš˜πš˜πš•-1πšŸπšŠπš•-1,πš‹πš˜πš˜πš•-0πšŸπšŠπš•-2,πš‹πš˜πš˜πš•-1πšŸπšŠπš•-3,πš‹πš˜πš˜πš•-1πšŸπšŠπš•-4,πš‹πš˜πš˜πš•-0πšŸπšŠπš•-5

In the example, the 0-1 variables associated with the values 1, 3 and 4 are all set to 1, while the other 0-1 variables are set to 0. Consequently, the πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ constraint holds since its first argument πš‚πš…π™°πš is set to {1,3,4}.

Typical
|π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚|>1
πš›πšŠπš—πšπšŽ(π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚.πš‹πš˜πš˜πš•)>1
Symmetry

Items of π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚ are permutable.

Usage

This constraint is used in order to make the link between a formulation using set variables and a formulation based on linear programming.

Systems

channel in Gecode, link_set_to_booleans in MiniZinc.

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜, πšŒπš•πš’πššπšžπšŽΒ (constraint involving set variables), πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πšΒ (channelling constraint), πš”_𝚌𝚞𝚝, πš™πšŠπšπš‘_πšπš›πš˜πš–_𝚝𝚘, πš›πš˜πš˜πšπšœ, πšœπšπš›πš˜πš—πšπš•πš’_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš, πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’, πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_𝚐𝚌𝚌, πšπš˜πšžπš›Β (constraint involving set variables).

Keywords

characteristic of a constraint: derived collection.

constraint arguments: constraint involving set variables.

constraint type: decomposition, value constraint.

filtering: linear programming.

modelling: channelling constraint, set channel.

Derived Collection
πšŒπš˜πš•πš‚π™΄πšƒ-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš—πšŽ-πš’πš—πš,πšœπšŽπšπšŸπšŠπš›-πšœπšŸπšŠπš›),πš’πšπšŽπš–(πš˜πš—πšŽ-1,πšœπšŽπšπšŸπšŠπš›-πš‚πš…π™°πš)]
Arc input(s)

πš‚π™΄πšƒ π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝,πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ)

Arc arity
Arc constraint(s)
πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ.πš‹πš˜πš˜πš•=𝚜𝚎𝚝.πš˜πš—πšŽβ‡”πš’πš—_𝚜𝚎𝚝(πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ.πšŸπšŠπš•,𝚜𝚎𝚝.πšœπšŽπšπšŸπšŠπš›)
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚|

Graph model

The πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ constraint is modelled with the following bipartite graph. The first set of vertices corresponds to a single vertex containing the set variable. The second class of vertices contains one vertex for each item of the collection π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚. The arc constraint between the set variable πš‚πš…π™°πš and one potential value v of the set variable expresses the following:

  • If the 0-1 variable associated with v is equal to 1 then v should belong to πš‚πš…π™°πš.

  • Otherwise if the 0-1 variable associated with v is equal to 0 then v should not belong to πš‚πš…π™°πš.

Since all arc constraints should hold the final graph contains exactly |π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚| arcs.

PartsΒ (A) andΒ (B) of FigureΒ 5.234.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold. The πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ constraint holds since the final graph contains exactly 6 arcs (one for each 0-1 variable).

Figure 5.234.1. Initial and final graph of the πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœ constraint
ctrs/link_set_to_booleansA
(a)
ctrs/link_set_to_booleansB
(b)
Signature

Since the initial graph contains |π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚| arcs the maximum number of arcs of the final graph is equal to |π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚|. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚| to 𝐍𝐀𝐑𝐂β‰₯|π™±π™Ύπ™Ύπ™»π™΄π™°π™½πš‚| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.