/* MISP, Maximum Independent Set Problem */

 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

 /* Let G = (V,E) be an undirected graph with vertex set V and edge set

    E. Vertices u, v in V are non-adjacent if (u,v) not in E. A subset

    of the vertices S within V is independent if all vertices in S are

    pairwise non-adjacent. The Maximum Independent Set Problem (MISP) is

    to find an independent set having the largest cardinality. */

 param n, integer, > 0;

 /* number of vertices */

 set V := 1..n;

 /* set of vertices */

 set E within V cross V;

 /* set of edges */

 var x{i in V}, binary;

 /* x[i] = 1 means vertex i belongs to independent set */

 s.t. edge{(i,j) in E}: x[i] + x[j] <= 1;

 /* if there is edge (i,j), vertices i and j cannot belong to the same

    independent set */

 maximize obj: sum{i in V} x[i];

 /* the objective is to maximize the cardinality of independent set */

 data;

 /* These data corresponds to the test instance from:

    M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN

    subroutines for approximate solution of the maximum independent set

    problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4,

    December 1998, pp. 386-394. */

 /* The optimal solution is 7 */

 param n := 50;

 set E :=

  1 2

  1 3

  1 5

  1 7

  1 8

  1 12

  1 15

  1 16

  1 19

  1 20

  1 21

  1 22

  1 28

  1 30

  1 34

  1 35

  1 37

  1 41

  1 42

  1 47

  1 50

  2 3

  2 5

  2 6

  2 7

  2 8

  2 9

  2 10

  2 13

  2 17

  2 19

  2 20

  2 21

  2 23

  2 25

  2 26

  2 29

  2 31

  2 35

  2 36

  2 44

  2 45

  2 46

  2 50

  3 5

  3 6

  3 8

  3 9

  3 10

  3 11

  3 14

  3 16

  3 23

  3 24

  3 26

  3 27

  3 28

  3 29

  3 30

  3 31

  3 34

  3 35

  3 36

  3 39

  3 41

  3 42

  3 43

  3 44

  3 50

  4 6

  4 7

  4 9

  4 10

  4 11

  4 13

  4 14

  4 15

  4 17

  4 21

  4 22

  4 23

  4 24

  4 25

  4 27

  4 28

  4 30

  4 31

  4 33

  4 34

  4 35

  4 36

  4 37

  4 38

  4 40

  4 41

  4 42

  4 46

  4 49

  5 6

  5 11

  5 14

  5 21

  5 24

  5 25

  5 28

  5 35

  5 38

  5 39

  5 41

  5 44

  5 49

  5 50

  6 8

  6 9

  6 10

  6 13

  6 14

  6 16

  6 17

  6 19

  6 22

  6 23

  6 26

  6 27

  6 30

  6 34

  6 35

  6 38

  6 39

  6 40

  6 41

  6 44

  6 45

  6 47

  6 50

  7 8

  7 9

  7 10

  7 11

  7 13

  7 15

  7 16

  7 18

  7 20

  7 22

  7 23

  7 24

  7 25

  7 33

  7 35

  7 36

  7 38

  7 43

  7 45

  7 46

  7 47

  8 10

  8 11

  8 13

  8 16

  8 17

  8 18

  8 19

  8 20

  8 21

  8 22

  8 23

  8 24

  8 25

  8 26

  8 33

  8 35

  8 36

  8 39

  8 42

  8 44

  8 48

  8 49

  9 12

  9 14

  9 17

  9 19

  9 20

  9 23

  9 28

  9 30

  9 31

  9 32

  9 33

  9 34

  9 38

  9 39

  9 42

  9 44

  9 45

  9 46

  10 11

  10 13

  10 15

  10 16

  10 17

  10 20

  10 21

  10 22

  10 23

  10 25

  10 26

  10 27

  10 28

  10 30

  10 31

  10 32

  10 37

  10 38

  10 41

  10 43

  10 44

  10 45

  10 50

  11 12

  11 14

  11 15

  11 18

  11 21

  11 24

  11 25

  11 26

  11 29

  11 32

  11 33

  11 35

  11 36

  11 37

  11 39

  11 40

  11 42

  11 43

  11 45

  11 47

  11 49

  11 50

  12 13

  12 16

  12 17

  12 19

  12 24

  12 25

  12 26

  12 30

  12 31

  12 32

  12 34

  12 36

  12 37

  12 39

  12 41

  12 44

  12 47

  12 48

  12 49

  13 15

  13 16

  13 18

  13 19

  13 20

  13 22

  13 23

  13 24

  13 27

  13 28

  13 29

  13 31

  13 33

  13 35

  13 36

  13 37

  13 44

  13 47

  13 49

  13 50

  14 15

  14 16

  14 17

  14 18

  14 19

  14 20

  14 21

  14 26

  14 28

  14 29

  14 30

  14 31

  14 32

  14 34

  14 35

  14 36

  14 38

  14 39

  14 41

  14 44

  14 46

  14 47

  14 48

  15 18

  15 21

  15 22

  15 23

  15 25

  15 28

  15 29

  15 30

  15 33

  15 34

  15 36

  15 37

  15 38

  15 39

  15 40

  15 43

  15 44

  15 46

  15 50

  16 17

  16 19

  16 20

  16 25

  16 26

  16 29

  16 35

  16 38

  16 39

  16 40

  16 41

  16 42

  16 44

  17 18

  17 19

  17 21

  17 22

  17 23

  17 25

  17 26

  17 28

  17 29

  17 33

  17 37

  17 44

  17 45

  17 48

  18 20

  18 24

  18 27

  18 28

  18 31

  18 32

  18 34

  18 35

  18 36

  18 37

  18 38

  18 45

  18 48

  18 49

  18 50

  19 22

  19 24

  19 28

  19 29

  19 36

  19 37

  19 39

  19 41

  19 43

  19 45

  19 48

  19 49

  20 21

  20 22

  20 24

  20 25

  20 26

  20 27

  20 29

  20 30

  20 31

  20 33

  20 34

  20 35

  20 38

  20 39

  20 41

  20 42

  20 43

  20 44

  20 45

  20 46

  20 48

  20 49

  21 22

  21 23

  21 29

  21 31

  21 35

  21 38

  21 42

  21 46

  21 47

  22 23

  22 26

  22 27

  22 28

  22 29

  22 30

  22 39

  22 40

  22 41

  22 42

  22 44

  22 45

  22 46

  22 47

  22 49

  22 50

  23 28

  23 31

  23 32

  23 33

  23 34

  23 35

  23 36

  23 39

  23 40

  23 41

  23 42

  23 44

  23 45

  23 48

  23 49

  23 50

  24 25

  24 27

  24 29

  24 30

  24 31

  24 33

  24 34

  24 38

  24 42

  24 43

  24 44

  24 49

  24 50

  25 26

  25 27

  25 29

  25 30

  25 33

  25 34

  25 36

  25 38

  25 40

  25 41

  25 42

  25 44

  25 46

  25 47

  25 48

  25 49

  26 28

  26 31

  26 32

  26 33

  26 37

  26 38

  26 39

  26 40

  26 41

  26 42

  26 45

  26 47

  26 48

  26 49

  27 29

  27 30

  27 33

  27 34

  27 35

  27 39

  27 40

  27 46

  27 48

  28 29

  28 37

  28 40

  28 42

  28 44

  28 46

  28 47

  28 50

  29 35

  29 38

  29 39

  29 41

  29 42

  29 48

  30 31

  30 32

  30 35

  30 37

  30 38

  30 40

  30 43

  30 45

  30 46

  30 47

  30 48

  31 33

  31 35

  31 38

  31 40

  31 41

  31 42

  31 44

  31 46

  31 47

  31 50

  32 33

  32 35

  32 39

  32 40

  32 46

  32 49

  32 50

  33 34

  33 36

  33 37

  33 40

  33 42

  33 43

  33 44

  33 45

  33 50

  34 35

  34 36

  34 37

  34 38

  34 40

  34 43

  34 44

  34 49

  34 50

  35 36

  35 38

  35 41

  35 42

  35 43

  35 45

  35 46

  35 47

  35 49

  35 50

  36 37

  36 39

  36 40

  36 41

  36 42

  36 43

  36 48

  36 50

  37 38

  37 41

  37 43

  37 46

  37 47

  37 48

  37 49

  37 50

  38 41

  38 45

  38 46

  38 48

  38 49

  38 50

  39 43

  39 46

  39 47

  39 48

  39 49

  40 43

  40 45

  40 48

  40 50

  41 42

  41 43

  41 44

  41 45

  41 46

  41 48

  41 49

  42 43

  42 44

  42 46

  42 48

  42 49

  43 45

  43 46

  43 48

  43 50

  44 45

  44 48

  45 46

  45 47

  45 48

  46 49

  47 49

  47 50

  48 49

  48 50

  49 50

 ;

 end;