this repo has no description
dekker.one
1include "alldifferent.mzn";
2
3/** @group globals
4 Constrains the elements of \a x to define a circuit where \a x[\p i] = \p j means
5 that \p j is the successor of \p i.
6*/
7% Linear version.
8predicate fzn_circuit(array[int] of var int: x) =
9 let { set of int: S = index_set(x),
10 int: l = min(S),
11 int: u = max(S),
12 int: n = card(S),
13 constraint forall( i in S )( x[i] in S diff {i} ), %% Self-mapping and exclude i->i before alldifferent
14 } in
15 alldifferent(x) /\
16% alldifferent(order) /\
17 if nMZN__fSECcuts>0 then
18 let {
19 array [int, int] of var int: eq_x = eq_encode( x ),
20 constraint assert( l==min( index_set_2of2( eq_x ) ), "circuit: index set mismatch" ), %% self-mapping
21 constraint assert( u==max( index_set_2of2( eq_x ) ), "circuit: index set mismatch" ),
22 } in
23 circuit__SECcuts( eq_x )
24 else true endif /\
25 if nMZN__fSECcuts<2 then
26 %%% MTZ model. Note that INTEGER order vars seem better!:
27 let {
28 array[l+1..l+n-1] of var 2..n: order,
29 } in
30 forall (i,j in l+1..l+n-1 where i!=j /\ j in dom(x[i])) (
31 order[i] - order[j] + (n-1)* bool2int(x[i]==j)
32 + (n-3)*bool2int(x[j]==i) %% the Desrochers & Laporte '91 term
33 %%%% --- strangely enough it is much worse on vrp-s2-v2-c7_vrp-v2-c7_det_ADAPT_1_INVERSE.mzn!
34 <= n-2 )
35 else true endif
36 %% ... but seems improved with this (leaving also for SEC)
37 /\ if n>2 then forall (i,j in S where i<j) ( x[i]!=j \/ x[j]!=i ) %% Only this improves overall with DL'91
38 else true endif
39 ;
40
41%-----------------------------------------------------------------------------%
42predicate circuit__SECcuts(array[int,int] of var int: x); %% passed on
43%-----------------------------------------------------------------------------%