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