Coverage for /home/simon/Git/preflibtools/preflibtools/properties/singlepeakedness.py: 79%
335 statements
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
« prev ^ index » next coverage.py v6.4.4, created at 2022-09-22 11:34 +0200
1""" This module provides procedures to deal with the potential single-peakedness of the instance.
2"""
4import copy
5import time
7from itertools import combinations
8from mip import *
11def is_single_peaked_axis(instance, axis):
12 """ Tests whether the instance is single-peaked with respect to the axis provided as argument.
14 :param instance: the instance to work on.
15 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
16 :param axis: a list of candidates.
17 :type axis: list
19 :return: A boolean indicating if the instance is single-peaked with respect to axis.
20 :rtype: bool
21 """
23 # Finds the position of the indifference class containing the alternative
24 def indif_class_pos(order, alt):
25 i = 0
26 for indif_class in order:
27 if alt in indif_class:
28 return i
29 i += 1
31 if instance.data_type not in ("toc", "soc"):
32 raise TypeError("You are trying to test for single-peakedness on an instance of type " +
33 str(instance.data_type) + ", this is not possible. Only toc and soc are allowed here.")
35 for order in instance.orders:
36 positions = [indif_class_pos(order, alt) for alt in axis]
38 peak_passed = False
39 previous_position = None
40 for pos in positions:
41 # If pos = 0, we are at the peak
42 if pos == 0:
43 peak_passed = True
44 else:
45 if previous_position is not None:
46 if peak_passed:
47 # If we passed the peak and the position is decreasing, there's a problem
48 if pos < previous_position:
49 return False
50 else:
51 # If we did not pass the peak and the position is increasing, there's a problem
52 if pos > previous_position:
53 return False
54 previous_position = pos
55 return True
58def is_single_peaked(instance):
59 """ Tests whether the instance describes a profile of single-peaked preferences. It only works with strict
60 preferences.
62 This function implements the algorithm of Escoffier, Lang, and Ozturk (2008). We are grateful to Thor Yung
63 Pheng who developed this function (under the supervision of Umberto Grandi).
65 :param instance: the instance to test for single-peakedness.
66 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
68 :return: The axis with respect to which the instance would be single-peaked, the empty list if the instance
69 is not single-peaked.
70 :rtype: list
71 """
73 if instance.data_type != "soc":
74 raise TypeError("You are trying to use the algorithm of Escoffier, Lang, and Ozturk (2008) to test single-" +
75 "peakedness on an instance of type " + str(instance.data_type) + ", this is not possible.")
77 is_SP = True
78 end_flag = False
79 axis = None
80 right_axis, left_axis = [], []
81 x_i, x_j = None, None
83 # generates list of preferences without the weight while flattening the orders
84 list_of_preferences = [list(orderMultiplicity[0]) for orderMultiplicity in instance.flatten_strict()]
86 # list_of_preferences_SP: list to modify
87 list_of_preferences_SP = copy.deepcopy(list_of_preferences)
89 iteration = 0
90 while is_SP and len(list_of_preferences_SP[0]) >= 1 and not end_flag:
92 # make a list of last candidates
93 last_candidates = []
94 for preference in list_of_preferences_SP:
95 last_candidate = preference.pop()
96 if last_candidate not in last_candidates:
97 last_candidates.append(last_candidate)
99 if len(last_candidates) >= 3: # impossible to position all candidates in leftmost and rightmost axis
100 is_SP = False
101 end_flag = True
103 elif len(last_candidates) == 1:
104 x = last_candidates[0]
105 for preference in list_of_preferences_SP:
106 if x in preference:
107 preference.remove(x)
109 case = 0
111 for i in range(len(list_of_preferences)):
113 # find index of x, x_i, x_j in each preference
114 index_x = list_of_preferences[i].index(x)
115 if x_i is None:
116 index_x_i = -1
117 else:
118 index_x_i = list_of_preferences[i].index(x_i)
119 if x_j is None:
120 index_x_j = -1
121 else:
122 index_x_j = list_of_preferences[i].index(x_j)
124 # 3 possibilities for len(last_candidates) == 1
125 if index_x_i > index_x > index_x_j: # Case 1
126 case_i = 1
127 if case == 0:
128 case = case_i
129 elif case == 1:
130 pass
131 elif case == 2:
132 end_flag = True
133 is_SP = False # contradiction
134 break
135 elif index_x_j > index_x > index_x_j: # Case 2
136 case_i = 2
137 if case == 0:
138 case = case_i
139 elif case == 2:
140 pass
141 elif case == 1:
142 end_flag = True
143 is_SP = False # contradiction
144 break
145 elif index_x > index_x_i and index_x > index_x_j: # Case 0
146 case_i = 0
148 # add x in leftmost or rightmost axis according to case if axis is compatible
149 if not end_flag:
150 if case == 0:
151 left_axis.append(x)
152 x_i = x
153 elif case == 1:
154 left_axis.append(x)
155 x_i = x
156 elif case == 2:
157 right_axis.insert(0, x)
158 x_j = x
160 elif len(last_candidates) == 2:
161 x = last_candidates[0]
162 y = last_candidates[1]
163 for preference in list_of_preferences_SP:
164 if x in preference:
165 preference.remove(x)
166 if y in preference:
167 preference.remove(y)
169 case = 0
171 for i in range(len(list_of_preferences)):
173 # find index of x, y, x_i, x_j in each preference
174 index_x = list_of_preferences[i].index(x)
175 index_y = list_of_preferences[i].index(y)
177 if x_i is None:
178 index_x_i = -1
179 else:
180 index_x_i = list_of_preferences[i].index(x_i)
181 if x_j is None:
182 index_x_j = -1
183 else:
184 index_x_j = list_of_preferences[i].index(x_j)
186 # swap position to put x in the lower position (ranked last)
187 if index_y > index_x:
188 index_x, index_y = index_y, index_x
190 # all possible cases
191 if index_x_i > index_x > index_y > index_x_j or index_x_j > index_x > index_y > index_x_i: # Case 4
192 case_i = 4
194 # get index for leftover elements and append them into left axis following increasing order
195 T_bar = last_candidates + list_of_preferences_SP[i]
196 order = []
197 for candidate in T_bar:
198 index_candidate = list_of_preferences[i].index(candidate)
199 order.append((index_candidate, candidate))
200 order.sort(reverse=True)
201 for index, candidate in order:
202 left_axis.append(candidate)
204 axis = left_axis + right_axis
206 is_SP = is_single_peaked_axis(instance, axis) # to be completed , complete right n left axis
207 end_flag = True
208 break
210 elif index_x_i > index_x > index_x_j > index_y: # Case 1
211 case_i = 1
212 if case == 0:
213 case = case_i
214 elif case == 1:
215 pass
216 elif case == 2:
217 end_flag = True
218 is_SP = False # contradiction
219 break
220 elif index_x_j > index_x > index_x_i > index_y: # Case 2
221 case_i = 2
222 if case == 0:
223 case = case_i
224 elif case == 2:
225 pass
226 elif case == 1:
227 end_flag = True
228 is_SP = False # contradiction
229 break
230 elif index_x > index_x_i and index_x > index_x_j:
231 case_i = 0
233 # add x and y in leftmost or rightmost axis according to case if axis is compatible
235 if not end_flag:
236 if case == 0:
237 left_axis.append(x)
238 right_axis.insert(0, y)
239 x_i = x
240 x_j = y
241 elif case == 1:
242 left_axis.append(x)
243 right_axis.insert(0, y)
244 x_i = x
245 x_j = y
246 elif case == 2:
247 left_axis.append(y)
248 right_axis.insert(0, x)
249 x_i = y
250 x_j = x
252 iteration += 1
254 if is_SP and axis is None:
255 axis = left_axis + right_axis
257 return is_SP, axis
260def sp_cons_ones_matrix(instance):
261 """ Returns a binary matrix such that the instance is single-peaked if and only if the matrix has the
262 consecutive ones property. This is an helper function to implement the algorithm proposed by Bartholdi
263 and Trick (1986) to deal with single-peakedness.
265 :param instance: the instance to test for single-peakedness.
266 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
268 :return: A binary matrix
269 :rtype: numpy array
270 """
271 matrix = np.zeros((sum(len(o) for o in instance.orders), instance.num_alternatives))
272 matrix_index = 0
273 for order in instance.orders:
274 for max_level in range(len(order)):
275 for level_index in range(max_level + 1):
276 level = order[level_index]
277 for a in level:
278 matrix[matrix_index][a] = 1
279 matrix_index += 1
280 return matrix
283def sp_ILP_trans_cstr(model, left_of_vars, instance):
284 """ A helper function for testing single-peakedness with an ILP solver. Adds the transitivity constraints to
285 the ILP model given as parameter. These constraints encode that the axis constructed is transitive.
287 :param model: The ILP model, should be an instance of the python-mip Model class.
288 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
289 if a1 is to the left of a2 in the axis.
290 :param instance: the instance to test for single-peakedness.
291 """
292 for (a1, a2, a3) in combinations(range(instance.num_alternatives), 3):
293 model.add_constr(left_of_vars[a1][a2] + left_of_vars[a2][a3] - 1 <= left_of_vars[a1][a3],
294 name="transitivity_" + str(a1) + "_" + str(a2) + "_" + str(a3))
295 model.add_constr(left_of_vars[a1][a3] + left_of_vars[a3][a2] - 1 <= left_of_vars[a1][a2],
296 name="transitivity_" + str(a1) + "_" + str(a3) + "_" + str(a2))
297 model.add_constr(left_of_vars[a2][a1] + left_of_vars[a1][a3] - 1 <= left_of_vars[a2][a3],
298 name="transitivity_" + str(a2) + "_" + str(a1) + "_" + str(a3))
299 model.add_constr(left_of_vars[a2][a3] + left_of_vars[a3][a1] - 1 <= left_of_vars[a2][a1],
300 name="transitivity_" + str(a2) + "_" + str(a3) + "_" + str(a1))
301 model.add_constr(left_of_vars[a3][a1] + left_of_vars[a1][a2] - 1 <= left_of_vars[a3][a2],
302 name="transitivity_" + str(a3) + "_" + str(a1) + "_" + str(a2))
303 model.add_constr(left_of_vars[a3][a2] + left_of_vars[a2][a1] - 1 <= left_of_vars[a3][a1],
304 name="transitivity_" + str(a3) + "_" + str(a2) + "_" + str(a1))
307def sp_ILP_total_cstr(model, left_of_vars, instance):
308 """ A helper function for testing single-peakedness with an ILP solver. Adds the totality constraints to
309 the ILP model given as parameter. These constraints encode that the axis constructed is total.
311 :param model: The ILP model, should be an instance of the python-mip Model class.
312 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
313 if a1 is to the left of a2 in the axis.
314 :param instance: the instance to test for single-peakedness.
315 """
316 for (a1, a2) in combinations(range(instance.num_alternatives), 2):
317 model.add_constr(left_of_vars[a1][a2] + left_of_vars[a2][a1] == 1, name="totality_" + str(a1) + "_" + str(a2))
320def sp_ILP_pos_cstr(model, left_of_vars, pos_vars, instance):
321 """ A helper function for testing single-peakedness with an ILP solver. Adds the position constraints to
322 the ILP model given as parameter. These constraints enforce the position variables to follow the order
323 defined by the left-of variables.
325 :param model: The ILP model, should be an instance of the python-mip Model class.
326 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
327 if alternative a1 is to the left of alternative a2 in the axis.
328 :param pos_vars: A list of list of python-mip variables where posVar[a1] indicates the position of
329 alternative a1 in the axis.
330 :param instance: the instance to test for single-peakedness.
331 """
332 num_alternatives = instance.num_alternatives
333 for (a1, a2) in combinations(range(num_alternatives), 2):
334 model.add_constr(pos_vars[a1] <= pos_vars[a2] + num_alternatives * (1 - left_of_vars[a1][a2]),
335 name="ordering_" + str(a1) + "_" + str(a2))
336 model.add_constr(pos_vars[a2] - pos_vars[a1] >= 0.5 * left_of_vars[a1][a2] - (1 - left_of_vars[a1][a2]) * num_alternatives,
337 name="diffPos1_" + str(a1) + "_" + str(a2))
338 model.add_constr(pos_vars[a2] <= pos_vars[a1] + num_alternatives * (1 - left_of_vars[a2][a1]),
339 name="ordering_" + str(a2) + "_" + str(a1))
340 model.add_constr(pos_vars[a1] - pos_vars[a2] >= 0.5 * left_of_vars[a2][a1] - (1 - left_of_vars[a2][a1]) * num_alternatives,
341 name="diffPos1_" + str(a2) + "_" + str(a1))
344def sp_ILP_cons_ones_cstr(model, left_of_vars, instance):
345 """ A helper function for testing single-peakedness with an ILP solver. Adds the single-peakedness constraints
346 to the ILP model given as parameter. These constraints enforce that the instance is indeed single-peaked
347 with respect to the axis constructed. They actually implement the consecutive ones property of the
348 binary matrix corresponding to the instance.
350 :param model: The ILP model, should be an instance of the python-mip Model class.
351 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
352 if a1 is to the left of a2 in the axis.
353 :param instance: the instance to test for single-peakedness.
354 """
355 matrix = sp_cons_ones_matrix(instance)
356 for row_index in range(len(matrix)):
357 row = matrix[row_index]
358 # print("Row{}: {}".format(rowIndex, row))
359 zeros = set()
360 ones = set()
361 for index, value in enumerate(row):
362 if value == 1:
363 ones.add(index)
364 else:
365 zeros.add(index)
366 for (i, j) in combinations(ones, 2):
367 for k in zeros:
368 model.add_constr(left_of_vars[i][k] + left_of_vars[k][j] <= 1,
369 name="SP_row" + str(row_index) + "_" + str(i) + "_" + str(j) + "_" + str(k))
370 model.add_constr(left_of_vars[j][k] + left_of_vars[k][i] <= 1,
371 name="SP_row" + str(row_index) + "_" + str(j) + "_" + str(i) + "_" + str(k))
374def sp_ILP_cons_ones_vot_del_cstr(model, left_of_vars, voter_vars, instance):
375 """ A helper function for computing the closeness to single-peakedness of and instance with an ILP solver.
376 Adds the single-peakedness constraints to the ILP model given as parameter, allowing to ignore some
377 voters if needed. These constraints enforce that the instance is indeed single-peaked with respect to
378 the axis constructed for the non-ignored voters. They actually implement the consecutive ones property of
379 the binary matrix corresponding to the instance.
381 :param model: The ILP model, should be an instance of the python-mip Model class.
382 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
383 if a1 is to the left of a2 in the axis.
384 :param voter_vars: A list of list of python-mip variables where votersVars[v] is set to 1 if and only if
385 voter v is removed from consideration.
386 :param instance: the instance to test for single-peakedness.
387 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
388 """
389 matrix = sp_cons_ones_matrix(instance)
390 voter_index = -1
391 for row_index in range(len(matrix)):
392 row = matrix[row_index]
393 if sum(row) == 1:
394 voter_index += 1
395 zeros = set()
396 ones = set()
397 for index, value in enumerate(row):
398 if value == 1:
399 ones.add(index)
400 else:
401 zeros.add(index)
402 for (i, j) in combinations(ones, 2):
403 for k in zeros:
404 model.add_constr(left_of_vars[i][k] + left_of_vars[k][j] <= 1 + voter_vars[voter_index],
405 name="SP_row" + str(row_index) + "_" + str(i) + "_" + str(j) + "_" + str(k))
406 model.add_constr(left_of_vars[j][k] + left_of_vars[k][i] <= 1 + voter_vars[voter_index],
407 name="SP_row" + str(row_index) + "_" + str(j) + "_" + str(i) + "_" + str(k))
410def sp_ILP_cons_ones_alt_del_cstr(model, left_of_vars, alt_vars, instance):
411 """ A helper function for computing the closeness to single-peakedness of and instance with an ILP solver.
412 Adds the single-peakedness constraints to the ILP model given as parameter, allowing to ignore some
413 alternatives if needed. These constraints enforce that the instance is indeed single-peaked with respect to
414 the axis constructed for the non-ignored alternatives. They actually implement the consecutive ones property
415 of the binary matrix corresponding to the instance.
417 :param model: The ILP model, should be an instance of the python-mip Model class.
418 :param left_of_vars: A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only
419 if a1 is to the left of a2 in the axis.
420 :param alt_vars: A list of list of python-mip variables where altVars[a] is set to 1 if and only if
421 alternative a is removed from consideration.
422 :param instance: the instance to test for single-peakedness.
423 """
424 matrix = sp_cons_ones_matrix(instance)
425 for row_index in range(len(matrix)):
426 row = matrix[row_index]
427 zeros = set()
428 ones = set()
429 for index, value in enumerate(row):
430 if value == 1:
431 ones.add(index)
432 else:
433 zeros.add(index)
434 for (i, j) in combinations(ones, 2):
435 for k in zeros:
436 model.add_constr(left_of_vars[i][k] + left_of_vars[k][j] <= 1 + alt_vars[i] + alt_vars[j] + alt_vars[k],
437 name="SP_row" + str(row_index) + "_" + str(i) + "_" + str(j) + "_" + str(k))
438 model.add_constr(left_of_vars[j][k] + left_of_vars[k][i] <= 1 + alt_vars[j] + alt_vars[i] + alt_vars[k],
439 name="SP_row" + str(row_index) + "_" + str(j) + "_" + str(i) + "_" + str(k))
442def is_single_peaked_ILP(instance):
443 """ Tests whether the instance describes a profile of single-peaked preferences. It also works if indifference
444 is allowed (the property would then be single-plateaued).
446 This function implements the algorithm proposed by Bartholdi and Trick (1986). It first constructs the
447 corresponding binary matrix and then uses an ILP solver to check whether the matrix has the consecutive
448 ones property.
450 This code is inspired by that of Zack Fitzsimmons (zfitzsim@holycross.edu) and Martin Lackner
451 (lackner@dbai.tuwien.ac.at), available at https://github.com/zmf6921/incompletesp.
453 :param instance: the instance to test for single-peakedness.
454 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
456 :return: A triple composed of a boolean variable indicating whether the instance is single-peaked or not,
457 the python-mip optimisation status of the ILP model, and the axis for which the instance is single-peaked
458 (None if the instance is not single-peaked).
459 :rtype: Tuple(bool, str, list)
460 """
462 if instance.data_type not in ("toc", "soc"):
463 raise TypeError("You are trying to test for single-peakedness on an instance of type " +
464 str(instance.data_type) + ", this is not possible. Only toc and soc are allowed here.")
466 model = Model(sense=MINIMIZE)
468 init_time = time.time()
470 left_of_vars = np.array([[model.add_var(var_type=BINARY,
471 name='leftof_' + str(a1) + '_' + str(a2)) for a2 in
472 range(instance.num_alternatives)] for a1 in range(instance.num_alternatives)])
473 pos_vars = np.array([model.add_var(var_type=INTEGER,
474 name='pos_' + str(a), lb=1, ub=instance.num_alternatives) for a in
475 range(instance.num_alternatives)])
477 sp_ILP_trans_cstr(model, left_of_vars, instance)
478 sp_ILP_total_cstr(model, left_of_vars, instance)
479 sp_ILP_cons_ones_cstr(model, left_of_vars, instance)
480 sp_ILP_pos_cstr(model, left_of_vars, pos_vars, instance)
482 model.objective = 0
484 print("Constraints for isSinglePeakedILP generated in {} seconds.".format(time.time() - init_time))
486 init_time = time.time()
488 # model.write('modelSP.lp')
490 model.verbose = 0
491 model.max_gap = 0.05
492 model.threads = -1
493 opt_status = model.optimize()
494 # if optStatus == OptimizationStatus.OPTIMAL:
495 # print('optimal solution cost {} found'.format(model.objective_value))
496 # elif optStatus == OptimizationStatus.FEASIBLE:
497 # print('sol.cost {} found, best possible: {}'.format(model.objective_value, model.objective_bound))
498 # elif optStatus == OptimizationStatus.NO_SOLUTION_FOUND:
499 # print('no feasible solution found, lower bound is: {}'.format(model.objective_bound))
501 print("Solver is done, took {} seconds.".format(time.time() - init_time))
503 if opt_status == OptimizationStatus.OPTIMAL or opt_status == OptimizationStatus.FEASIBLE:
504 axis = [0 for i in range(instance.num_alternatives)]
505 for v in pos_vars:
506 axis[int(v.x) - 1] = int(v.name.split("_")[-1])
507 # print('solution:')
508 # for v in model.vars:
509 # if abs(v.x) > 1e-6: # only printing non-zeros
510 # print('{} : {}'.format(v.name, v.x))
511 return True, opt_status.name, axis
512 return False, opt_status.name, None
515def approx_SP_voter_deletion_ILP(instance, weighted=False):
516 """ Uses an ILP solver to compute how close to single-peakedness an instance, where closeness is measured as the
517 smallest number of voter to remove for the instance to be single-peaked.
519 :param instance: the instance to work on.
520 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
521 :param weighted: a boolean indicating if orders in the instance should have a weight of 1 in the ILP
522 optimization (the default case), or if the weight should be the number of voters having submitted
523 the order.
525 :return: A quadruple composed of the number of voters that have been removed for the instance to be
526 single-peaked, the python-mip optimisation status of the ILP model, the axis for which the instance
527 is single-peaked, and the list of voters that have been removed.
528 :rtype: Tuple(bool, str, list, list)
529 """
531 if instance.data_type not in ("toc", "soc"):
532 raise TypeError("You are trying to test for single-peakedness on an instance of type " +
533 str(instance.data_type) + ", this is not possible. Only toc and soc are allowed here.")
535 model = Model(sense=MINIMIZE)
537 init_time = time.time()
539 left_of_vars = np.array([[model.add_var(var_type=BINARY, name='leftof_' + str(a1) + '_' + str(a2)) for a2 in
540 range(instance.num_alternatives)] for a1 in range(instance.num_alternatives)])
541 pos_vars = np.array(
542 [model.add_var(var_type=INTEGER, name='pos_' + str(a), lb=1, ub=instance.num_alternatives) for a in
543 range(instance.num_alternatives)])
544 voter_vars = np.array(
545 [model.add_var(var_type=BINARY, name='delVoter_' + str(v)) for v in range(len(instance.orders))])
547 sp_ILP_trans_cstr(model, left_of_vars, instance)
548 print("Transitivity done")
549 sp_ILP_total_cstr(model, left_of_vars, instance)
550 print("Totality done")
551 sp_ILP_cons_ones_vot_del_cstr(model, left_of_vars, voter_vars, instance)
552 print("Consecutive ones done")
553 sp_ILP_pos_cstr(model, left_of_vars, pos_vars, instance)
554 print("Position done")
556 # model.start = [(v, 1) for v in votersVars[:-2]]
558 if weighted:
559 model.objective = xsum(v * instance.multiplicity[int(v.name.split('_')[-1])] for v in voter_vars)
560 else:
561 model.objective = xsum(v for v in voter_vars)
563 print("Constraints for approxSPVoterDeletionILP generated in {} seconds.".format(time.time() - init_time))
565 # model.write('modelSP.lp')
567 # model.verbose = 0
568 model.max_gap = 0.05
569 model.threads = -1
570 opt_status = model.optimize()
571 # if optStatus == OptimizationStatus.OPTIMAL:
572 # print('optimal solution cost {} found'.format(model.objective_value))
573 # elif optStatus == OptimizationStatus.FEASIBLE:
574 # print('sol.cost {} found, best possible: {}'.format(model.objective_value, model.objective_bound))
575 # elif optStatus == OptimizationStatus.NO_SOLUTION_FOUND:
576 # print('no feasible solution found, lower bound is: {}'.format(model.objective_bound))
578 print("Solver is done, took {} seconds.".format(time.time() - init_time))
580 axis = None
581 deleted_voters = None
582 if opt_status == OptimizationStatus.OPTIMAL or opt_status == OptimizationStatus.FEASIBLE:
583 axis = [0 for i in range(instance.num_alternatives)]
584 for v in pos_vars:
585 axis[int(v.x) - 1] = int(v.name.split("_")[-1])
586 deleted_voters = []
587 for v in voter_vars:
588 if v.x > 0:
589 deleted_voters.append(v.name.split("_")[-1])
590 # print('solution:')
591 # for v in model.vars:
592 # if abs(v.x) > 1e-6: # only printing non-zeros
593 # print('{} : {}'.format(v.name, v.x))
595 return model.objective_value, opt_status.name, axis, deleted_voters
598def approx_SP_alternative_deletion_ILP(instance):
599 """ Uses an ILP solver to compute how close to single-peakedness an instance, where closeness is measured as the
600 smallest number of alternatives to remove for the instance to be single-peaked.
602 :param instance: the instance to work on.
603 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance
605 :return: A quadruple composed of the number of alternatives that have been removed for the instance to be
606 single-peaked, the python-mip optimisation status of the ILP model, the axis for which the instance
607 is single-peaked, and the list of alternatives that have been removed.
608 :rtype: Tuple(bool, str, list, list)
609 """
611 if instance.data_type not in ("toc", "soc"):
612 raise TypeError("You are trying to test for single-peakedness on an instance of type " +
613 str(instance.data_type) + ", this is not possible. Only toc and soc are allowed here.")
615 model = Model(sense=MINIMIZE)
617 init_time = time.time()
619 left_of_vars= np.array([[model.add_var(var_type=BINARY, name='leftof_' + str(a1) + '_' + str(a2)) for a2 in
620 range(instance.num_alternatives)] for a1 in range(instance.num_alternatives)])
621 pos_vars = np.array(
622 [model.add_var(var_type=INTEGER, name='pos_' + str(a), lb=1, ub=instance.num_alternatives) for a in
623 range(instance.num_alternatives)])
624 alt_vars = np.array(
625 [model.add_var(var_type=BINARY, name='delAlt_' + str(a)) for a in range(instance.num_alternatives)])
627 sp_ILP_trans_cstr(model, left_of_vars, instance)
628 sp_ILP_total_cstr(model, left_of_vars, instance)
629 sp_ILP_cons_ones_alt_del_cstr(model, left_of_vars, alt_vars, instance)
630 sp_ILP_pos_cstr(model, left_of_vars, pos_vars, instance)
632 model.start = [(a, 1) for a in alt_vars[:-2]]
634 model.objective = xsum(a for a in alt_vars)
636 print("Constraints for approxSPAlternativeDeletionILP generated in {} seconds.".format(time.time() - init_time))
638 init_time = time.time()
640 # model.write('modelSP.lp')
642 # model.verbose = 0
643 model.max_gap = 0.05
644 model.threads = -1
645 opt_status = model.optimize()
646 # if optStatus == OptimizationStatus.OPTIMAL:
647 # print('optimal solution cost {} found'.format(model.objective_value))
648 # elif optStatus == OptimizationStatus.FEASIBLE:
649 # print('sol.cost {} found, best possible: {}'.format(model.objective_value, model.objective_bound))
650 # elif optStatus == OptimizationStatus.NO_SOLUTION_FOUND:
651 # print('no feasible solution found, lower bound is: {}'.format(model.objective_bound))
653 print("Solver is done, took {} seconds.".format(time.time() - init_time))
655 axis = None
656 deleted_alts = None
657 if opt_status == OptimizationStatus.OPTIMAL or opt_status == OptimizationStatus.FEASIBLE:
658 axis = [0 for i in range(instance.num_alternatives)]
659 for v in pos_vars:
660 axis[int(v.x) - 1] = int(v.name.split("_")[-1])
661 deleted_alts = []
662 for v in alt_vars:
663 if v.x > 0:
664 deleted_alts.append(v.name.split("_")[-1])
665 # print('solution:')
666 # for v in model.vars:
667 # if abs(v.x) > 1e-6: # only printing non-zeros
668 # print('{} : {}'.format(v.name, v.x))
670 return model.objective_value, opt_status.name, axis, deleted_alts