this repo has no description
dekker.one
1/***
2!Test
3expected:
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
45include "globals.mzn";
46
47%-----------------------------------------------------------------------------
48% Specification
49
50int: n_names;
51int: n_prefs;
52array[1..n_prefs,1..2] of int: prefs;
53
54% Instance
55
56n_names = 9;
57n_prefs = 17;
58prefs = 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
66array[1..n_names] of var 0..n_names-1: pos;
67var 0..n_names-1: satisfies;
68
69array[1..n_prefs] of var bool: ful;
70
71constraint
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
80constraint
81 sum (i in 1..n_prefs) (bool2int(ful[i])) = satisfies;
82
83constraint
84 alldifferent(pos);
85
86% Break some symmetry
87constraint
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.
98solve :: int_search(pos, first_fail, indomain, complete)
99 maximize satisfies;
100
101output ["Positions: ", show(pos), "\n",
102 "Preferences satisfied: ", show(satisfies), "\n"];