Debian Codegraph @

tests/spec/examples/photo.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 ful: [false, false, false, true, false, true, false, false, true, false, false, false, true, true, true, true, true]
7 objective: 8
8 pos: [0, 1, 4, 3, 2, 8, 5, 6, 7]
9 satisfies: 8
10 - !Result
11 solution: !Solution
12 ful: [false, true, true, false, true, false, false, false, false, true, true, false, false, true, true, false, true]
13 objective: 8
14 pos: [3, 8, 6, 0, 2, 1, 5, 4, 7]
15 satisfies: 8
16 - !Result
17 solution: !Solution
18 ful: [false, true, false, false, false, false, false, true, false, false, true, false, true, true, true, true, true]
19 objective: 8
20 pos: [1, 3, 4, 2, 0, 8, 5, 6, 7]
21 satisfies: 8
22 - !Result
23 solution: !Solution
24 ful: [false, true, true, false, true, true, false, false, true, false, true, false, false, true, false, true, false]
25 objective: 8
26 pos: [5, 8, 2, 3, 4, 0, 1, 6, 7]
27 satisfies: 8
28 ***/
29
30 %-----------------------------------------------------------------------------
31 % Placing people on a photo
32 %
33 % Guido Tack
34 % 2007-02-22
35 %
36 % Ported from the Gecode example
37 %
38 %-----------------------------------------------------------------------------
39
40 % A group of people wants to take a group photo. Each person can give
41 % preferences next to whom he or she wants to be placed on the
42 % photo. The problem to be solved is to find a placement that
43 % satisfies as many preferences as possible.
44
45 include "globals.mzn";
46
47 %-----------------------------------------------------------------------------
48 % Specification
49
50 int: n_names;
51 int: n_prefs;
52 array[1..n_prefs,1..2] of int: prefs;
53
54 % Instance
55
56 n_names = 9;
57 n_prefs = 17;
58 prefs = array2d(1..n_prefs, 1..2,
59 [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 |
60 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |]
61 );
62
63 %-----------------------------------------------------------------------------
64 % Model
65
66 array[1..n_names] of var 0..n_names-1: pos;
67 var 0..n_names-1: satisfies;
68
69 array[1..n_prefs] of var bool: ful;
70
71 constraint
72 forall (i in 1..n_prefs) (
73 let {
74 int: pa = prefs[i,1],
75 int: pb = prefs[i,2]
76 } in
77 ful[i] = (pos[pb]-pos[pa] == 1 xor pos[pa]-pos[pb] == 1)
78 );
79
80 constraint
81 sum (i in 1..n_prefs) (bool2int(ful[i])) = satisfies;
82
83 constraint
84 alldifferent(pos);
85
86 % Break some symmetry
87 constraint
88 pos[1] < pos[2];
89
90 % Justification for annotation, from Guido:
91 % I've had a closer look at the FlatZinc file for photo again. The real
92 % problem is branching! Currently, if nothing is annotated, I branch on
93 % all the variables, just naively in the order they're given in the source
94 % file. For photo, this is apparently the worst you can do. You have to
95 % branch on the pos array (that's what the Gecode version does), but this
96 % array appears only after loads of Boolean variables. I've added a
97 % search annotation to photo.mzn, which should solve this issue.
98 solve :: int_search(pos, first_fail, indomain, complete)
99 maximize satisfies;
100
101 output ["Positions: ", show(pos), "\n",
102 "Preferences satisfied: ", show(satisfies), "\n"];