1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/examples/misp.mod Mon Dec 06 13:09:21 2010 +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;