/* 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;