alpar@1: /* MISP, Maximum Independent Set Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* Let G = (V,E) be an undirected graph with vertex set V and edge set
alpar@1:    E. Vertices u, v in V are non-adjacent if (u,v) not in E. A subset
alpar@1:    of the vertices S within V is independent if all vertices in S are
alpar@1:    pairwise non-adjacent. The Maximum Independent Set Problem (MISP) is
alpar@1:    to find an independent set having the largest cardinality. */
alpar@1: 
alpar@1: param n, integer, > 0;
alpar@1: /* number of vertices */
alpar@1: 
alpar@1: set V := 1..n;
alpar@1: /* set of vertices */
alpar@1: 
alpar@1: set E within V cross V;
alpar@1: /* set of edges */
alpar@1: 
alpar@1: var x{i in V}, binary;
alpar@1: /* x[i] = 1 means vertex i belongs to independent set */
alpar@1: 
alpar@1: s.t. edge{(i,j) in E}: x[i] + x[j] <= 1;
alpar@1: /* if there is edge (i,j), vertices i and j cannot belong to the same
alpar@1:    independent set */
alpar@1: 
alpar@1: maximize obj: sum{i in V} x[i];
alpar@1: /* the objective is to maximize the cardinality of independent set */
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data corresponds to the test instance from:
alpar@1: 
alpar@1:    M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN
alpar@1:    subroutines for approximate solution of the maximum independent set
alpar@1:    problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4,
alpar@1:    December 1998, pp. 386-394. */
alpar@1: 
alpar@1: /* The optimal solution is 7 */
alpar@1: 
alpar@1: param n := 50;
alpar@1: 
alpar@1: set E :=
alpar@1:  1 2
alpar@1:  1 3
alpar@1:  1 5
alpar@1:  1 7
alpar@1:  1 8
alpar@1:  1 12
alpar@1:  1 15
alpar@1:  1 16
alpar@1:  1 19
alpar@1:  1 20
alpar@1:  1 21
alpar@1:  1 22
alpar@1:  1 28
alpar@1:  1 30
alpar@1:  1 34
alpar@1:  1 35
alpar@1:  1 37
alpar@1:  1 41
alpar@1:  1 42
alpar@1:  1 47
alpar@1:  1 50
alpar@1:  2 3
alpar@1:  2 5
alpar@1:  2 6
alpar@1:  2 7
alpar@1:  2 8
alpar@1:  2 9
alpar@1:  2 10
alpar@1:  2 13
alpar@1:  2 17
alpar@1:  2 19
alpar@1:  2 20
alpar@1:  2 21
alpar@1:  2 23
alpar@1:  2 25
alpar@1:  2 26
alpar@1:  2 29
alpar@1:  2 31
alpar@1:  2 35
alpar@1:  2 36
alpar@1:  2 44
alpar@1:  2 45
alpar@1:  2 46
alpar@1:  2 50
alpar@1:  3 5
alpar@1:  3 6
alpar@1:  3 8
alpar@1:  3 9
alpar@1:  3 10
alpar@1:  3 11
alpar@1:  3 14
alpar@1:  3 16
alpar@1:  3 23
alpar@1:  3 24
alpar@1:  3 26
alpar@1:  3 27
alpar@1:  3 28
alpar@1:  3 29
alpar@1:  3 30
alpar@1:  3 31
alpar@1:  3 34
alpar@1:  3 35
alpar@1:  3 36
alpar@1:  3 39
alpar@1:  3 41
alpar@1:  3 42
alpar@1:  3 43
alpar@1:  3 44
alpar@1:  3 50
alpar@1:  4 6
alpar@1:  4 7
alpar@1:  4 9
alpar@1:  4 10
alpar@1:  4 11
alpar@1:  4 13
alpar@1:  4 14
alpar@1:  4 15
alpar@1:  4 17
alpar@1:  4 21
alpar@1:  4 22
alpar@1:  4 23
alpar@1:  4 24
alpar@1:  4 25
alpar@1:  4 27
alpar@1:  4 28
alpar@1:  4 30
alpar@1:  4 31
alpar@1:  4 33
alpar@1:  4 34
alpar@1:  4 35
alpar@1:  4 36
alpar@1:  4 37
alpar@1:  4 38
alpar@1:  4 40
alpar@1:  4 41
alpar@1:  4 42
alpar@1:  4 46
alpar@1:  4 49
alpar@1:  5 6
alpar@1:  5 11
alpar@1:  5 14
alpar@1:  5 21
alpar@1:  5 24
alpar@1:  5 25
alpar@1:  5 28
alpar@1:  5 35
alpar@1:  5 38
alpar@1:  5 39
alpar@1:  5 41
alpar@1:  5 44
alpar@1:  5 49
alpar@1:  5 50
alpar@1:  6 8
alpar@1:  6 9
alpar@1:  6 10
alpar@1:  6 13
alpar@1:  6 14
alpar@1:  6 16
alpar@1:  6 17
alpar@1:  6 19
alpar@1:  6 22
alpar@1:  6 23
alpar@1:  6 26
alpar@1:  6 27
alpar@1:  6 30
alpar@1:  6 34
alpar@1:  6 35
alpar@1:  6 38
alpar@1:  6 39
alpar@1:  6 40
alpar@1:  6 41
alpar@1:  6 44
alpar@1:  6 45
alpar@1:  6 47
alpar@1:  6 50
alpar@1:  7 8
alpar@1:  7 9
alpar@1:  7 10
alpar@1:  7 11
alpar@1:  7 13
alpar@1:  7 15
alpar@1:  7 16
alpar@1:  7 18
alpar@1:  7 20
alpar@1:  7 22
alpar@1:  7 23
alpar@1:  7 24
alpar@1:  7 25
alpar@1:  7 33
alpar@1:  7 35
alpar@1:  7 36
alpar@1:  7 38
alpar@1:  7 43
alpar@1:  7 45
alpar@1:  7 46
alpar@1:  7 47
alpar@1:  8 10
alpar@1:  8 11
alpar@1:  8 13
alpar@1:  8 16
alpar@1:  8 17
alpar@1:  8 18
alpar@1:  8 19
alpar@1:  8 20
alpar@1:  8 21
alpar@1:  8 22
alpar@1:  8 23
alpar@1:  8 24
alpar@1:  8 25
alpar@1:  8 26
alpar@1:  8 33
alpar@1:  8 35
alpar@1:  8 36
alpar@1:  8 39
alpar@1:  8 42
alpar@1:  8 44
alpar@1:  8 48
alpar@1:  8 49
alpar@1:  9 12
alpar@1:  9 14
alpar@1:  9 17
alpar@1:  9 19
alpar@1:  9 20
alpar@1:  9 23
alpar@1:  9 28
alpar@1:  9 30
alpar@1:  9 31
alpar@1:  9 32
alpar@1:  9 33
alpar@1:  9 34
alpar@1:  9 38
alpar@1:  9 39
alpar@1:  9 42
alpar@1:  9 44
alpar@1:  9 45
alpar@1:  9 46
alpar@1:  10 11
alpar@1:  10 13
alpar@1:  10 15
alpar@1:  10 16
alpar@1:  10 17
alpar@1:  10 20
alpar@1:  10 21
alpar@1:  10 22
alpar@1:  10 23
alpar@1:  10 25
alpar@1:  10 26
alpar@1:  10 27
alpar@1:  10 28
alpar@1:  10 30
alpar@1:  10 31
alpar@1:  10 32
alpar@1:  10 37
alpar@1:  10 38
alpar@1:  10 41
alpar@1:  10 43
alpar@1:  10 44
alpar@1:  10 45
alpar@1:  10 50
alpar@1:  11 12
alpar@1:  11 14
alpar@1:  11 15
alpar@1:  11 18
alpar@1:  11 21
alpar@1:  11 24
alpar@1:  11 25
alpar@1:  11 26
alpar@1:  11 29
alpar@1:  11 32
alpar@1:  11 33
alpar@1:  11 35
alpar@1:  11 36
alpar@1:  11 37
alpar@1:  11 39
alpar@1:  11 40
alpar@1:  11 42
alpar@1:  11 43
alpar@1:  11 45
alpar@1:  11 47
alpar@1:  11 49
alpar@1:  11 50
alpar@1:  12 13
alpar@1:  12 16
alpar@1:  12 17
alpar@1:  12 19
alpar@1:  12 24
alpar@1:  12 25
alpar@1:  12 26
alpar@1:  12 30
alpar@1:  12 31
alpar@1:  12 32
alpar@1:  12 34
alpar@1:  12 36
alpar@1:  12 37
alpar@1:  12 39
alpar@1:  12 41
alpar@1:  12 44
alpar@1:  12 47
alpar@1:  12 48
alpar@1:  12 49
alpar@1:  13 15
alpar@1:  13 16
alpar@1:  13 18
alpar@1:  13 19
alpar@1:  13 20
alpar@1:  13 22
alpar@1:  13 23
alpar@1:  13 24
alpar@1:  13 27
alpar@1:  13 28
alpar@1:  13 29
alpar@1:  13 31
alpar@1:  13 33
alpar@1:  13 35
alpar@1:  13 36
alpar@1:  13 37
alpar@1:  13 44
alpar@1:  13 47
alpar@1:  13 49
alpar@1:  13 50
alpar@1:  14 15
alpar@1:  14 16
alpar@1:  14 17
alpar@1:  14 18
alpar@1:  14 19
alpar@1:  14 20
alpar@1:  14 21
alpar@1:  14 26
alpar@1:  14 28
alpar@1:  14 29
alpar@1:  14 30
alpar@1:  14 31
alpar@1:  14 32
alpar@1:  14 34
alpar@1:  14 35
alpar@1:  14 36
alpar@1:  14 38
alpar@1:  14 39
alpar@1:  14 41
alpar@1:  14 44
alpar@1:  14 46
alpar@1:  14 47
alpar@1:  14 48
alpar@1:  15 18
alpar@1:  15 21
alpar@1:  15 22
alpar@1:  15 23
alpar@1:  15 25
alpar@1:  15 28
alpar@1:  15 29
alpar@1:  15 30
alpar@1:  15 33
alpar@1:  15 34
alpar@1:  15 36
alpar@1:  15 37
alpar@1:  15 38
alpar@1:  15 39
alpar@1:  15 40
alpar@1:  15 43
alpar@1:  15 44
alpar@1:  15 46
alpar@1:  15 50
alpar@1:  16 17
alpar@1:  16 19
alpar@1:  16 20
alpar@1:  16 25
alpar@1:  16 26
alpar@1:  16 29
alpar@1:  16 35
alpar@1:  16 38
alpar@1:  16 39
alpar@1:  16 40
alpar@1:  16 41
alpar@1:  16 42
alpar@1:  16 44
alpar@1:  17 18
alpar@1:  17 19
alpar@1:  17 21
alpar@1:  17 22
alpar@1:  17 23
alpar@1:  17 25
alpar@1:  17 26
alpar@1:  17 28
alpar@1:  17 29
alpar@1:  17 33
alpar@1:  17 37
alpar@1:  17 44
alpar@1:  17 45
alpar@1:  17 48
alpar@1:  18 20
alpar@1:  18 24
alpar@1:  18 27
alpar@1:  18 28
alpar@1:  18 31
alpar@1:  18 32
alpar@1:  18 34
alpar@1:  18 35
alpar@1:  18 36
alpar@1:  18 37
alpar@1:  18 38
alpar@1:  18 45
alpar@1:  18 48
alpar@1:  18 49
alpar@1:  18 50
alpar@1:  19 22
alpar@1:  19 24
alpar@1:  19 28
alpar@1:  19 29
alpar@1:  19 36
alpar@1:  19 37
alpar@1:  19 39
alpar@1:  19 41
alpar@1:  19 43
alpar@1:  19 45
alpar@1:  19 48
alpar@1:  19 49
alpar@1:  20 21
alpar@1:  20 22
alpar@1:  20 24
alpar@1:  20 25
alpar@1:  20 26
alpar@1:  20 27
alpar@1:  20 29
alpar@1:  20 30
alpar@1:  20 31
alpar@1:  20 33
alpar@1:  20 34
alpar@1:  20 35
alpar@1:  20 38
alpar@1:  20 39
alpar@1:  20 41
alpar@1:  20 42
alpar@1:  20 43
alpar@1:  20 44
alpar@1:  20 45
alpar@1:  20 46
alpar@1:  20 48
alpar@1:  20 49
alpar@1:  21 22
alpar@1:  21 23
alpar@1:  21 29
alpar@1:  21 31
alpar@1:  21 35
alpar@1:  21 38
alpar@1:  21 42
alpar@1:  21 46
alpar@1:  21 47
alpar@1:  22 23
alpar@1:  22 26
alpar@1:  22 27
alpar@1:  22 28
alpar@1:  22 29
alpar@1:  22 30
alpar@1:  22 39
alpar@1:  22 40
alpar@1:  22 41
alpar@1:  22 42
alpar@1:  22 44
alpar@1:  22 45
alpar@1:  22 46
alpar@1:  22 47
alpar@1:  22 49
alpar@1:  22 50
alpar@1:  23 28
alpar@1:  23 31
alpar@1:  23 32
alpar@1:  23 33
alpar@1:  23 34
alpar@1:  23 35
alpar@1:  23 36
alpar@1:  23 39
alpar@1:  23 40
alpar@1:  23 41
alpar@1:  23 42
alpar@1:  23 44
alpar@1:  23 45
alpar@1:  23 48
alpar@1:  23 49
alpar@1:  23 50
alpar@1:  24 25
alpar@1:  24 27
alpar@1:  24 29
alpar@1:  24 30
alpar@1:  24 31
alpar@1:  24 33
alpar@1:  24 34
alpar@1:  24 38
alpar@1:  24 42
alpar@1:  24 43
alpar@1:  24 44
alpar@1:  24 49
alpar@1:  24 50
alpar@1:  25 26
alpar@1:  25 27
alpar@1:  25 29
alpar@1:  25 30
alpar@1:  25 33
alpar@1:  25 34
alpar@1:  25 36
alpar@1:  25 38
alpar@1:  25 40
alpar@1:  25 41
alpar@1:  25 42
alpar@1:  25 44
alpar@1:  25 46
alpar@1:  25 47
alpar@1:  25 48
alpar@1:  25 49
alpar@1:  26 28
alpar@1:  26 31
alpar@1:  26 32
alpar@1:  26 33
alpar@1:  26 37
alpar@1:  26 38
alpar@1:  26 39
alpar@1:  26 40
alpar@1:  26 41
alpar@1:  26 42
alpar@1:  26 45
alpar@1:  26 47
alpar@1:  26 48
alpar@1:  26 49
alpar@1:  27 29
alpar@1:  27 30
alpar@1:  27 33
alpar@1:  27 34
alpar@1:  27 35
alpar@1:  27 39
alpar@1:  27 40
alpar@1:  27 46
alpar@1:  27 48
alpar@1:  28 29
alpar@1:  28 37
alpar@1:  28 40
alpar@1:  28 42
alpar@1:  28 44
alpar@1:  28 46
alpar@1:  28 47
alpar@1:  28 50
alpar@1:  29 35
alpar@1:  29 38
alpar@1:  29 39
alpar@1:  29 41
alpar@1:  29 42
alpar@1:  29 48
alpar@1:  30 31
alpar@1:  30 32
alpar@1:  30 35
alpar@1:  30 37
alpar@1:  30 38
alpar@1:  30 40
alpar@1:  30 43
alpar@1:  30 45
alpar@1:  30 46
alpar@1:  30 47
alpar@1:  30 48
alpar@1:  31 33
alpar@1:  31 35
alpar@1:  31 38
alpar@1:  31 40
alpar@1:  31 41
alpar@1:  31 42
alpar@1:  31 44
alpar@1:  31 46
alpar@1:  31 47
alpar@1:  31 50
alpar@1:  32 33
alpar@1:  32 35
alpar@1:  32 39
alpar@1:  32 40
alpar@1:  32 46
alpar@1:  32 49
alpar@1:  32 50
alpar@1:  33 34
alpar@1:  33 36
alpar@1:  33 37
alpar@1:  33 40
alpar@1:  33 42
alpar@1:  33 43
alpar@1:  33 44
alpar@1:  33 45
alpar@1:  33 50
alpar@1:  34 35
alpar@1:  34 36
alpar@1:  34 37
alpar@1:  34 38
alpar@1:  34 40
alpar@1:  34 43
alpar@1:  34 44
alpar@1:  34 49
alpar@1:  34 50
alpar@1:  35 36
alpar@1:  35 38
alpar@1:  35 41
alpar@1:  35 42
alpar@1:  35 43
alpar@1:  35 45
alpar@1:  35 46
alpar@1:  35 47
alpar@1:  35 49
alpar@1:  35 50
alpar@1:  36 37
alpar@1:  36 39
alpar@1:  36 40
alpar@1:  36 41
alpar@1:  36 42
alpar@1:  36 43
alpar@1:  36 48
alpar@1:  36 50
alpar@1:  37 38
alpar@1:  37 41
alpar@1:  37 43
alpar@1:  37 46
alpar@1:  37 47
alpar@1:  37 48
alpar@1:  37 49
alpar@1:  37 50
alpar@1:  38 41
alpar@1:  38 45
alpar@1:  38 46
alpar@1:  38 48
alpar@1:  38 49
alpar@1:  38 50
alpar@1:  39 43
alpar@1:  39 46
alpar@1:  39 47
alpar@1:  39 48
alpar@1:  39 49
alpar@1:  40 43
alpar@1:  40 45
alpar@1:  40 48
alpar@1:  40 50
alpar@1:  41 42
alpar@1:  41 43
alpar@1:  41 44
alpar@1:  41 45
alpar@1:  41 46
alpar@1:  41 48
alpar@1:  41 49
alpar@1:  42 43
alpar@1:  42 44
alpar@1:  42 46
alpar@1:  42 48
alpar@1:  42 49
alpar@1:  43 45
alpar@1:  43 46
alpar@1:  43 48
alpar@1:  43 50
alpar@1:  44 45
alpar@1:  44 48
alpar@1:  45 46
alpar@1:  45 47
alpar@1:  45 48
alpar@1:  46 49
alpar@1:  47 49
alpar@1:  47 50
alpar@1:  48 49
alpar@1:  48 50
alpar@1:  49 50
alpar@1: ;
alpar@1: 
alpar@1: end;