| 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"]; |