The exercise is:
A group of n people wants to take a group photo. Each person can give preferences next to whom he or she wants to be placed on the photo. The problem to be solved is to find a placement that satisfies maximum number of preferences.
The code I have written so far:
include "globals.mzn";
% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of var 1..n: prefs;
% FDV:s
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement)
% MORE Constraints
solve maximize cost;
output [show( photo_arrangement )]
n is the number of persons in the photo
n_prefs is the number of preferences
prefs is the matrix containing all the preferences
The main idea is to have a an array containing the persons 1 to n, and a cost variable that we want to maximize. How can I change the cost variable depending on the preferences?
Here is one approach. (Update: Actually, here are now three different models with the same underlying idea.)
include "globals.mzn";
% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;
% FDV:s
array [1..n] of var 1..n: photo_arrangement;
% the positions of each person in photo_arrangement
array [1..n] of var 1..n: pa_inv = inverse(photo_arrangement);
% to see what preferences that are satisfied
array[1..n_prefs] of var int: prefs_sat;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement)
/\
forall(p in 1..n_prefs) (
% note: we use the inverse of photo_arrangement for indexing since we
% want to compare the positions of the two persons prefs[p,1] and prefs[p,2]
prefs_sat[p] = if abs(pa_inv[prefs[p,1]]-pa_inv[prefs[p,2]]) = 1 then 1 else 0 endif
)
/\
cost = sum(prefs_sat)
;
solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;
output [
"cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n(pa_inv: \(pa_inv))\n"
] ++
[
show([prefs[p,i] | i in 1..2]) ++ ": " ++ show(prefs_sat[p]) ++ "\n"
| p in 1..n_prefs
];
% data
n = 9;
n_prefs = 17;
prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];
The main point is the use of an extra array (pa_inv) which is the inverse of photo_arrangement and shows the position for each person. This means that we can use pa_inv[1] to get the position of person 1, and thus can calculate the difference of the positions of pa_inv[prefs[p,1] and pa_inv[prefs[p,2] (which is 1 if the two persons is between each other). The prefs_sat array shows if a preference is satisfied (1) or not (0).
There are 20 optimal solutions with 10 satisfied preferences. One optimal solutions is:
cost: 10
photo_arrangement: [2, 5, 1, 4, 3, 7, 8, 9, 6]
(pa_inv: [3, 1, 5, 4, 2, 9, 6, 7, 8])
[1, 3]: 0
[1, 5]: 1
[1, 8]: 0
[2, 5]: 1
[2, 9]: 0
[3, 4]: 1
[3, 5]: 0
[4, 1]: 1
[4, 5]: 0
[5, 6]: 0
[5, 1]: 1
[6, 1]: 0
[6, 9]: 1
[7, 3]: 1
[7, 8]: 1
[8, 9]: 1
[8, 7]: 1
Update some minutes later:
Here is another approach using the element function instead of using inverse, which means that we don't need the pa_inv array. The forall loop in the code above can be replaced with:
%
forall(p in 1..n_prefs) (
prefs_sat[p] = if abs(element([prefs[p,1],photo_arrangement)-element(prefs[p,2],photo_arrangement)) = 1 then 1 else 0 endif
)
%
Update some days later: There is another - and arguably simpler - model, similar to the previous approaches, but it use the "inverse" part in the output instead.
include "globals.mzn";
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement) /\
cost = sum(p in 1..n_prefs) (
if abs(photo_arrangement[prefs[p,1]]-photo_arrangement[prefs[p,2]]) = 1 then 1 else 0 endif
)
;
solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;
output [
"cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n",
"positions:\n"
] ++ [
if fix(photo_arrangement[j]) = i then show(j) ++ " " else "" endif
| i,j in 1..n
];
n = 9;
n_prefs = 17;
prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];
The solution is
cost: 10
photo_arrangement: [8, 1, 5, 6, 7, 9, 4, 3, 2]
positions:
2 9 8 7 3 4 5 1 6