1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/misp.mod	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,665 @@
     1.4 +/* MISP, Maximum Independent Set Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* Let G = (V,E) be an undirected graph with vertex set V and edge set
     1.9 +   E. Vertices u, v in V are non-adjacent if (u,v) not in E. A subset
    1.10 +   of the vertices S within V is independent if all vertices in S are
    1.11 +   pairwise non-adjacent. The Maximum Independent Set Problem (MISP) is
    1.12 +   to find an independent set having the largest cardinality. */
    1.13 +
    1.14 +param n, integer, > 0;
    1.15 +/* number of vertices */
    1.16 +
    1.17 +set V := 1..n;
    1.18 +/* set of vertices */
    1.19 +
    1.20 +set E within V cross V;
    1.21 +/* set of edges */
    1.22 +
    1.23 +var x{i in V}, binary;
    1.24 +/* x[i] = 1 means vertex i belongs to independent set */
    1.25 +
    1.26 +s.t. edge{(i,j) in E}: x[i] + x[j] <= 1;
    1.27 +/* if there is edge (i,j), vertices i and j cannot belong to the same
    1.28 +   independent set */
    1.29 +
    1.30 +maximize obj: sum{i in V} x[i];
    1.31 +/* the objective is to maximize the cardinality of independent set */
    1.32 +
    1.33 +data;
    1.34 +
    1.35 +/* These data corresponds to the test instance from:
    1.36 +
    1.37 +   M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN
    1.38 +   subroutines for approximate solution of the maximum independent set
    1.39 +   problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4,
    1.40 +   December 1998, pp. 386-394. */
    1.41 +
    1.42 +/* The optimal solution is 7 */
    1.43 +
    1.44 +param n := 50;
    1.45 +
    1.46 +set E :=
    1.47 + 1 2
    1.48 + 1 3
    1.49 + 1 5
    1.50 + 1 7
    1.51 + 1 8
    1.52 + 1 12
    1.53 + 1 15
    1.54 + 1 16
    1.55 + 1 19
    1.56 + 1 20
    1.57 + 1 21
    1.58 + 1 22
    1.59 + 1 28
    1.60 + 1 30
    1.61 + 1 34
    1.62 + 1 35
    1.63 + 1 37
    1.64 + 1 41
    1.65 + 1 42
    1.66 + 1 47
    1.67 + 1 50
    1.68 + 2 3
    1.69 + 2 5
    1.70 + 2 6
    1.71 + 2 7
    1.72 + 2 8
    1.73 + 2 9
    1.74 + 2 10
    1.75 + 2 13
    1.76 + 2 17
    1.77 + 2 19
    1.78 + 2 20
    1.79 + 2 21
    1.80 + 2 23
    1.81 + 2 25
    1.82 + 2 26
    1.83 + 2 29
    1.84 + 2 31
    1.85 + 2 35
    1.86 + 2 36
    1.87 + 2 44
    1.88 + 2 45
    1.89 + 2 46
    1.90 + 2 50
    1.91 + 3 5
    1.92 + 3 6
    1.93 + 3 8
    1.94 + 3 9
    1.95 + 3 10
    1.96 + 3 11
    1.97 + 3 14
    1.98 + 3 16
    1.99 + 3 23
   1.100 + 3 24
   1.101 + 3 26
   1.102 + 3 27
   1.103 + 3 28
   1.104 + 3 29
   1.105 + 3 30
   1.106 + 3 31
   1.107 + 3 34
   1.108 + 3 35
   1.109 + 3 36
   1.110 + 3 39
   1.111 + 3 41
   1.112 + 3 42
   1.113 + 3 43
   1.114 + 3 44
   1.115 + 3 50
   1.116 + 4 6
   1.117 + 4 7
   1.118 + 4 9
   1.119 + 4 10
   1.120 + 4 11
   1.121 + 4 13
   1.122 + 4 14
   1.123 + 4 15
   1.124 + 4 17
   1.125 + 4 21
   1.126 + 4 22
   1.127 + 4 23
   1.128 + 4 24
   1.129 + 4 25
   1.130 + 4 27
   1.131 + 4 28
   1.132 + 4 30
   1.133 + 4 31
   1.134 + 4 33
   1.135 + 4 34
   1.136 + 4 35
   1.137 + 4 36
   1.138 + 4 37
   1.139 + 4 38
   1.140 + 4 40
   1.141 + 4 41
   1.142 + 4 42
   1.143 + 4 46
   1.144 + 4 49
   1.145 + 5 6
   1.146 + 5 11
   1.147 + 5 14
   1.148 + 5 21
   1.149 + 5 24
   1.150 + 5 25
   1.151 + 5 28
   1.152 + 5 35
   1.153 + 5 38
   1.154 + 5 39
   1.155 + 5 41
   1.156 + 5 44
   1.157 + 5 49
   1.158 + 5 50
   1.159 + 6 8
   1.160 + 6 9
   1.161 + 6 10
   1.162 + 6 13
   1.163 + 6 14
   1.164 + 6 16
   1.165 + 6 17
   1.166 + 6 19
   1.167 + 6 22
   1.168 + 6 23
   1.169 + 6 26
   1.170 + 6 27
   1.171 + 6 30
   1.172 + 6 34
   1.173 + 6 35
   1.174 + 6 38
   1.175 + 6 39
   1.176 + 6 40
   1.177 + 6 41
   1.178 + 6 44
   1.179 + 6 45
   1.180 + 6 47
   1.181 + 6 50
   1.182 + 7 8
   1.183 + 7 9
   1.184 + 7 10
   1.185 + 7 11
   1.186 + 7 13
   1.187 + 7 15
   1.188 + 7 16
   1.189 + 7 18
   1.190 + 7 20
   1.191 + 7 22
   1.192 + 7 23
   1.193 + 7 24
   1.194 + 7 25
   1.195 + 7 33
   1.196 + 7 35
   1.197 + 7 36
   1.198 + 7 38
   1.199 + 7 43
   1.200 + 7 45
   1.201 + 7 46
   1.202 + 7 47
   1.203 + 8 10
   1.204 + 8 11
   1.205 + 8 13
   1.206 + 8 16
   1.207 + 8 17
   1.208 + 8 18
   1.209 + 8 19
   1.210 + 8 20
   1.211 + 8 21
   1.212 + 8 22
   1.213 + 8 23
   1.214 + 8 24
   1.215 + 8 25
   1.216 + 8 26
   1.217 + 8 33
   1.218 + 8 35
   1.219 + 8 36
   1.220 + 8 39
   1.221 + 8 42
   1.222 + 8 44
   1.223 + 8 48
   1.224 + 8 49
   1.225 + 9 12
   1.226 + 9 14
   1.227 + 9 17
   1.228 + 9 19
   1.229 + 9 20
   1.230 + 9 23
   1.231 + 9 28
   1.232 + 9 30
   1.233 + 9 31
   1.234 + 9 32
   1.235 + 9 33
   1.236 + 9 34
   1.237 + 9 38
   1.238 + 9 39
   1.239 + 9 42
   1.240 + 9 44
   1.241 + 9 45
   1.242 + 9 46
   1.243 + 10 11
   1.244 + 10 13
   1.245 + 10 15
   1.246 + 10 16
   1.247 + 10 17
   1.248 + 10 20
   1.249 + 10 21
   1.250 + 10 22
   1.251 + 10 23
   1.252 + 10 25
   1.253 + 10 26
   1.254 + 10 27
   1.255 + 10 28
   1.256 + 10 30
   1.257 + 10 31
   1.258 + 10 32
   1.259 + 10 37
   1.260 + 10 38
   1.261 + 10 41
   1.262 + 10 43
   1.263 + 10 44
   1.264 + 10 45
   1.265 + 10 50
   1.266 + 11 12
   1.267 + 11 14
   1.268 + 11 15
   1.269 + 11 18
   1.270 + 11 21
   1.271 + 11 24
   1.272 + 11 25
   1.273 + 11 26
   1.274 + 11 29
   1.275 + 11 32
   1.276 + 11 33
   1.277 + 11 35
   1.278 + 11 36
   1.279 + 11 37
   1.280 + 11 39
   1.281 + 11 40
   1.282 + 11 42
   1.283 + 11 43
   1.284 + 11 45
   1.285 + 11 47
   1.286 + 11 49
   1.287 + 11 50
   1.288 + 12 13
   1.289 + 12 16
   1.290 + 12 17
   1.291 + 12 19
   1.292 + 12 24
   1.293 + 12 25
   1.294 + 12 26
   1.295 + 12 30
   1.296 + 12 31
   1.297 + 12 32
   1.298 + 12 34
   1.299 + 12 36
   1.300 + 12 37
   1.301 + 12 39
   1.302 + 12 41
   1.303 + 12 44
   1.304 + 12 47
   1.305 + 12 48
   1.306 + 12 49
   1.307 + 13 15
   1.308 + 13 16
   1.309 + 13 18
   1.310 + 13 19
   1.311 + 13 20
   1.312 + 13 22
   1.313 + 13 23
   1.314 + 13 24
   1.315 + 13 27
   1.316 + 13 28
   1.317 + 13 29
   1.318 + 13 31
   1.319 + 13 33
   1.320 + 13 35
   1.321 + 13 36
   1.322 + 13 37
   1.323 + 13 44
   1.324 + 13 47
   1.325 + 13 49
   1.326 + 13 50
   1.327 + 14 15
   1.328 + 14 16
   1.329 + 14 17
   1.330 + 14 18
   1.331 + 14 19
   1.332 + 14 20
   1.333 + 14 21
   1.334 + 14 26
   1.335 + 14 28
   1.336 + 14 29
   1.337 + 14 30
   1.338 + 14 31
   1.339 + 14 32
   1.340 + 14 34
   1.341 + 14 35
   1.342 + 14 36
   1.343 + 14 38
   1.344 + 14 39
   1.345 + 14 41
   1.346 + 14 44
   1.347 + 14 46
   1.348 + 14 47
   1.349 + 14 48
   1.350 + 15 18
   1.351 + 15 21
   1.352 + 15 22
   1.353 + 15 23
   1.354 + 15 25
   1.355 + 15 28
   1.356 + 15 29
   1.357 + 15 30
   1.358 + 15 33
   1.359 + 15 34
   1.360 + 15 36
   1.361 + 15 37
   1.362 + 15 38
   1.363 + 15 39
   1.364 + 15 40
   1.365 + 15 43
   1.366 + 15 44
   1.367 + 15 46
   1.368 + 15 50
   1.369 + 16 17
   1.370 + 16 19
   1.371 + 16 20
   1.372 + 16 25
   1.373 + 16 26
   1.374 + 16 29
   1.375 + 16 35
   1.376 + 16 38
   1.377 + 16 39
   1.378 + 16 40
   1.379 + 16 41
   1.380 + 16 42
   1.381 + 16 44
   1.382 + 17 18
   1.383 + 17 19
   1.384 + 17 21
   1.385 + 17 22
   1.386 + 17 23
   1.387 + 17 25
   1.388 + 17 26
   1.389 + 17 28
   1.390 + 17 29
   1.391 + 17 33
   1.392 + 17 37
   1.393 + 17 44
   1.394 + 17 45
   1.395 + 17 48
   1.396 + 18 20
   1.397 + 18 24
   1.398 + 18 27
   1.399 + 18 28
   1.400 + 18 31
   1.401 + 18 32
   1.402 + 18 34
   1.403 + 18 35
   1.404 + 18 36
   1.405 + 18 37
   1.406 + 18 38
   1.407 + 18 45
   1.408 + 18 48
   1.409 + 18 49
   1.410 + 18 50
   1.411 + 19 22
   1.412 + 19 24
   1.413 + 19 28
   1.414 + 19 29
   1.415 + 19 36
   1.416 + 19 37
   1.417 + 19 39
   1.418 + 19 41
   1.419 + 19 43
   1.420 + 19 45
   1.421 + 19 48
   1.422 + 19 49
   1.423 + 20 21
   1.424 + 20 22
   1.425 + 20 24
   1.426 + 20 25
   1.427 + 20 26
   1.428 + 20 27
   1.429 + 20 29
   1.430 + 20 30
   1.431 + 20 31
   1.432 + 20 33
   1.433 + 20 34
   1.434 + 20 35
   1.435 + 20 38
   1.436 + 20 39
   1.437 + 20 41
   1.438 + 20 42
   1.439 + 20 43
   1.440 + 20 44
   1.441 + 20 45
   1.442 + 20 46
   1.443 + 20 48
   1.444 + 20 49
   1.445 + 21 22
   1.446 + 21 23
   1.447 + 21 29
   1.448 + 21 31
   1.449 + 21 35
   1.450 + 21 38
   1.451 + 21 42
   1.452 + 21 46
   1.453 + 21 47
   1.454 + 22 23
   1.455 + 22 26
   1.456 + 22 27
   1.457 + 22 28
   1.458 + 22 29
   1.459 + 22 30
   1.460 + 22 39
   1.461 + 22 40
   1.462 + 22 41
   1.463 + 22 42
   1.464 + 22 44
   1.465 + 22 45
   1.466 + 22 46
   1.467 + 22 47
   1.468 + 22 49
   1.469 + 22 50
   1.470 + 23 28
   1.471 + 23 31
   1.472 + 23 32
   1.473 + 23 33
   1.474 + 23 34
   1.475 + 23 35
   1.476 + 23 36
   1.477 + 23 39
   1.478 + 23 40
   1.479 + 23 41
   1.480 + 23 42
   1.481 + 23 44
   1.482 + 23 45
   1.483 + 23 48
   1.484 + 23 49
   1.485 + 23 50
   1.486 + 24 25
   1.487 + 24 27
   1.488 + 24 29
   1.489 + 24 30
   1.490 + 24 31
   1.491 + 24 33
   1.492 + 24 34
   1.493 + 24 38
   1.494 + 24 42
   1.495 + 24 43
   1.496 + 24 44
   1.497 + 24 49
   1.498 + 24 50
   1.499 + 25 26
   1.500 + 25 27
   1.501 + 25 29
   1.502 + 25 30
   1.503 + 25 33
   1.504 + 25 34
   1.505 + 25 36
   1.506 + 25 38
   1.507 + 25 40
   1.508 + 25 41
   1.509 + 25 42
   1.510 + 25 44
   1.511 + 25 46
   1.512 + 25 47
   1.513 + 25 48
   1.514 + 25 49
   1.515 + 26 28
   1.516 + 26 31
   1.517 + 26 32
   1.518 + 26 33
   1.519 + 26 37
   1.520 + 26 38
   1.521 + 26 39
   1.522 + 26 40
   1.523 + 26 41
   1.524 + 26 42
   1.525 + 26 45
   1.526 + 26 47
   1.527 + 26 48
   1.528 + 26 49
   1.529 + 27 29
   1.530 + 27 30
   1.531 + 27 33
   1.532 + 27 34
   1.533 + 27 35
   1.534 + 27 39
   1.535 + 27 40
   1.536 + 27 46
   1.537 + 27 48
   1.538 + 28 29
   1.539 + 28 37
   1.540 + 28 40
   1.541 + 28 42
   1.542 + 28 44
   1.543 + 28 46
   1.544 + 28 47
   1.545 + 28 50
   1.546 + 29 35
   1.547 + 29 38
   1.548 + 29 39
   1.549 + 29 41
   1.550 + 29 42
   1.551 + 29 48
   1.552 + 30 31
   1.553 + 30 32
   1.554 + 30 35
   1.555 + 30 37
   1.556 + 30 38
   1.557 + 30 40
   1.558 + 30 43
   1.559 + 30 45
   1.560 + 30 46
   1.561 + 30 47
   1.562 + 30 48
   1.563 + 31 33
   1.564 + 31 35
   1.565 + 31 38
   1.566 + 31 40
   1.567 + 31 41
   1.568 + 31 42
   1.569 + 31 44
   1.570 + 31 46
   1.571 + 31 47
   1.572 + 31 50
   1.573 + 32 33
   1.574 + 32 35
   1.575 + 32 39
   1.576 + 32 40
   1.577 + 32 46
   1.578 + 32 49
   1.579 + 32 50
   1.580 + 33 34
   1.581 + 33 36
   1.582 + 33 37
   1.583 + 33 40
   1.584 + 33 42
   1.585 + 33 43
   1.586 + 33 44
   1.587 + 33 45
   1.588 + 33 50
   1.589 + 34 35
   1.590 + 34 36
   1.591 + 34 37
   1.592 + 34 38
   1.593 + 34 40
   1.594 + 34 43
   1.595 + 34 44
   1.596 + 34 49
   1.597 + 34 50
   1.598 + 35 36
   1.599 + 35 38
   1.600 + 35 41
   1.601 + 35 42
   1.602 + 35 43
   1.603 + 35 45
   1.604 + 35 46
   1.605 + 35 47
   1.606 + 35 49
   1.607 + 35 50
   1.608 + 36 37
   1.609 + 36 39
   1.610 + 36 40
   1.611 + 36 41
   1.612 + 36 42
   1.613 + 36 43
   1.614 + 36 48
   1.615 + 36 50
   1.616 + 37 38
   1.617 + 37 41
   1.618 + 37 43
   1.619 + 37 46
   1.620 + 37 47
   1.621 + 37 48
   1.622 + 37 49
   1.623 + 37 50
   1.624 + 38 41
   1.625 + 38 45
   1.626 + 38 46
   1.627 + 38 48
   1.628 + 38 49
   1.629 + 38 50
   1.630 + 39 43
   1.631 + 39 46
   1.632 + 39 47
   1.633 + 39 48
   1.634 + 39 49
   1.635 + 40 43
   1.636 + 40 45
   1.637 + 40 48
   1.638 + 40 50
   1.639 + 41 42
   1.640 + 41 43
   1.641 + 41 44
   1.642 + 41 45
   1.643 + 41 46
   1.644 + 41 48
   1.645 + 41 49
   1.646 + 42 43
   1.647 + 42 44
   1.648 + 42 46
   1.649 + 42 48
   1.650 + 42 49
   1.651 + 43 45
   1.652 + 43 46
   1.653 + 43 48
   1.654 + 43 50
   1.655 + 44 45
   1.656 + 44 48
   1.657 + 45 46
   1.658 + 45 47
   1.659 + 45 48
   1.660 + 46 49
   1.661 + 47 49
   1.662 + 47 50
   1.663 + 48 49
   1.664 + 48 50
   1.665 + 49 50
   1.666 +;
   1.667 +
   1.668 +end;