5. Global Constraint Catalogue

5.1. abs_value
5.2. all_differ_from_at_least_k_pos
5.3. all_equal
5.4. all_min_dist
5.5. alldifferent
5.6. alldifferent_between_sets
5.7. alldifferent_consecutive_values
5.8. alldifferent_cst
5.9. alldifferent_except_0
5.10. alldifferent_interval
5.11. alldifferent_modulo
5.12. alldifferent_on_intersection
5.13. alldifferent_partition
5.14. alldifferent_same_value
5.15. allperm
5.16. among
5.17. among_diff_0
5.18. among_interval
5.19. among_low_up
5.20. among_modulo
5.21. among_seq
5.22. among_var
5.23. and
5.24. arith
5.25. arith_or
5.26. arith_sliding
5.27. assign_and_counts
5.28. assign_and_nvalues
5.29. atleast
5.30. atleast_nvalue
5.31. atleast_nvector
5.32. atmost
5.33. atmost1
5.34. atmost_nvalue
5.35. atmost_nvector
5.36. balance
5.37. balance_interval
5.38. balance_modulo
5.39. balance_partition
5.40. between_min_max
5.41. bin_packing
5.42. bin_packing_capa
5.43. binary_tree
5.44. bipartite
5.45. calendar
5.46. cardinality_atleast
5.47. cardinality_atmost
5.48. cardinality_atmost_partition
5.49. change
5.50. change_continuity
5.51. change_pair
5.52. change_partition
5.53. circuit
5.54. circuit_cluster
5.55. circular_change
5.56. clause_and
5.57. clause_or
5.58. clique
5.59. colored_matrix
5.60. coloured_cumulative
5.61. coloured_cumulatives
5.62. common
5.63. common_interval
5.64. common_modulo
5.65. common_partition
5.66. cond_lex_cost
5.67. cond_lex_greater
5.68. cond_lex_greatereq
5.69. cond_lex_less
5.70. cond_lex_lesseq
5.71. connect_points
5.72. connected
5.73. consecutive_groups_of_ones
5.74. consecutive_values
5.75. contains_sboxes
5.76. correspondence
5.77. count
5.78. counts
5.79. coveredby_sboxes
5.80. covers_sboxes
5.81. crossing
5.82. cumulative
5.83. cumulative_convex
5.84. cumulative_product
5.85. cumulative_two_d
5.86. cumulative_with_level_of_priority
5.87. cumulatives
5.88. cutset
5.89. cycle
5.90. cycle_card_on_path
5.91. cycle_or_accessibility
5.92. cycle_resource
5.93. cyclic_change
5.94. cyclic_change_joker
5.95. dag
5.96. decreasing
5.97. deepest_valley
5.98. derangement
5.99. differ_from_at_least_k_pos
5.100. diffn
5.101. diffn_column
5.102. diffn_include
5.103. discrepancy
5.104. disj
5.105. disjoint
5.106. disjoint_sboxes
5.107. disjoint_tasks
5.108. disjunctive
5.109. distance
5.110. distance_between
5.111. distance_change
5.112. dom_reachability
5.113. domain
5.114. domain_constraint
5.115. elem
5.116. elem_from_to
5.117. element
5.118. element_greatereq
5.119. element_lesseq
5.120. element_matrix
5.121. element_product
5.122. element_sparse
5.123. elementn
5.124. elements
5.125. elements_alldifferent
5.126. elements_sparse
5.127. eq
5.128. eq_cst
5.129. eq_set
5.130. equal_sboxes
5.131. equivalent
5.132. exactly
5.133. gcd
5.134. geost
5.135. geost_time
5.136. geq
5.137. geq_cst
5.138. global_cardinality
5.139. global_cardinality_low_up
5.140. global_cardinality_low_up_no_loop
5.141. global_cardinality_no_loop
5.142. global_cardinality_with_costs
5.143. global_contiguity
5.144. golomb
5.145. graph_crossing
5.146. graph_isomorphism
5.147. group
5.148. group_skip_isolated_item
5.149. gt
5.150. highest_peak
5.151. imply
5.152. in
5.153. in_interval
5.154. in_interval_reified
5.155. in_intervals
5.156. in_relation
5.157. in_same_partition
5.158. in_set
5.159. increasing
5.160. increasing_global_cardinality
5.161. increasing_nvalue
5.162. increasing_nvalue_chain
5.163. indexed_sum
5.164. inflexion
5.165. inside_sboxes
5.166. int_value_precede
5.167. int_value_precede_chain
5.168. interval_and_count
5.169. interval_and_sum
5.170. inverse
5.171. inverse_offset
5.172. inverse_set
5.173. inverse_within_range
5.174. ith_pos_different_from_0
5.175. k_alldifferent
5.176. k_cut
5.177. k_disjoint
5.178. k_same
5.179. k_same_interval
5.180. k_same_modulo
5.181. k_same_partition
5.182. k_used_by
5.183. k_used_by_interval
5.184. k_used_by_modulo
5.185. k_used_by_partition
5.186. length_first_sequence
5.187. length_last_sequence
5.188. leq
5.189. leq_cst
5.190. lex2
5.191. lex_alldifferent
5.192. lex_between
5.193. lex_chain_less
5.194. lex_chain_lesseq
5.195. lex_different
5.196. lex_equal
5.197. lex_greater
5.198. lex_greatereq
5.199. lex_less
5.200. lex_lesseq
5.201. lex_lesseq_allperm
5.202. link_set_to_booleans
5.203. longest_change
5.204. lt
5.205. map
5.206. max_index
5.207. max_n
5.208. max_nvalue
5.209. max_size_set_of_consecutive_var
5.210. maximum
5.211. maximum_modulo
5.212. meet_sboxes
5.213. min_index
5.214. min_n
5.215. min_nvalue
5.216. min_size_set_of_consecutive_var
5.217. minimum
5.218. minimum_except_0
5.219. minimum_greater_than
5.220. minimum_modulo
5.221. minimum_weight_alldifferent
5.222. nand
5.223. nclass
5.224. neq
5.225. neq_cst
5.226. nequivalence
5.227. next_element
5.228. next_greater_element
5.229. ninterval
5.230. no_peak
5.231. no_valley
5.232. non_overlap_sboxes
5.233. nor
5.234. not_all_equal
5.235. not_in
5.236. npair
5.237. nset_of_consecutive_values
5.238. nvalue
5.239. nvalue_on_intersection
5.240. nvalues
5.241. nvalues_except_0
5.242. nvector
5.243. nvectors
5.244. open_alldifferent
5.245. open_among
5.246. open_atleast
5.247. open_atmost
5.248. open_global_cardinality
5.249. open_global_cardinality_low_up
5.250. open_maximum
5.251. open_minimum
5.252. opposite_sign
5.253. or
5.254. orchard
5.255. ordered_atleast_nvector
5.256. ordered_atmost_nvector
5.257. ordered_global_cardinality
5.258. ordered_nvector
5.259. orth_link_ori_siz_end
5.260. orth_on_the_ground
5.261. orth_on_top_of_orth
5.262. orths_are_connected
5.263. overlap_sboxes
5.264. path
5.265. path_from_to
5.266. pattern
5.267. peak
5.268. period
5.269. period_except_0
5.270. place_in_pyramid
5.271. polyomino
5.272. power
5.273. product_ctr
5.274. proper_forest
5.275. range_ctr
5.276. relaxed_sliding_sum
5.277. roots
5.278. same
5.279. same_and_global_cardinality
5.280. same_and_global_cardinality_low_up
5.281. same_intersection
5.282. same_interval
5.283. same_modulo
5.284. same_partition
5.285. same_sign
5.286. scalar_product
5.287. sequence_folding
5.288. set_value_precede
5.289. shift
5.290. size_max_seq_alldifferent
5.291. size_max_starting_seq_alldifferent
5.292. sliding_card_skip0
5.293. sliding_distribution
5.294. sliding_sum
5.295. sliding_time_window
5.296. sliding_time_window_from_start
5.297. sliding_time_window_sum
5.298. smooth
5.299. soft_all_equal_max_var
5.300. soft_all_equal_min_ctr
5.301. soft_all_equal_min_var
5.302. soft_alldifferent_ctr
5.303. soft_alldifferent_var
5.304. soft_cumulative
5.305. soft_same_interval_var
5.306. soft_same_modulo_var
5.307. soft_same_partition_var
5.308. soft_same_var
5.309. soft_used_by_interval_var
5.310. soft_used_by_modulo_var
5.311. soft_used_by_partition_var
5.312. soft_used_by_var
5.313. sort
5.314. sort_permutation
5.315. stable_compatibility
5.316. stage_element
5.317. stretch_circuit
5.318. stretch_path
5.319. stretch_path_partition
5.320. strict_lex2
5.321. strictly_decreasing
5.322. strictly_increasing
5.323. strongly_connected
5.324. subgraph_isomorphism
5.325. sum
5.326. sum_ctr
5.327. sum_free
5.328. sum_of_weights_of_distinct_values
5.329. sum_set
5.330. symmetric
5.331. symmetric_alldifferent
5.332. symmetric_cardinality
5.333. symmetric_gcc
5.334. temporal_path
5.335. tour
5.336. track
5.337. tree
5.338. tree_range
5.339. tree_resource
5.340. two_layer_edge_crossing
5.341. two_orth_are_in_contact
5.342. two_orth_column
5.343. two_orth_do_not_overlap
5.344. two_orth_include
5.345. used_by
5.346. used_by_interval
5.347. used_by_modulo
5.348. used_by_partition
5.349. uses
5.350. valley
5.351. vec_eq_tuple
5.352. visible
5.353. weighted_partial_alldiff
5.354. xor

5.288. set_value_precede

DESCRIPTION

LINKS

Origin

[YatChiuLawJimmyLee04]

Constraint

$𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎 (𝚂, 𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

$𝚂$	$𝚒𝚗𝚝$
$𝚃$	$𝚒𝚗𝚝$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚜𝚟𝚊𝚛)$

Restrictions

𝚂 \neq 𝚃

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

If there exists a set variable $v_{1}$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ such that $𝚂$ does not belong to $v_{1}$ and $𝚃$ does, then there also exists a set variable $v_{2}$ preceding $v_{1}$ such that $𝚂$ belongs to $v_{2}$ and $𝚃$ does not.

Example

(\begin{matrix} 2, 1, 〈\begin{matrix} 𝚟𝚊𝚛 - {0, 2}, \\ 𝚟𝚊𝚛 - {0, 1}, \\ 𝚟𝚊𝚛 - \emptyset, \\ 𝚟𝚊𝚛 - {1} \end{matrix}〉 \end{matrix})

The $𝚜𝚎𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ constraint holds since the first occurrence of value 2 precedes the first occurrence of value 1.

Algorithm

A filtering algorithm for maintaining value precedence on a sequence of set variables is presented in [YatChiuLawJimmyLee04]. Its complexity is linear to the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

See also

specialisation: $𝚒𝚗𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎$ ( $𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ of $𝚜𝚎𝚝 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ replaced by $𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎$ of $𝚍𝚘𝚖𝚊𝚒𝚗 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

Keywords

constraint arguments: constraint involving set variables.

constraint type: order constraint.

symmetry: symmetry, indistinguishable values, value precedence.

Global Constraint Catalog

5. Global Constraint Catalogue

5.288. set_value_precede

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