| author | Alpar Juttner <alpar@cs.elte.hu> |
| Mon, 06 Dec 2010 13:09:21 +0100 | |
| changeset 1 | c445c931472f |
| permissions | -rw-r--r-- |
1 /* MISP, Maximum Independent Set Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
5 /* Let G = (V,E) be an undirected graph with vertex set V and edge set
6 E. Vertices u, v in V are non-adjacent if (u,v) not in E. A subset
7 of the vertices S within V is independent if all vertices in S are
8 pairwise non-adjacent. The Maximum Independent Set Problem (MISP) is
9 to find an independent set having the largest cardinality. */
11 param n, integer, > 0;
12 /* number of vertices */
14 set V := 1..n;
15 /* set of vertices */
17 set E within V cross V;
18 /* set of edges */
20 var x{i in V}, binary;
21 /* x[i] = 1 means vertex i belongs to independent set */
23 s.t. edge{(i,j) in E}: x[i] + x[j] <= 1;
24 /* if there is edge (i,j), vertices i and j cannot belong to the same
25 independent set */
27 maximize obj: sum{i in V} x[i];
28 /* the objective is to maximize the cardinality of independent set */
30 data;
32 /* These data corresponds to the test instance from:
34 M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN
35 subroutines for approximate solution of the maximum independent set
36 problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4,
37 December 1998, pp. 386-394. */
39 /* The optimal solution is 7 */
41 param n := 50;
43 set E :=
44 1 2
45 1 3
46 1 5
47 1 7
48 1 8
49 1 12
50 1 15
51 1 16
52 1 19
53 1 20
54 1 21
55 1 22
56 1 28
57 1 30
58 1 34
59 1 35
60 1 37
61 1 41
62 1 42
63 1 47
64 1 50
65 2 3
66 2 5
67 2 6
68 2 7
69 2 8
70 2 9
71 2 10
72 2 13
73 2 17
74 2 19
75 2 20
76 2 21
77 2 23
78 2 25
79 2 26
80 2 29
81 2 31
82 2 35
83 2 36
84 2 44
85 2 45
86 2 46
87 2 50
88 3 5
89 3 6
90 3 8
91 3 9
92 3 10
93 3 11
94 3 14
95 3 16
96 3 23
97 3 24
98 3 26
99 3 27
100 3 28
101 3 29
102 3 30
103 3 31
104 3 34
105 3 35
106 3 36
107 3 39
108 3 41
109 3 42
110 3 43
111 3 44
112 3 50
113 4 6
114 4 7
115 4 9
116 4 10
117 4 11
118 4 13
119 4 14
120 4 15
121 4 17
122 4 21
123 4 22
124 4 23
125 4 24
126 4 25
127 4 27
128 4 28
129 4 30
130 4 31
131 4 33
132 4 34
133 4 35
134 4 36
135 4 37
136 4 38
137 4 40
138 4 41
139 4 42
140 4 46
141 4 49
142 5 6
143 5 11
144 5 14
145 5 21
146 5 24
147 5 25
148 5 28
149 5 35
150 5 38
151 5 39
152 5 41
153 5 44
154 5 49
155 5 50
156 6 8
157 6 9
158 6 10
159 6 13
160 6 14
161 6 16
162 6 17
163 6 19
164 6 22
165 6 23
166 6 26
167 6 27
168 6 30
169 6 34
170 6 35
171 6 38
172 6 39
173 6 40
174 6 41
175 6 44
176 6 45
177 6 47
178 6 50
179 7 8
180 7 9
181 7 10
182 7 11
183 7 13
184 7 15
185 7 16
186 7 18
187 7 20
188 7 22
189 7 23
190 7 24
191 7 25
192 7 33
193 7 35
194 7 36
195 7 38
196 7 43
197 7 45
198 7 46
199 7 47
200 8 10
201 8 11
202 8 13
203 8 16
204 8 17
205 8 18
206 8 19
207 8 20
208 8 21
209 8 22
210 8 23
211 8 24
212 8 25
213 8 26
214 8 33
215 8 35
216 8 36
217 8 39
218 8 42
219 8 44
220 8 48
221 8 49
222 9 12
223 9 14
224 9 17
225 9 19
226 9 20
227 9 23
228 9 28
229 9 30
230 9 31
231 9 32
232 9 33
233 9 34
234 9 38
235 9 39
236 9 42
237 9 44
238 9 45
239 9 46
240 10 11
241 10 13
242 10 15
243 10 16
244 10 17
245 10 20
246 10 21
247 10 22
248 10 23
249 10 25
250 10 26
251 10 27
252 10 28
253 10 30
254 10 31
255 10 32
256 10 37
257 10 38
258 10 41
259 10 43
260 10 44
261 10 45
262 10 50
263 11 12
264 11 14
265 11 15
266 11 18
267 11 21
268 11 24
269 11 25
270 11 26
271 11 29
272 11 32
273 11 33
274 11 35
275 11 36
276 11 37
277 11 39
278 11 40
279 11 42
280 11 43
281 11 45
282 11 47
283 11 49
284 11 50
285 12 13
286 12 16
287 12 17
288 12 19
289 12 24
290 12 25
291 12 26
292 12 30
293 12 31
294 12 32
295 12 34
296 12 36
297 12 37
298 12 39
299 12 41
300 12 44
301 12 47
302 12 48
303 12 49
304 13 15
305 13 16
306 13 18
307 13 19
308 13 20
309 13 22
310 13 23
311 13 24
312 13 27
313 13 28
314 13 29
315 13 31
316 13 33
317 13 35
318 13 36
319 13 37
320 13 44
321 13 47
322 13 49
323 13 50
324 14 15
325 14 16
326 14 17
327 14 18
328 14 19
329 14 20
330 14 21
331 14 26
332 14 28
333 14 29
334 14 30
335 14 31
336 14 32
337 14 34
338 14 35
339 14 36
340 14 38
341 14 39
342 14 41
343 14 44
344 14 46
345 14 47
346 14 48
347 15 18
348 15 21
349 15 22
350 15 23
351 15 25
352 15 28
353 15 29
354 15 30
355 15 33
356 15 34
357 15 36
358 15 37
359 15 38
360 15 39
361 15 40
362 15 43
363 15 44
364 15 46
365 15 50
366 16 17
367 16 19
368 16 20
369 16 25
370 16 26
371 16 29
372 16 35
373 16 38
374 16 39
375 16 40
376 16 41
377 16 42
378 16 44
379 17 18
380 17 19
381 17 21
382 17 22
383 17 23
384 17 25
385 17 26
386 17 28
387 17 29
388 17 33
389 17 37
390 17 44
391 17 45
392 17 48
393 18 20
394 18 24
395 18 27
396 18 28
397 18 31
398 18 32
399 18 34
400 18 35
401 18 36
402 18 37
403 18 38
404 18 45
405 18 48
406 18 49
407 18 50
408 19 22
409 19 24
410 19 28
411 19 29
412 19 36
413 19 37
414 19 39
415 19 41
416 19 43
417 19 45
418 19 48
419 19 49
420 20 21
421 20 22
422 20 24
423 20 25
424 20 26
425 20 27
426 20 29
427 20 30
428 20 31
429 20 33
430 20 34
431 20 35
432 20 38
433 20 39
434 20 41
435 20 42
436 20 43
437 20 44
438 20 45
439 20 46
440 20 48
441 20 49
442 21 22
443 21 23
444 21 29
445 21 31
446 21 35
447 21 38
448 21 42
449 21 46
450 21 47
451 22 23
452 22 26
453 22 27
454 22 28
455 22 29
456 22 30
457 22 39
458 22 40
459 22 41
460 22 42
461 22 44
462 22 45
463 22 46
464 22 47
465 22 49
466 22 50
467 23 28
468 23 31
469 23 32
470 23 33
471 23 34
472 23 35
473 23 36
474 23 39
475 23 40
476 23 41
477 23 42
478 23 44
479 23 45
480 23 48
481 23 49
482 23 50
483 24 25
484 24 27
485 24 29
486 24 30
487 24 31
488 24 33
489 24 34
490 24 38
491 24 42
492 24 43
493 24 44
494 24 49
495 24 50
496 25 26
497 25 27
498 25 29
499 25 30
500 25 33
501 25 34
502 25 36
503 25 38
504 25 40
505 25 41
506 25 42
507 25 44
508 25 46
509 25 47
510 25 48
511 25 49
512 26 28
513 26 31
514 26 32
515 26 33
516 26 37
517 26 38
518 26 39
519 26 40
520 26 41
521 26 42
522 26 45
523 26 47
524 26 48
525 26 49
526 27 29
527 27 30
528 27 33
529 27 34
530 27 35
531 27 39
532 27 40
533 27 46
534 27 48
535 28 29
536 28 37
537 28 40
538 28 42
539 28 44
540 28 46
541 28 47
542 28 50
543 29 35
544 29 38
545 29 39
546 29 41
547 29 42
548 29 48
549 30 31
550 30 32
551 30 35
552 30 37
553 30 38
554 30 40
555 30 43
556 30 45
557 30 46
558 30 47
559 30 48
560 31 33
561 31 35
562 31 38
563 31 40
564 31 41
565 31 42
566 31 44
567 31 46
568 31 47
569 31 50
570 32 33
571 32 35
572 32 39
573 32 40
574 32 46
575 32 49
576 32 50
577 33 34
578 33 36
579 33 37
580 33 40
581 33 42
582 33 43
583 33 44
584 33 45
585 33 50
586 34 35
587 34 36
588 34 37
589 34 38
590 34 40
591 34 43
592 34 44
593 34 49
594 34 50
595 35 36
596 35 38
597 35 41
598 35 42
599 35 43
600 35 45
601 35 46
602 35 47
603 35 49
604 35 50
605 36 37
606 36 39
607 36 40
608 36 41
609 36 42
610 36 43
611 36 48
612 36 50
613 37 38
614 37 41
615 37 43
616 37 46
617 37 47
618 37 48
619 37 49
620 37 50
621 38 41
622 38 45
623 38 46
624 38 48
625 38 49
626 38 50
627 39 43
628 39 46
629 39 47
630 39 48
631 39 49
632 40 43
633 40 45
634 40 48
635 40 50
636 41 42
637 41 43
638 41 44
639 41 45
640 41 46
641 41 48
642 41 49
643 42 43
644 42 44
645 42 46
646 42 48
647 42 49
648 43 45
649 43 46
650 43 48
651 43 50
652 44 45
653 44 48
654 45 46
655 45 47
656 45 48
657 46 49
658 47 49
659 47 50
660 48 49
661 48 50
662 49 50
663 ;
665 end;