-
Notifications
You must be signed in to change notification settings - Fork 0
/
heuristics.cpp
739 lines (592 loc) · 23.4 KB
/
heuristics.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
#include "heuristics.h"
/*
verification algorithm
*/
bool verify_vertex_cover(Graph &g, INT_SET Vc) {
for (auto it = g.edges.begin(); it != g.edges.end(); it++) {
INT_SET ev = {it->first, it->second};
if (find_first_of(Vc.begin(), Vc.end(), ev.begin(), ev.end()) == Vc.end()) {
// neither vertex is in vertex cover: edge isn't covered
return false;
}
}
return true;
}
/*
simple greedy constructive heuristic
iterates through all edges and, if the edge is uncovered, adds its vertex with the highest degree to vertex cover
*/
INT_SET greedy(Graph &g, int seed, bool debug) {
INT_SET Vc;
INT_PAIR current_edge;
int degree_a = 0, degree_b = 0, a = -1, b = -1;
INT_PAIR_LIST edges = g.edges; // won't be altered
if (seed) { // shuffles array if seed is not 0
srand(seed);
random_shuffle(edges.begin(), edges.end(), rng);
if (debug) printf("Edges shuffled. First: (%d, %d)\n", edges[0].first, edges[0].second);
}
for (auto it = edges.begin(); it != edges.end(); it++) {
a = it->first, b = it->second;
INT_SET ev = {a, b};
if (find_first_of(Vc.begin(), Vc.end(), ev.begin(), ev.end()) == Vc.end()) {
// none of the edge vertices are in vertex cover
if (g.degree(a) > g.degree(b)) {
Vc.insert(a);
if (debug) printf("Added %d to vertex cover.\n", a);
} else {
Vc.insert(b);
if (debug) printf("Added %d to vertex cover.\n", b);
}
}
}
return Vc;
}
/*
random multistart variation that runs simple greedy multiple times and returns the best solution found
*/
INT_SET rm_greedy(Graph &g, int iterations, bool debug) {
if (iterations < 2) error("Number of iterations should be at least 2.");
INT_SET result, best_result;
int best_result_size = INT_MAX, result_size = 0;
for (int i = 0; i < iterations; i++) {
result = greedy(g, i+1); // pass iterator++ as seed for the random number generator
result_size = result.size();
if (debug) printf("Iteration %d: found vertex cover of size %d.\n", i, result_size);
if (result_size < best_result_size) {
best_result = result;
best_result_size = result_size; // save obtained MVC as the best one yet
}
}
if (debug) printf("%s - Best result: %d\n", g.get_name().c_str(), best_result_size);
return best_result;
}
/*
multistart alternative function that returns all solutions found
*/
vector<INT_SET> rm_greedy_all(Graph &g, int iterations, bool debug) {
if (iterations < 2) error("Number of iterations should be at least 2.");
INT_SET result;
vector<INT_SET> results = {};
for (int i = 0; i < iterations; i++) {
result = greedy(g, /*i+1*/ time(NULL)); // pass iterator++ as seed for the random number generator
results.push_back(result);
if (debug) printf("Iteration %d: found vertex cover of size %d.\n", i, result.size());
}
return results;
}
/*
edges that will become uncovered by the removal of all the vertices in V from Vc
*/
INT_PAIR_LIST loss(Graph &g, INT_SET Vc, INT_SET V) {
int a = -1, b = -1;
INT_PAIR_LIST loss = {};
bool removing_a = false, removing_b = false;
for (auto it = g.edges.begin(); it != g.edges.end(); it++) {
a = it->first;
b = it->second;
removing_a = find(V.begin(), V.end(), a) != V.end();
removing_b = find(V.begin(), V.end(), b) != V.end();
if ((removing_a && removing_b) || // a and b are to be removed: (a,b) would be uncovered
(removing_a && find(Vc.begin(), Vc.end(), b) == Vc.end()) || // a to be removed, b not in cover: (a,b) would be uncovered
(removing_b && find(Vc.begin(), Vc.end(), a) == Vc.end()) // b to be removed, a not in cover: (a,b) would be uncovered
) {
loss.push_back(make_pair(a, b));
}
}
return loss;
}
/*
returns first solution that improves the given solution, or -1 if it reaches max_it iterations
*/
INT_SET first_improving(Graph &g, INT_SET solution, int max_it, int seed, bool debug) {
srand(seed);
for (int i = 0; i < max_it; i++) {
int v1 = rand() % solution.size();
int v2 = rand() % solution.size();
if (v2 == v1) {
v2 = rand() % solution.size();
}
if (debug) printf("Selected vertices to remove: %d and %d\n", v1, v2);
INT_PAIR_LIST uncovered = loss(g, solution, {v1, v2});
if (debug) {
printf("Uncovered edges: ");
print(uncovered);
}
int loss = uncovered.size();
if (debug) printf("Total loss: %d\n", loss);
int common = -1; // vertex (most likely non existent) that covers all of the edges uncovered by the loss of v1 and v2
INT_LIST flattened = {};
for (auto it = uncovered.begin(); it != uncovered.end(); it++) {
flattened.push_back(it->first);
flattened.push_back(it->second);
}
for (auto it = flattened.begin(); it != flattened.end(); it++) {
if (*it == v1 || *it == v2) continue; // common vertex can't be the 2 removed
if (count_occurrences(flattened, *it) == loss) {
// found a vertex that covers all lost edges!
common = *it;
break;
}
}
if (debug) {
printf("Flattened: ");
for (auto it = flattened.begin(); it != flattened.end(); it++) {
printf("%d ", *it);
}
printf("\n");
}
if (common != -1) {
// remove v1 and v2 and insert common vertex
solution.erase(v1);
solution.erase(v2);
solution.insert(common);
if (debug) printf("Found common vertex: %d\n", common);
// verify vertex cover at each turn
if (verify_vertex_cover(g, solution)) {
return solution;
} else {
printf("Solution found didn't pass vertex cover validation. :(\n");
return INT_SET_NULL;
}
} else {
if (debug) printf("Iteration %d couldn't find common vertex.\n", i);
}
}
if (debug) printf("Couldn't find common vertex after %d iterations. Returning INT_SET_NULL.\n", max_it);
return INT_SET_NULL; // reached max_it and couldn't find improving solution
}
/*
local search algorithm
g: graph
max_it: max search iterations
max_it_1st: max iterations of first-improving heuristic at each search iteration
initial: optional initial solution for the search
debug: whether to print debug messages
*/
INT_SET local_search(Graph &g, int max_it, int max_it_1st, INT_SET initial, bool debug) {
if (debug) printf("%s - Starting local search\n", g.get_name().c_str());
INT_SET current_solution = (initial == INT_SET_NULL) ? greedy(g) /* build initial solution */ : initial;
if (debug) printf("Initial solution:: [%d]\n", current_solution.size());
INT_SET first_improving_solution;
int it = 0;
while (it < max_it) {
first_improving_solution = first_improving(g, current_solution, max_it_1st, time(NULL), debug);
// stop when no longer able to improve solution
if (first_improving_solution == INT_SET_NULL) {
if (debug) printf("[Search iteration %d] Couldn't find improving solution after %d iterations. Finishing local search.\nFinal solution: %d vertices.\n", it, max_it_1st, current_solution.size());
if (!verify_vertex_cover(g, current_solution)) {
printf("Final solution doesn't pass vertex cover verification.\n");
return INT_SET_NULL;
}
return current_solution;
}
current_solution = first_improving_solution;
it++;
}
return current_solution;
}
/*
random multistart version of local search, using the solutions from rm-greedy and applying local search to them, finally returning only the best result found
*/
INT_SET rm_local_search(Graph &g, string type, int it_rm, int max_it, int max_it_1st, bool debug) {
vector<INT_SET> initial_solutions = rm_greedy_all(g, it_rm, debug); // get all rm-greedy solutions
INT_SET solution = {}, best_ls_solution = {};
int best_ls_solution_size = INT_MAX;
int solution_size = 0, it_count = 0;
for (auto it = initial_solutions.begin(); it != initial_solutions.end(); it++) {
if (debug) printf("Applying local search to initial solution %d of size %d.\n", it_count, it->size());
solution = local_search(g, max_it, max_it_1st, *it); // run local search using rm solution as initial
solution_size = solution.size();
if (solution_size <= best_ls_solution_size) {
best_ls_solution = solution;
best_ls_solution_size = solution_size;
}
it_count++;
}
return best_ls_solution;
}
/*
semi-greedy
uses restricted candidate list
[!] MAY RETURN INCOMPLETE VERTEX COVER (NOT A VALID SOLUTION)
*/
INT_SET semi_greedy(Graph &g, int seed, float alpha, bool debug) {
if ((alpha < 0.0) || (alpha > 1.0)) {
error("Invalid alpha. (0 <= alpha <= 1)");
}
INT_SET Vc = {};
/* get vertex list and sort it by highest degree first */
INT_LIST vertices = g.get_vertex_list();
vertices = g.sort_vertices_by_higher_degree(vertices);
if (debug) printf("Vertices list sorted.\n");
int min_degree, max_degree;
INT_LIST RCL = {};
int min_accepted_degree = -1, v = -1;
if (seed) srand(seed); // seed generator once
int m = g.get_m(), it = 0;
/* main loop */
while (it < m) {
if (alpha == 1.0) {
RCL = INT_LIST(vertices.begin(), vertices.end()); // copy of vertices
} else {
max_degree = g.degree(vertices.front());
min_degree = g.degree(vertices.back());
min_accepted_degree = max_degree - (int) floor(alpha*(max_degree-min_degree));
if (debug) printf("Max degree = %d, min degree = %d, min accepted = %d\n", max_degree, min_degree, min_accepted_degree);
for (auto v_it = vertices.begin(); v_it != vertices.end(); v_it++) {
if (g.degree(*v_it) < min_accepted_degree) break;
RCL.push_back(*v_it);
}
}
if (!RCL.size()) break;
if (debug) printf("RCL size: %d\n", RCL.size());
/* select random vertex from RCL and add it to cover */
v = RCL[rand() % RCL.size()];
if (debug) printf("Randomly chosen vertex from RCL: %d\n", v);
Vc.insert(v);
vertices.erase(find(vertices.begin(), vertices.end(), v));
/* if it's a complete cover, stop running */
if (verify_vertex_cover(g, Vc)) break;
RCL.clear();
it++;
}
return Vc;
}
/*
repair incomplete vertex cover by iterating through edges and, for uncovered edges, adding the vertex of highest degree to the solution
*/
INT_SET repair(Graph &g, INT_SET incomplete_Vc, int seed) {
INT_SET Vc = incomplete_Vc;
int a = 0, b = 0;
INT_PAIR_LIST edges = g.get_edges_copy();
if (seed) {
srand(seed);
random_shuffle(edges.begin(), edges.end(), rng);
/*if (debug)*/ printf("Shuffled edges successfully! First edge is: (%d, %d)\n", edges[0].first, edges[0].second);
}
for (auto it = g.edges.begin(); it != g.edges.end(); it++) {
a = it->first;
b = it->second;
if ((find(Vc.begin(), Vc.end(), a) == Vc.end()) && (find(Vc.begin(), Vc.end(), b) == Vc.end())) {
// edge is uncovered
if (g.degree(a) > g.degree(b)) { // add vertex with the highest degree to incomplete Vc
Vc.insert(a);
} else {
Vc.insert(b);
}
}
}
return Vc;
}
INT_SET grasp(Graph &g, float alpha, int max_time_ms, int max_iterations, int target, bool debug) {
INT_SET solution = {}, best_solution = {};
int solution_size = 0, best_solution_size = INT_MAX, iterations = 0;
int total_elapsed_time = 0, dt = 0;
TIMESTAMP t0 = time();
/* main loop of GRASP procedure */
while ((iterations < max_iterations) && (total_elapsed_time < max_time_ms)) { // stopping conditions
printf("GRASP iteration %d.\n", iterations);
/*
phase 1: construction (semi-greedy)
*/
t0 = time();
solution = semi_greedy(g, time(NULL), alpha, false);
dt = elapsed_time(t0); // semi-greedy runtime
if (!verify_vertex_cover(g, solution)) {
if (debug) printf("Semi-greedy solution (INVALID): [%d].\n", solution.size());
t0 = time();
solution = repair(g, solution, iterations+1);
dt += elapsed_time(t0); // repair runtime
if (debug) printf("Repaired solution: [%d].\n", solution.size());
} else {
if (debug) printf("Semi-greedy solution: [%d].\n", solution.size());
}
/*
phase 2: local search
*/
int max_it = 100, max_it_1st = 300;
t0 = time();
solution = local_search(g, max_it, max_it_1st, solution);
dt += elapsed_time(t0); // local search runtime
solution_size = solution.size();
if (debug) printf("Local search solution [%d].\n", solution_size);
/*
conclusion: replace current best solution if the one found is better
*/
if (solution_size < best_solution_size) {
best_solution = solution;
best_solution_size = solution_size;
}
/* target verification */
if (target != -1 && best_solution_size <= target) {
if (debug) printf("GRASP reached target value.\n");
break;
}
total_elapsed_time += dt;
iterations++;
}
if (debug) printf("Stopped GRASP at %d elapsed milliseconds & %d iterations.\n", total_elapsed_time, iterations);
if (verify_vertex_cover(g, solution)) {
return best_solution;
} else {
printf("GRASP returned invalid solution. D:\n");
return INT_SET{-1};
}
}
SOLUTION_SET restricted_neighborhood(Graph &g, INT_SET initial, INT_SET guiding) {
SOLUTION_SET viable_solutions = {}; // set to avoid identical solutions
if (initial == guiding) return viable_solutions; // neighborhood is empty if the solutions are the same
else if (initial.size() < guiding.size()) {
printf("Initial solution shouldn't be better than guiding solution.\n");
return viable_solutions;
}
INT_SET possible_solution = {};
INT_SET diff_to_remove = subtraction(initial, guiding); // elements in Si that are not in Sg
INT_SET diff_to_include = subtraction(guiding, initial); // elements in Sg that are not in Si
for (auto r_it = diff_to_remove.begin(); r_it != diff_to_remove.end(); r_it++) {
possible_solution = copy_int_set(initial);
possible_solution.erase(find(possible_solution.begin(), possible_solution.end(), *r_it));
if (verify_vertex_cover(g, possible_solution)) viable_solutions.insert(possible_solution);
for (auto i_it = diff_to_include.begin(); i_it != diff_to_include.end(); i_it++) {
possible_solution.insert(*i_it);
if (verify_vertex_cover(g, possible_solution)) viable_solutions.insert(possible_solution);
}
}
return viable_solutions;
}
/*
Compute the similarity between two solutions
*/
float similarity(Graph &g, INT_SET A, INT_SET B) {
if (A == B) return 1;
INT_SET difference = symmetric_difference(A, B);
float difference_cost = difference.size() / (float) g.get_n();
return 1.0 - difference_cost;
}
/*
Given a solution set, returns the best solution considering the following criteria
1. Smallest size
2. Most similar to given solution closer_to
*/
INT_SET best_solution(Graph &g, SOLUTION_SET solutions, INT_SET closer_to, bool &tie) {
if (solutions.size() == 1) return *solutions.begin();
int min_size = INT_MAX, solution_size = 0;
float max_similarity = 0.0, solution_similarity = 0.0;
INT_SET best_solution = {}, solution = {};
for (auto it = solutions.begin(); it != solutions.end(); it++) {
solution = *it;
solution_size = solution.size();
solution_similarity = similarity(g, solution, closer_to);
if (solution_size < min_size) {
best_solution = solution;
min_size = solution_size;
max_similarity = solution_similarity;
} else if (solution_size == min_size) {
if (solution_similarity > max_similarity) {
best_solution = solution;
min_size = solution_size;
max_similarity = solution_similarity;
} else if (solution_similarity == max_similarity) tie = true;
}
}
return best_solution;
}
/*
Forward path relinking procedure
*/
INT_SET forward_path_relinking(Graph &g, INT_SET initial, INT_SET guiding, bool debug) {
if (initial.size() < guiding.size()) {
if (debug) printf("FPR called for initial solution better than guiding solution.\n");
return initial;
}
printf("FPR: relinking initial [%d] and guiding [%d].\n", initial.size(), guiding.size());
INT_SET general_best = INT_SET_NULL, neighborhood_best = INT_SET_NULL;
int min_size = INT_MAX;
int size_before = 0, improvement = 0; // logging
float max_similarity = 0;
SOLUTION_SET to_compare = {};
int it = 0; // logging
bool tie = false, tr;
SOLUTION_SET rn = restricted_neighborhood(g, initial, guiding);
while (rn.size() > 0) {
printf("FPR ITERATION %d: RN has %d solutions.\n", it, rn.size());
neighborhood_best = best_solution(g, rn, guiding, tr); // best & closest to guiding solution
if (debug) printf("Neighborhood best solution: [%d].\n", neighborhood_best.size());
if (neighborhood_best.size() > initial.size()) {
if (debug) printf("Neighborhood best [%d] is worse than initial [%d].\n", neighborhood_best.size(), initial.size());
return general_best != INT_SET_NULL ? general_best : initial;
}
if (neighborhood_best == general_best) { // can't keep going if the solutions are equal
if (debug) printf("Neighborhood best and general best are the same.\n"); // TODO: verify if this happens
break;
}
/* neighborhood_best vs. general_best */
if (general_best == INT_SET_NULL) {
general_best = neighborhood_best; // first general best
} else {
to_compare.insert(neighborhood_best);
to_compare.insert(general_best);
general_best = best_solution(g, to_compare, guiding, tie);
if (tie) {
printf("Neighborhood best and general best are equal in size [%d] and similarity. Finishing FPR.\n", general_best.size());
return general_best;
}
to_compare.clear();
}
/* general best might not be a local optimum: run local search */
size_before = general_best.size();
general_best = local_search(g, 100, 300, general_best);
improvement = size_before - general_best.size();
if (debug) {
if (!improvement) printf("Local search solution: [%d] (general best not improved).\n", general_best.size());
else printf("Local search solution: [%d] (general best improved by %d).\n", general_best.size(), improvement);
}
/* update general best info */
min_size = general_best.size();
max_similarity = similarity(g, general_best, guiding);
if (min_size <= guiding.size()) {
printf("Finishing FPR: General best [%d] equal to or better than guiding [%d].\n", min_size, guiding.size());
break;
} else {
// generate new restricted neighborhood to keep going
rn = restricted_neighborhood(g, general_best, guiding);
it++;
}
}
if (debug && rn.size() == 0) printf("Finishing FPR: RN is empty.\n");
return general_best == INT_SET_NULL ? initial : general_best;
}
/*
GRASP with path relinking
*/
SOLUTION_SET update_elite_set(INT_SET new_solution, SOLUTION_SET elite_set, int max_size, int delta_threshold, bool debug) {
if (new_solution == INT_SET_NULL) {
printf("[!] Update called on null solution.");
return elite_set;
}
int current_size = elite_set.size();
if (current_size < max_size) { // hasn't reached max_size: decide whether to include solution
if (current_size == 0) {
elite_set.insert(new_solution);
if (debug) printf("Solution [%d] added to elite set.\n", new_solution.size());
return elite_set;
} else {
int delta = -1, min_delta = INT_MAX;
for (auto e_it = elite_set.begin(); e_it != elite_set.end(); e_it++) {
delta = symmetric_difference(new_solution, *e_it).size();
if (delta < min_delta) min_delta = delta;
}
if (min_delta > delta_threshold) { // only include if min_delta is higher than the threshold
elite_set.insert(new_solution);
return elite_set;
} else {
if (debug) printf("Elite set not full but solution [%] wasn't included.\n", new_solution.size());
}
}
} else { // elite set is in its max size: decide between keeping it as it is or choosing solution to replace with new_solution
int largest_size = 0, size = -1;
int delta = -1, min_delta = INT_MAX;
for (auto e_it = elite_set.begin(); e_it != elite_set.end(); e_it++) {
/* max size */
size = e_it->size();
if (size > largest_size) largest_size = size;
/* min delta */
delta = symmetric_difference(new_solution, *e_it).size();
if (delta < min_delta) {
min_delta = delta;
}
}
if ((new_solution.size() < largest_size) && (min_delta > delta_threshold)) { // solution should be included: choose which to remove
auto rm_it = elite_set.end();
min_delta = INT_MAX, delta = -1;
for (auto e_it = elite_set.begin(); e_it != elite_set.end(); e_it++) {
if (e_it->size() < new_solution.size()) continue;
delta = symmetric_difference(new_solution, *e_it).size();
if (delta < min_delta) {
min_delta = delta;
rm_it = e_it;
}
}
if (rm_it != elite_set.end()) {
if (debug) printf("Elite set is full -> removing [%d] to include [%d].\n", rm_it->size(), new_solution.size());
elite_set.erase(rm_it);
elite_set.insert(new_solution);
} else {
printf("YIKES");
}
}
}
return elite_set;
}
INT_SET grasp_pr(Graph &g, float alpha, int max_time_ms, int max_iterations, int max_elite, bool debug) {
INT_SET solution = {}, best_solution = {}, random_elite = {};
int solution_size = 0, best_solution_size = INT_MAX, iterations = 0, total_elapsed_time = 0, dt = 0;
TIMESTAMP t0 = time();
SOLUTION_SET elite_set = {};
srand(time(NULL));
/* main loop of GRASP procedure */
while ((iterations < max_iterations) && (total_elapsed_time < max_time_ms)) { // stopping conditions
printf("GRASP-PR ITERATION %d.\n", iterations);
/*
phase 1: construction (semi-greedy)
*/
t0 = time();
solution = semi_greedy(g, time(NULL), alpha);
dt = elapsed_time(t0); // semi-greedy runtime
if (!verify_vertex_cover(g, solution)) {
if (debug) printf("Semi-greedy solution (INVALID): [%d].\n", solution.size());
t0 = time();
solution = repair(g, solution, iterations+1);
dt += elapsed_time(t0); // repair runtime
if (debug) printf("Repaired solution: [%d].\n", solution.size());
} else {
if (debug) printf("Semi-greedy solution: [%d].\n", solution.size());
}
/*
phase 2: local search
*/
int max_it = 100, max_it_1st = 300;
if (debug) printf("Running local search...\n");
t0 = time();
solution = local_search(g, max_it, max_it_1st, solution);
dt += elapsed_time(t0); // local search runtime
solution_size = solution.size();
if (debug) printf("Local search solution: [%d].\n", solution_size);
/*
phase 3: path relinking between current solution and a random solution from elite set
*/
t0 = time();
if (elite_set.size() > 0) {
/* choose random solution from elite set */
if (elite_set.size() == 1) random_elite = *elite_set.begin();
else {
auto it = elite_set.begin();
advance(it, rand() % elite_set.size());
random_elite = *it;
}
if (debug) printf("Random elite set solution to relink: [%d].\n", random_elite.size());
solution = forward_path_relinking(g, solution, random_elite, true);
solution_size = solution.size();
if (debug) printf("FPR solution: [%d].\n", solution_size);
}
elite_set = update_elite_set(solution, elite_set, max_elite, 0, debug);
dt += elapsed_time(t0); // path-relinking runtime
/*
conclusion: replace current best solution if the one found is better
*/
if (solution_size < best_solution_size) {
best_solution = solution;
best_solution_size = solution_size;
}
total_elapsed_time += dt;
iterations++;
}
if (debug) printf("Stopped GRASP-PR at %d elapsed milliseconds & %d iterations.\n", total_elapsed_time, iterations);
if (verify_vertex_cover(g, solution)) {
return best_solution;
} else {
printf("GRASP returned invalid solution!\n");
return INT_SET_NULL;
}
}