simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 665 insertions, 0 deletions

diff --git a/glpk-5.0/examples/misp.mod b/glpk-5.0/examples/misp.mod
new file mode 100644
index 0000000..b2b1f6b
--- /dev/null
+++ b/glpk-5.0/examples/misp.mod
@@ -0,0 +1,665 @@
+/* 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;