A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%
2% Model for group splitting problem
3%
4% A group of people want to do activities (Cinema then Restaurant)
5% in subgroups where the activities for subgroups are supposed to
6% match better members' preferences.
7% The aim of our model is to find the best activities and group
8% combinations to recommend.
9%
10% @authors:
11%
12% Jacopo Mauro <mauro.jacopo@gmail.com>
13% Tong Liu <t.liu@unibo.it>
14%
15
16include "count.mzn";
17include "table.mzn";
18
19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20% Variables and array definitions
21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22
23% number of users
24set of int: user_ids;
25
26% activities for phase 1
27set of int: activity1_ids;
28
29% activities for phase 2
30set of int: activity2_ids;
31
32% number of cells
33set of int: cell_ids;
34
35% number of groups
36set of int: group_ids;
37
38% time domain
39set of int: time_slot_ids;
40
41% rating domains
42set of int: pub_rating_domain = 0..5;
43set of int: user_rating_domain = -2..2;
44
45% global constraint Variables
46int: min_group_size; % min cardinality of a subgroup
47int: usersn; % number of users
48int: max_wait; % wait time btw 2 activities
49int: startAfter; % time after which schedule starts
50int: eta; % balance user's rating and public rating
51
52array[activity1_ids,1..5] of int: activities1;
53array[activity2_ids,1..5] of int: activities2;
54
55array[user_ids,activity1_ids] of user_rating_domain: preferences1;
56array[user_ids,activity2_ids] of user_rating_domain: preferences2;
57
58array[activity1_ids] of int: oid1;
59array[activity2_ids] of int: oid2;
60
61array[cell_ids,cell_ids] of int: distances;
62
63% Create activities1_new for the calculation inserting index in the first position.
64array[activity1_ids,1..6] of int: activities1_data = array2d(activity1_ids,1..6,
65 [ if i=1 then j else activities1[j,i-1] endif | j in activity1_ids, i in 1..6 ]);
66array[activity2_ids,1..6] of int: activities2_data = array2d(activity2_ids,1..6,
67 [ if i=1 then j else activities2[j,i-1] endif | j in activity2_ids, i in 1..6 ]);
68
69% Configure datalist for table constraint
70array[1..max(user_ids)*max(activity1_ids),1..3] of int: preferences1_data = array2d(1..max(user_ids)*max(activity1_ids),1..3,
71 [ if k=1 then i else if k=2 then j else preferences1[i,j] endif endif | i in user_ids, j in activity1_ids, k in 1..3 ]);
72array[1..max(user_ids)*max(activity2_ids),1..3] of int: preferences2_data = array2d(1..max(user_ids)*max(activity2_ids),1..3,
73 [ if k=1 then i else if k=2 then j else preferences2[i,j] endif endif | i in user_ids, j in activity2_ids, k in 1..3 ]);
74array[1..max(cell_ids)*max(cell_ids),1..3] of int: distances_data = array2d(1..max(cell_ids)*max(cell_ids),1..3,
75 [ if k=1 then i else if k=2 then j else distances[i,j] endif endif | i in cell_ids, j in cell_ids, k in 1..3 ]);
76
77
78
79%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
80% Maps to define a solution
81%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
82
83% map user -> group
84array[user_ids] of var group_ids: user_group_map1;
85array[user_ids] of var group_ids: user_group_map2;
86
87% map group -> activity
88array[group_ids] of var activity1_ids: group_act_map1;
89array[group_ids] of var activity2_ids: group_act_map2;
90
91% map user -> activity
92array[user_ids] of var activity1_ids: user_act_map1;
93array[user_ids] of var activity2_ids: user_act_map2;
94
95% map user -> start of activity
96array[user_ids] of var time_slot_ids: user_start_time_map1;
97array[user_ids] of var time_slot_ids: user_start_time_map2;
98
99% map user -> duration
100array[user_ids] of var time_slot_ids: user_duration_map1;
101array[user_ids] of var time_slot_ids: user_duration_map2;
102
103% map user -> begin
104array[user_ids] of var time_slot_ids: activity_available_from1;
105array[user_ids] of var time_slot_ids: activity_available_from2;
106
107% map user -> end
108array[user_ids] of var time_slot_ids: user_end_map1;
109array[user_ids] of var time_slot_ids: user_end_map2;
110
111% map user -> cell
112array[user_ids] of var cell_ids: user_cell_map1;
113array[user_ids] of var cell_ids: user_cell_map2;
114
115% map user -> type
116array[user_ids] of var pub_rating_domain: user_pub_rating_map1;
117array[user_ids] of var pub_rating_domain: user_pub_rating_map2;
118
119% map user -> weight
120array[user_ids] of var user_rating_domain: user_weight_map1;
121array[user_ids] of var user_rating_domain: user_weight_map2;
122
123% map user -> distance
124array[user_ids] of var time_slot_ids: user_distance_map;
125
126array[int] of var int: check_all = user_group_map1 ++ user_group_map2 ++ group_act_map1 ++ group_act_map2 ++ user_act_map1 ++ user_act_map2 ++ user_start_time_map1 ++ user_start_time_map2 ++ user_duration_map1 ++ user_duration_map2 ++ activity_available_from1 ++ activity_available_from2 ++ user_end_map1 ++ user_end_map2 ++ user_cell_map1 ++ user_cell_map2 ++ user_pub_rating_map1 ++ user_pub_rating_map2 ++ user_weight_map1 ++ user_weight_map2 ++ user_distance_map;
127
128%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129% Check that the group members satisfy minCardinality
130%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
131
132constraint forall(i in group_ids) (
133 let { var min_group_size..usersn: c} in (
134 count(user_group_map1,i,c)) );
135
136constraint forall(i in group_ids) (
137 let { var min_group_size..usersn: c} in (
138 count(user_group_map2,i,c)) );
139
140
141%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
142% Channel constraints
143%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
144
145constraint forall(i in user_ids) (
146 table( [ user_act_map1[i], activity_available_from1[i], user_end_map1[i], user_duration_map1[i], user_cell_map1[i], user_pub_rating_map1[i] ], activities1_data) );
147
148constraint forall(i in user_ids) (
149 table( [ user_act_map2[i], activity_available_from2[i], user_end_map2[i], user_duration_map2[i], user_cell_map2[i], user_pub_rating_map2[i] ], activities2_data) );
150
151constraint forall(i in user_ids) (
152 table( [ i, user_act_map1[i], user_weight_map1[i] ], preferences1_data));
153
154constraint forall(i in user_ids) (
155 table( [ i, user_act_map2[i], user_weight_map2[i] ], preferences2_data));
156
157constraint forall(i in user_ids) (
158 table( [ user_cell_map1[i], user_cell_map2[i], user_distance_map[i] ], distances_data));
159
160% user's activity is also group's activity
161
162constraint forall(i in user_ids) (
163 user_act_map1[i] = group_act_map1[user_group_map1[i]] );
164
165constraint forall(i in user_ids) (
166 user_act_map2[i] = group_act_map2[user_group_map2[i]] );
167
168
169% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
170% % Symmetry breaking constraints
171% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
172
173% user 1 belongs always to the first group
174constraint redundant_constraint(
175 user_group_map1[min(user_ids)] = min(group_ids) /\
176 user_group_map2[min(user_ids)] = min(group_ids));
177
178% next user belongs to the group of the previous users or +1
179constraint symmetry_breaking_constraint(
180 forall (i in 1..max(group_ids)-min(group_ids)+1) (
181 user_group_map1[min(user_ids)+i] in min(group_ids)..min(group_ids)+i /\
182 user_group_map2[min(user_ids)+i] in min(group_ids)..min(group_ids)+i
183));
184
185% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186% % Activity temporal constraints
187% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
188
189constraint forall(i in user_ids) (
190 user_start_time_map1[i] >= activity_available_from1[i] /\
191 user_start_time_map1[i] <= user_end_map1[i] - user_duration_map1[i]);
192
193constraint forall(i in user_ids) (
194 user_start_time_map2[i] >= activity_available_from2[i] /\
195 user_start_time_map2[i] <= user_end_map2[i] - user_duration_map2[i]);
196
197constraint forall(i in user_ids) (
198 user_start_time_map2[i] >= user_start_time_map1[i] + user_duration_map1[i] +
199 user_distance_map[i] /\
200 user_start_time_map2[i] <= user_start_time_map1[i] + user_duration_map1[i] + max_wait );
201
202%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
203% Start After Constraint
204%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
205
206constraint forall(i in user_ids) (
207 user_start_time_map1[i] >= startAfter);
208
209%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
210% Compute objective function
211%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
212
213int: objub = eta*card(user_ids)*2 + (10-eta)*card(user_ids)*5 + (10-eta)*card(user_ids)*5 + eta*card(user_ids)*2;
214int: objlb=eta*card(user_ids)*(-2)+ (10-eta)*card(user_ids)*0 + (10-eta)*card(user_ids)*0 + eta*card(user_ids)*(-2);
215var objlb..objub: objective;
216
217constraint objective = (
218 eta * sum (user_weight_map1) + (10-eta) * sum (user_pub_rating_map1) + (10-eta) * sum (user_pub_rating_map2) + eta * sum (user_weight_map2) );
219
220solve :: seq_search([
221 int_search(user_group_map1,first_fail, indomain_min, complete),
222 int_search(user_group_map2,first_fail, indomain_min, complete),
223 int_search(user_weight_map1, first_fail, indomain_min, complete),
224 int_search(user_weight_map2, first_fail, indomain_min, complete),
225 int_search(user_act_map1, first_fail, indomain_min, complete),
226 int_search(user_act_map2, first_fail, indomain_min, complete),
227 int_search(user_start_time_map1, first_fail, indomain_min, complete),
228 int_search(user_start_time_map2, first_fail, indomain_min, complete),
229 int_search(user_duration_map1, first_fail, indomain_min, complete),
230 int_search(user_duration_map2, first_fail, indomain_min, complete),
231 int_search(user_end_map1, first_fail, indomain_min, complete),
232 int_search(user_end_map2, first_fail, indomain_min, complete),
233 ])
234 maximize objective;
235
236
237output [
238 "user_group_map1 = \(user_group_map1);\n",
239 "user_group_map2 = \(user_group_map2);\n",
240 "user_weight_map1 = \(user_weight_map1);\n",
241 "user_weight_map2 = \(user_weight_map2);\n",
242 "user_act_map1 = \(user_act_map1);\n",
243 "user_act_map2 = \(user_act_map2);\n",
244 "user_start_time_map1 = \(user_start_time_map1);\n",
245 "user_start_time_map2 = \(user_start_time_map2);\n",
246 "user_duration_map1 = \(user_duration_map1);\n",
247 "user_duration_map2 = \(user_duration_map2);\n",
248 "user_end_map1 = \(user_end_map1);\n",
249 "user_end_map2 = \(user_end_map2);\n",
250 "objective = \(objective);\n"
251];
252