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

1""" This module provides procedures to deal with the potential single-peakedness of the instance. 

2""" 

3 

4import copy 

5import time 

6 

7from itertools import combinations 

8from mip import * 

9 

10 

11def is_single_peaked_axis(instance, axis): 

12 """ Tests whether the instance is single-peaked with respect to the axis provided as argument. 

13 

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 

18 

19 :return: A boolean indicating if the instance is single-peaked with respect to axis. 

20 :rtype: bool 

21 """ 

22 

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 

30 

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.") 

34 

35 for order in instance.orders: 

36 positions = [indif_class_pos(order, alt) for alt in axis] 

37 

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 

56 

57 

58def is_single_peaked(instance): 

59 """ Tests whether the instance describes a profile of single-peaked preferences. It only works with strict 

60 preferences. 

61 

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). 

64 

65 :param instance: the instance to test for single-peakedness. 

66 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

67 

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

72 

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.") 

76 

77 is_SP = True 

78 end_flag = False 

79 axis = None 

80 right_axis, left_axis = [], [] 

81 x_i, x_j = None, None 

82 

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()] 

85 

86 # list_of_preferences_SP: list to modify 

87 list_of_preferences_SP = copy.deepcopy(list_of_preferences) 

88 

89 iteration = 0 

90 while is_SP and len(list_of_preferences_SP[0]) >= 1 and not end_flag: 

91 

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) 

98 

99 if len(last_candidates) >= 3: # impossible to position all candidates in leftmost and rightmost axis 

100 is_SP = False 

101 end_flag = True 

102 

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) 

108 

109 case = 0 

110 

111 for i in range(len(list_of_preferences)): 

112 

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) 

123 

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 

147 

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 

159 

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) 

168 

169 case = 0 

170 

171 for i in range(len(list_of_preferences)): 

172 

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) 

176 

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) 

185 

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 

189 

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 

193 

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) 

203 

204 axis = left_axis + right_axis 

205 

206 is_SP = is_single_peaked_axis(instance, axis) # to be completed , complete right n left axis 

207 end_flag = True 

208 break 

209 

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 

232 

233 # add x and y in leftmost or rightmost axis according to case if axis is compatible 

234 

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 

251 

252 iteration += 1 

253 

254 if is_SP and axis is None: 

255 axis = left_axis + right_axis 

256 

257 return is_SP, axis 

258 

259 

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. 

264 

265 :param instance: the instance to test for single-peakedness. 

266 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

267 

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 

281 

282 

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. 

286 

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)) 

305 

306 

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. 

310 

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)) 

318 

319 

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. 

324 

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)) 

342 

343 

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.  

349 

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)) 

372 

373 

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.  

380 

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)) 

408 

409 

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.  

416 

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)) 

440 

441 

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). 

445 

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. 

449 

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. 

452 

453 :param instance: the instance to test for single-peakedness. 

454 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

455 

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

461 

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.") 

465 

466 model = Model(sense=MINIMIZE) 

467 

468 init_time = time.time() 

469 

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)]) 

476 

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) 

481 

482 model.objective = 0 

483 

484 print("Constraints for isSinglePeakedILP generated in {} seconds.".format(time.time() - init_time)) 

485 

486 init_time = time.time() 

487 

488 # model.write('modelSP.lp') 

489 

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)) 

500 

501 print("Solver is done, took {} seconds.".format(time.time() - init_time)) 

502 

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 

513 

514 

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. 

518 

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.  

524 

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

530 

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.") 

534 

535 model = Model(sense=MINIMIZE) 

536 

537 init_time = time.time() 

538 

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))]) 

546 

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") 

555 

556 # model.start = [(v, 1) for v in votersVars[:-2]] 

557 

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) 

562 

563 print("Constraints for approxSPVoterDeletionILP generated in {} seconds.".format(time.time() - init_time)) 

564 

565 # model.write('modelSP.lp') 

566 

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)) 

577 

578 print("Solver is done, took {} seconds.".format(time.time() - init_time)) 

579 

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)) 

594 

595 return model.objective_value, opt_status.name, axis, deleted_voters 

596 

597 

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. 

601 

602 :param instance: the instance to work on. 

603 :type instance: preflibtools.instance.preflibinstance.OrdinalInstance 

604 

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

610 

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.") 

614 

615 model = Model(sense=MINIMIZE) 

616 

617 init_time = time.time() 

618 

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)]) 

626 

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) 

631 

632 model.start = [(a, 1) for a in alt_vars[:-2]] 

633 

634 model.objective = xsum(a for a in alt_vars) 

635 

636 print("Constraints for approxSPAlternativeDeletionILP generated in {} seconds.".format(time.time() - init_time)) 

637 

638 init_time = time.time() 

639 

640 # model.write('modelSP.lp') 

641 

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)) 

652 

653 print("Solver is done, took {} seconds.".format(time.time() - init_time)) 

654 

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)) 

669 

670 return model.objective_value, opt_status.name, axis, deleted_alts