3. Description of the Catalogue

3.1. Which global constraints are included?
3.2. Which global constraints are missing?
3.3. Searching in the catalogue
3.4. Figures of the catalogue
3.5. Constraints argument patterns
- 3.5.1. Constraints with 1 argument
- 3.5.2. Constraints with 2 arguments
- 3.5.3. Constraints with 3 arguments
- 3.5.4. Constraints with 4 arguments
- 3.5.5. Constraints with 5 arguments
- 3.5.6. Constraints with 6 arguments
- 3.5.7. Constraints with 8 arguments
- 3.5.8. Constraints with 10 arguments
3.6. Meta-keywords attached to the keywords
- 3.6.1. Application area
- 3.6.2. Characteristic of a constraint
- 3.6.3. Combinatorial object
- 3.6.4. Complexity
- 3.6.5. Constraint network structure
- 3.6.6. Constraint type
- 3.6.7. Constraint arguments
- 3.6.8. Filtering
- 3.6.9. Final graph structure
- 3.6.10. Geometry
- 3.6.11. Heuristics
- 3.6.12. Miscellaneous
- 3.6.13. Modelling
- 3.6.14. Modelling exercises
- 3.6.15. Problems
- 3.6.16. Puzzles
- 3.6.17. Symmetry
3.7. Keywords attached to the global constraints
- 3.7.1. 3-dimensional-matching
- 3.7.2. 3-SAT
- 3.7.3. Abstract interpretation
- 3.7.4. Acyclic
- 3.7.5. Air traffic management
- 3.7.6. Alignment
- 3.7.7. All different
- 3.7.8. Alpha-acyclic constraint network(2)
- 3.7.9. Alpha-acyclic constraint network(3)
- 3.7.10. Apartition
- 3.7.11. Arc-consistency
- 3.7.12. Arithmetic constraint
- 3.7.13. Array constraint
- 3.7.14. Assigning and scheduling tasks that run in parallel
- 3.7.15. Assignment
- 3.7.16. Assignment dimension
- 3.7.17. Assignment to the same set of values
- 3.7.18. At least
- 3.7.19. At most
- 3.7.20. Automaton
- 3.7.21. Automaton with array of counters
- 3.7.22. Automaton with counters
- 3.7.23. Automaton without counters
- 3.7.24. Autoref
- 3.7.25. Balanced assignment
- 3.7.26. Balanced tree
- 3.7.27. Berge-acyclic constraint network
- 3.7.28. Binary constraint
- 3.7.29. Bioinformatics
- 3.7.30. Bipartite
- 3.7.31. Bipartite matching
- 3.7.32. Bipartite matching in convex bipartite graphs
- 3.7.33. Boolean channel
- 3.7.34. Boolean constraint
- 3.7.35. Border
- 3.7.36. Bound-consistency
- 3.7.37. Business rules
- 3.7.38. Centered cyclic(1) constraint network(1)
- 3.7.39. Centered cyclic(2) constraint network(1)
- 3.7.40. Centered cyclic(3) constraint network(1)
- 3.7.41. Channel routing
- 3.7.42. Channelling constraint
- 3.7.43. Circuit
- 3.7.44. Circular sliding cyclic(1) constraint network(2)
- 3.7.45. Cluster
- 3.7.46. Coloured
- 3.7.47. Compulsory part
- 3.7.48. Conditional constraint
- 3.7.49. Configuration problem
- 3.7.50. Connected component
- 3.7.51. Consecutive loops are connected
- 3.7.52. Consecutive values
- 3.7.53. Constraint between two collections of variables
- 3.7.54. Constraint between three collections of variables
- 3.7.55. Constraint involving set variables
- 3.7.56. Constraint on the intersection
- 3.7.57. Constructive disjunction
- 3.7.58. Contact
- 3.7.59. Convex
- 3.7.60. Convex bipartite graph
- 3.7.61. Convex hull relaxation
- 3.7.62. Conway packing problem
- 3.7.63. Core
- 3.7.64. Costas arrays
- 3.7.65. Cost filtering constraint
- 3.7.66. Cost matrix
- 3.7.67. Counting constraint
- 3.7.68. Cumulative longest hole problems
- 3.7.69. Cycle
- 3.7.70. Cyclic
- 3.7.71. Data constraint
- 3.7.72. Deadlock breaking
- 3.7.73. Decomposition
- 3.7.74. Decomposition-based violation measure
- 3.7.75. DFS-bottleneck
- 3.7.76. Demand profile
- 3.7.77. Degree of diversity of a set of solutions
- 3.7.78. Derived collection
- 3.7.79. Difference
- 3.7.80. Difference between pairs of variables
- 3.7.81. Directed acyclic graph
- 3.7.82. Disequality
- 3.7.83. Disjunction
- 3.7.84. Domain channel
- 3.7.85. Domain definition
- 3.7.86. Dominating queens
- 3.7.87. Domination
- 3.7.88. Dual model
- 3.7.89. Duplicated variables
- 3.7.90. Dynamic programming
- 3.7.91. Empty intersection
- 3.7.92. Entailment
- 3.7.93. Equality
- 3.7.94. Equality between multisets
- 3.7.95. Equivalence
- 3.7.96. Euler knight
- 3.7.97. Excluded
- 3.7.98. Extension
- 3.7.99. Facilities location problem
- 3.7.100. Floor planning problem
- 3.7.101. Flow
  - 3.7.101.1. Flow models for $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚘𝚙𝚎𝚗_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$
  - 3.7.101.2. Flow models for $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ , $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙_𝚗𝚘_𝚕𝚘𝚘𝚙$
  - 3.7.101.3. Flow models for $𝚞𝚜𝚎𝚍_𝚋𝚢$ , $𝚜𝚊𝚖𝚎$
  - 3.7.101.4. Flow model for $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$
- 3.7.102. Frequency allocation problem
- 3.7.103. Functional dependency
- 3.7.104. Geometrical constraint
- 3.7.105. Golomb ruler
- 3.7.106. Graph colouring
- 3.7.107. Graph constraint
- 3.7.108. Graph partitioning constraint
- 3.7.109. Guillotine cut
- 3.7.110. Hall interval
- 3.7.111. Hamiltonian
- 3.7.112. Heuristics
- 3.7.113. Heuristics and Berge-acyclic constraint network
- 3.7.114. Heuristics and lexicographical ordering
- 3.7.115. Heuristics for two-dimensional rectangle placement problems
  - 3.7.115.1. Dual strategy for rectangle placement problems with no slack
  - 3.7.115.2. Strategy that gradually creates a compulsory part
- 3.7.116. Hungarian method for the assignment problem
- 3.7.117. Hybrid-consistency
- 3.7.118. Hypergraph
- 3.7.119. Included
- 3.7.120. Inclusion
- 3.7.121. Incompatible pairs of values
- 3.7.122. Indistinguishable values
- 3.7.123. Interval
- 3.7.124. Joker value
- 3.7.125. Klee's measure problem
- 3.7.126. Latin square
- 3.7.127. Lexicographic order
- 3.7.128. Limited discrepancy search
- 3.7.129. Linear programming
- 3.7.130. Line-segments intersection
- 3.7.131. Logic
- 3.7.132. Logigraphe
- 3.7.133. Magic hexagon
- 3.7.134. Magic series
- 3.7.135. Magic square
- 3.7.136. Matching
- 3.7.137. Matrix
- 3.7.138. Matrix model
- 3.7.139. Matrix symmetry
- 3.7.140. Maximum
- 3.7.141. Maximum clique
- 3.7.142. Maximum number of occurrences
- 3.7.143. maxint
- 3.7.144. Metro
- 3.7.145. Minimum
- 3.7.146. Minimum cost flow
- 3.7.147. Minimum feedback vertex set
- 3.7.148. Minimum hitting set cardinality
- 3.7.149. Minimum number of occurrences
- 3.7.150. Modulo
- 3.7.151. Multiset
- 3.7.152. Multiset ordering
- 3.7.153. No cycle
- 3.7.154. No loop
- 3.7.155. n-Amazon
- 3.7.156. n-queen
- 3.7.157. Non-deterministic automaton
- 3.7.158. Non-overlapping
- 3.7.159. Number of changes
- 3.7.160. Number of distinct equivalence classes
- 3.7.161. Number of distinct values
- 3.7.162. Obscure
- 3.7.163. One succ
- 3.7.164. Open automaton constraint
- 3.7.165. Open constraint
- 3.7.166. Order constraint
- 3.7.167. Orthotope
- 3.7.168. Overlapping alldifferent
- 3.7.169. Pair
- 3.7.170. Packing almost squares
- 3.7.171. Pallet loading
- 3.7.172. Partition
- 3.7.173. Path
- 3.7.174. Partridge
- 3.7.175. Pattern sequencing
- 3.7.176. Pentomino
- 3.7.177. Periodic
- 3.7.178. Permutation
- 3.7.179. Permutation channel
- 3.7.180. Phi-tree
- 3.7.181. Phylogeny
- 3.7.182. Pick-up delivery
- 3.7.183. Planarity test
- 3.7.184. Polygon
- 3.7.185. Positioning constraint
- 3.7.186. Predefined constraint
- 3.7.187. Preferences
- 3.7.188. Producer-consumer
- 3.7.189. Product
- 3.7.190. Program verification
- 3.7.191. Proximity constraint
- 3.7.192. Quadtree
- 3.7.193. Range
- 3.7.194. Rank
- 3.7.195. RCC8
- 3.7.196. Reified automaton constraint
- 3.7.197. Reified constraint
- 3.7.198. Relation
- 3.7.199. Relaxation
- 3.7.200. Relaxation dimension
- 3.7.201. Rectangle clique partition
- 3.7.202. Resource constraint
- 3.7.203. Run of a permutation
- 3.7.204. SAT
- 3.7.205. Scalar product
- 3.7.206. Sequence
- 3.7.207. Sequence dependent set-up
- 3.7.208. Sequencing with release times and deadlines
- 3.7.209. Set channel
- 3.7.210. Set packing
- 3.7.211. Shikaku
- 3.7.212. Scheduling constraint
- 3.7.213. Scheduling with machine choice, calendars and preemption
- 3.7.214. Shared table
- 3.7.215. Schur number
- 3.7.216. SLAM problem
- 3.7.217. Sliding cyclic(1) constraint network(1)
- 3.7.218. Sliding cyclic(1) constraint network(2)
- 3.7.219. Sliding cyclic(1) constraint network(3)
- 3.7.220. Sliding cyclic(2) constraint network(2)
- 3.7.221. Sliding sequence constraint
- 3.7.222. Smallest square for packing consecutive dominoes
- 3.7.223. Smallest rectangle area
- 3.7.224. Smallest square for packing rectangles with distinct sizes
- 3.7.225. Soft constraint
- 3.7.226. Sort
- 3.7.227. Sparse functional dependency
- 3.7.228. Sparse table
- 3.7.229. Sport timetabling
- 3.7.230. Squared squares
- 3.7.231. Statistics
- 3.7.232. Strip packing
- 3.7.233. Strong bridge
- 3.7.234. Strong articulation point
- 3.7.235. Strongly connected component
- 3.7.236. Subset sum
- 3.7.237. Sudoku
- 3.7.238. Sum
- 3.7.239. Sweep
- 3.7.240. Symmetry
- 3.7.241. Symmetric
- 3.7.242. System of constraints
- 3.7.243. Table
- 3.7.244. Temporal constraint
- 3.7.245. Ternary constraint
- 3.7.246. Timetabling constraint
- 3.7.247. Time window
- 3.7.248. Touch
- 3.7.249. Tree
- 3.7.250. Tuple
- 3.7.251. Two-dimensional orthogonal packing
- 3.7.252. Unary constraint
- 3.7.253. Undirected graph
- 3.7.254. Value constraint
- 3.7.255. Value partitioning constraint
- 3.7.256. Value precedence
- 3.7.257. Variable-based violation measure
- 3.7.258. Variable indexing
- 3.7.259. Variable subscript
- 3.7.260. Vector
- 3.7.261. Vpartition
- 3.7.262. Weighted assignment
- 3.7.263. Workload covering
- 3.7.264. Zebra puzzle
- 3.7.265. Zero-duration task

3.7.101.4. Flow model for $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$

Figure 3.7.25 presents a flow model for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint. Blue arcs represent a feasible flow corresponding to the solution $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ $(〈 x_{1} = 2, x_{2} = 4, x_{4} = 〉, 〈 y_{1} = 2, y_{2} = 4, y_{3} = 4 〉, 〈 𝚟𝚊𝚕 - 1 𝚘𝚖𝚒𝚗 - 0 𝚘𝚖𝚊𝚡 - 1, 𝚟𝚊𝚕 - 2 𝚘𝚖𝚒𝚗 - 1 𝚘𝚖𝚊𝚡 - 2, 𝚟𝚊𝚕 - 3 𝚘𝚖𝚒𝚗 - 0 𝚘𝚖𝚊𝚡 - 3, 𝚟𝚊𝚕 - 4 𝚘𝚖𝚒𝚗 - 2 𝚘𝚖𝚊𝚡 - 3, 𝚟𝚊𝚕 - 5 𝚘𝚖𝚒𝚗 - 0 𝚘𝚖𝚊𝚡 - 2, 𝚟𝚊𝚕 - 6 𝚘𝚖𝚒𝚗 - 0 𝚘𝚖𝚊𝚡 - 1 〉)$ , while pink arcs correspond to arcs that cannot carry any flow if the constraint has a solution. The assignment $x_{1} = 1$ is forbidden since $1 \notin 𝑑𝑜𝑚 (y_{1}) \cup 𝑑𝑜𝑚 (y_{2}) \cup 𝑑𝑜𝑚 (y_{3})$ . Consequently $x_{1} = 2$ and, since $y_{1}$ is the only variable of ${y_{1}, y_{2}, y_{3}}$ that can be assigned value 2, the assignment $y_{1} = 3$ is forbidden. Now since $3 \notin 𝑑𝑜𝑚 (y_{1}) \cup 𝑑𝑜𝑚 (y_{2}) \cup 𝑑𝑜𝑚 (y_{3})$ the assignment $x_{2} = 3$ is also forbidden. $x_{3} = 6$ is forbidden since $6 \notin 𝑑𝑜𝑚 (y_{1}) \cup 𝑑𝑜𝑚 (y_{2}) \cup 𝑑𝑜𝑚 (y_{3})$ . Finally $x_{3} = 5$ and $y_{3} = 5$ are also forbidden since value 4 must be assigned to at least two variables.

Figure 3.7.25. Flow model for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint described in table 3.7.25.

ctrs/flow_same_and_global_cardinality_low_up

**Table 3.7.25.** Domains of the variables and minimum and maximum number of occurrences of each value for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint of Figure 3.7.25.
$i$	$𝑑𝑜𝑚 (x_{i})$	$i$	$𝑑𝑜𝑚 (y_{i})$	$i$	$[{𝑜𝑚𝑖𝑛}_{i}, {𝑜𝑚𝑎𝑥}_{i}]$	$i$	$[{𝑜𝑚𝑖𝑛}_{i}, {𝑜𝑚𝑎𝑥}_{i}]$
1	${1, 2}$	1	${2, 3}$	1	$[0, 1]$	4	$[2, 3]$
2	${3, 4}$	2	${4, 5}$	2	$[1, 2]$	5	$[0, 2]$
3	${4, 5, 6}$	3	${4, 5}$	3	$[0, 3]$	6	$[0, 1]$

Global Constraint Catalog

3. Description of the Catalogue

3.7.101.4. Flow model for $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$

Figure 3.7.25. Flow model for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint described in table 3.7.25.

Table 3.7.25. Domains of the variables and minimum and maximum number of occurrences of each value for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint of Figure 3.7.25.

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

3. Description of the Catalogue

3.7.101.4. Flow model for 𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙

Figure 3.7.25. Flow model for the 𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙 constraint described in table 3.7.25.

Table 3.7.25. Domains of the variables and minimum and maximum number of occurrences of each value for the 𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙 constraint of Figure 3.7.25.

W3C: XHTML - last update: 2010-12-6. SD.

3.7.101.4. Flow model for $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$

Figure 3.7.25. Flow model for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint described in table 3.7.25.

Table 3.7.25. Domains of the variables and minimum and maximum number of occurrences of each value for the $𝚜𝚊𝚖𝚎_𝚊𝚗𝚍_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢_𝚕𝚘𝚠_𝚞𝚙$ constraint of Figure 3.7.25.