lemon-project-template-glpk

annotate deps/glpk/examples/misp.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* MISP, Maximum Independent Set Problem */
alpar@9 2
alpar@9 3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@9 4
alpar@9 5 /* Let G = (V,E) be an undirected graph with vertex set V and edge set
alpar@9 6 E. Vertices u, v in V are non-adjacent if (u,v) not in E. A subset
alpar@9 7 of the vertices S within V is independent if all vertices in S are
alpar@9 8 pairwise non-adjacent. The Maximum Independent Set Problem (MISP) is
alpar@9 9 to find an independent set having the largest cardinality. */
alpar@9 10
alpar@9 11 param n, integer, > 0;
alpar@9 12 /* number of vertices */
alpar@9 13
alpar@9 14 set V := 1..n;
alpar@9 15 /* set of vertices */
alpar@9 16
alpar@9 17 set E within V cross V;
alpar@9 18 /* set of edges */
alpar@9 19
alpar@9 20 var x{i in V}, binary;
alpar@9 21 /* x[i] = 1 means vertex i belongs to independent set */
alpar@9 22
alpar@9 23 s.t. edge{(i,j) in E}: x[i] + x[j] <= 1;
alpar@9 24 /* if there is edge (i,j), vertices i and j cannot belong to the same
alpar@9 25 independent set */
alpar@9 26
alpar@9 27 maximize obj: sum{i in V} x[i];
alpar@9 28 /* the objective is to maximize the cardinality of independent set */
alpar@9 29
alpar@9 30 data;
alpar@9 31
alpar@9 32 /* These data corresponds to the test instance from:
alpar@9 33
alpar@9 34 M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN
alpar@9 35 subroutines for approximate solution of the maximum independent set
alpar@9 36 problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4,
alpar@9 37 December 1998, pp. 386-394. */
alpar@9 38
alpar@9 39 /* The optimal solution is 7 */
alpar@9 40
alpar@9 41 param n := 50;
alpar@9 42
alpar@9 43 set E :=
alpar@9 44 1 2
alpar@9 45 1 3
alpar@9 46 1 5
alpar@9 47 1 7
alpar@9 48 1 8
alpar@9 49 1 12
alpar@9 50 1 15
alpar@9 51 1 16
alpar@9 52 1 19
alpar@9 53 1 20
alpar@9 54 1 21
alpar@9 55 1 22
alpar@9 56 1 28
alpar@9 57 1 30
alpar@9 58 1 34
alpar@9 59 1 35
alpar@9 60 1 37
alpar@9 61 1 41
alpar@9 62 1 42
alpar@9 63 1 47
alpar@9 64 1 50
alpar@9 65 2 3
alpar@9 66 2 5
alpar@9 67 2 6
alpar@9 68 2 7
alpar@9 69 2 8
alpar@9 70 2 9
alpar@9 71 2 10
alpar@9 72 2 13
alpar@9 73 2 17
alpar@9 74 2 19
alpar@9 75 2 20
alpar@9 76 2 21
alpar@9 77 2 23
alpar@9 78 2 25
alpar@9 79 2 26
alpar@9 80 2 29
alpar@9 81 2 31
alpar@9 82 2 35
alpar@9 83 2 36
alpar@9 84 2 44
alpar@9 85 2 45
alpar@9 86 2 46
alpar@9 87 2 50
alpar@9 88 3 5
alpar@9 89 3 6
alpar@9 90 3 8
alpar@9 91 3 9
alpar@9 92 3 10
alpar@9 93 3 11
alpar@9 94 3 14
alpar@9 95 3 16
alpar@9 96 3 23
alpar@9 97 3 24
alpar@9 98 3 26
alpar@9 99 3 27
alpar@9 100 3 28
alpar@9 101 3 29
alpar@9 102 3 30
alpar@9 103 3 31
alpar@9 104 3 34
alpar@9 105 3 35
alpar@9 106 3 36
alpar@9 107 3 39
alpar@9 108 3 41
alpar@9 109 3 42
alpar@9 110 3 43
alpar@9 111 3 44
alpar@9 112 3 50
alpar@9 113 4 6
alpar@9 114 4 7
alpar@9 115 4 9
alpar@9 116 4 10
alpar@9 117 4 11
alpar@9 118 4 13
alpar@9 119 4 14
alpar@9 120 4 15
alpar@9 121 4 17
alpar@9 122 4 21
alpar@9 123 4 22
alpar@9 124 4 23
alpar@9 125 4 24
alpar@9 126 4 25
alpar@9 127 4 27
alpar@9 128 4 28
alpar@9 129 4 30
alpar@9 130 4 31
alpar@9 131 4 33
alpar@9 132 4 34
alpar@9 133 4 35
alpar@9 134 4 36
alpar@9 135 4 37
alpar@9 136 4 38
alpar@9 137 4 40
alpar@9 138 4 41
alpar@9 139 4 42
alpar@9 140 4 46
alpar@9 141 4 49
alpar@9 142 5 6
alpar@9 143 5 11
alpar@9 144 5 14
alpar@9 145 5 21
alpar@9 146 5 24
alpar@9 147 5 25
alpar@9 148 5 28
alpar@9 149 5 35
alpar@9 150 5 38
alpar@9 151 5 39
alpar@9 152 5 41
alpar@9 153 5 44
alpar@9 154 5 49
alpar@9 155 5 50
alpar@9 156 6 8
alpar@9 157 6 9
alpar@9 158 6 10
alpar@9 159 6 13
alpar@9 160 6 14
alpar@9 161 6 16
alpar@9 162 6 17
alpar@9 163 6 19
alpar@9 164 6 22
alpar@9 165 6 23
alpar@9 166 6 26
alpar@9 167 6 27
alpar@9 168 6 30
alpar@9 169 6 34
alpar@9 170 6 35
alpar@9 171 6 38
alpar@9 172 6 39
alpar@9 173 6 40
alpar@9 174 6 41
alpar@9 175 6 44
alpar@9 176 6 45
alpar@9 177 6 47
alpar@9 178 6 50
alpar@9 179 7 8
alpar@9 180 7 9
alpar@9 181 7 10
alpar@9 182 7 11
alpar@9 183 7 13
alpar@9 184 7 15
alpar@9 185 7 16
alpar@9 186 7 18
alpar@9 187 7 20
alpar@9 188 7 22
alpar@9 189 7 23
alpar@9 190 7 24
alpar@9 191 7 25
alpar@9 192 7 33
alpar@9 193 7 35
alpar@9 194 7 36
alpar@9 195 7 38
alpar@9 196 7 43
alpar@9 197 7 45
alpar@9 198 7 46
alpar@9 199 7 47
alpar@9 200 8 10
alpar@9 201 8 11
alpar@9 202 8 13
alpar@9 203 8 16
alpar@9 204 8 17
alpar@9 205 8 18
alpar@9 206 8 19
alpar@9 207 8 20
alpar@9 208 8 21
alpar@9 209 8 22
alpar@9 210 8 23
alpar@9 211 8 24
alpar@9 212 8 25
alpar@9 213 8 26
alpar@9 214 8 33
alpar@9 215 8 35
alpar@9 216 8 36
alpar@9 217 8 39
alpar@9 218 8 42
alpar@9 219 8 44
alpar@9 220 8 48
alpar@9 221 8 49
alpar@9 222 9 12
alpar@9 223 9 14
alpar@9 224 9 17
alpar@9 225 9 19
alpar@9 226 9 20
alpar@9 227 9 23
alpar@9 228 9 28
alpar@9 229 9 30
alpar@9 230 9 31
alpar@9 231 9 32
alpar@9 232 9 33
alpar@9 233 9 34
alpar@9 234 9 38
alpar@9 235 9 39
alpar@9 236 9 42
alpar@9 237 9 44
alpar@9 238 9 45
alpar@9 239 9 46
alpar@9 240 10 11
alpar@9 241 10 13
alpar@9 242 10 15
alpar@9 243 10 16
alpar@9 244 10 17
alpar@9 245 10 20
alpar@9 246 10 21
alpar@9 247 10 22
alpar@9 248 10 23
alpar@9 249 10 25
alpar@9 250 10 26
alpar@9 251 10 27
alpar@9 252 10 28
alpar@9 253 10 30
alpar@9 254 10 31
alpar@9 255 10 32
alpar@9 256 10 37
alpar@9 257 10 38
alpar@9 258 10 41
alpar@9 259 10 43
alpar@9 260 10 44
alpar@9 261 10 45
alpar@9 262 10 50
alpar@9 263 11 12
alpar@9 264 11 14
alpar@9 265 11 15
alpar@9 266 11 18
alpar@9 267 11 21
alpar@9 268 11 24
alpar@9 269 11 25
alpar@9 270 11 26
alpar@9 271 11 29
alpar@9 272 11 32
alpar@9 273 11 33
alpar@9 274 11 35
alpar@9 275 11 36
alpar@9 276 11 37
alpar@9 277 11 39
alpar@9 278 11 40
alpar@9 279 11 42
alpar@9 280 11 43
alpar@9 281 11 45
alpar@9 282 11 47
alpar@9 283 11 49
alpar@9 284 11 50
alpar@9 285 12 13
alpar@9 286 12 16
alpar@9 287 12 17
alpar@9 288 12 19
alpar@9 289 12 24
alpar@9 290 12 25
alpar@9 291 12 26
alpar@9 292 12 30
alpar@9 293 12 31
alpar@9 294 12 32
alpar@9 295 12 34
alpar@9 296 12 36
alpar@9 297 12 37
alpar@9 298 12 39
alpar@9 299 12 41
alpar@9 300 12 44
alpar@9 301 12 47
alpar@9 302 12 48
alpar@9 303 12 49
alpar@9 304 13 15
alpar@9 305 13 16
alpar@9 306 13 18
alpar@9 307 13 19
alpar@9 308 13 20
alpar@9 309 13 22
alpar@9 310 13 23
alpar@9 311 13 24
alpar@9 312 13 27
alpar@9 313 13 28
alpar@9 314 13 29
alpar@9 315 13 31
alpar@9 316 13 33
alpar@9 317 13 35
alpar@9 318 13 36
alpar@9 319 13 37
alpar@9 320 13 44
alpar@9 321 13 47
alpar@9 322 13 49
alpar@9 323 13 50
alpar@9 324 14 15
alpar@9 325 14 16
alpar@9 326 14 17
alpar@9 327 14 18
alpar@9 328 14 19
alpar@9 329 14 20
alpar@9 330 14 21
alpar@9 331 14 26
alpar@9 332 14 28
alpar@9 333 14 29
alpar@9 334 14 30
alpar@9 335 14 31
alpar@9 336 14 32
alpar@9 337 14 34
alpar@9 338 14 35
alpar@9 339 14 36
alpar@9 340 14 38
alpar@9 341 14 39
alpar@9 342 14 41
alpar@9 343 14 44
alpar@9 344 14 46
alpar@9 345 14 47
alpar@9 346 14 48
alpar@9 347 15 18
alpar@9 348 15 21
alpar@9 349 15 22
alpar@9 350 15 23
alpar@9 351 15 25
alpar@9 352 15 28
alpar@9 353 15 29
alpar@9 354 15 30
alpar@9 355 15 33
alpar@9 356 15 34
alpar@9 357 15 36
alpar@9 358 15 37
alpar@9 359 15 38
alpar@9 360 15 39
alpar@9 361 15 40
alpar@9 362 15 43
alpar@9 363 15 44
alpar@9 364 15 46
alpar@9 365 15 50
alpar@9 366 16 17
alpar@9 367 16 19
alpar@9 368 16 20
alpar@9 369 16 25
alpar@9 370 16 26
alpar@9 371 16 29
alpar@9 372 16 35
alpar@9 373 16 38
alpar@9 374 16 39
alpar@9 375 16 40
alpar@9 376 16 41
alpar@9 377 16 42
alpar@9 378 16 44
alpar@9 379 17 18
alpar@9 380 17 19
alpar@9 381 17 21
alpar@9 382 17 22
alpar@9 383 17 23
alpar@9 384 17 25
alpar@9 385 17 26
alpar@9 386 17 28
alpar@9 387 17 29
alpar@9 388 17 33
alpar@9 389 17 37
alpar@9 390 17 44
alpar@9 391 17 45
alpar@9 392 17 48
alpar@9 393 18 20
alpar@9 394 18 24
alpar@9 395 18 27
alpar@9 396 18 28
alpar@9 397 18 31
alpar@9 398 18 32
alpar@9 399 18 34
alpar@9 400 18 35
alpar@9 401 18 36
alpar@9 402 18 37
alpar@9 403 18 38
alpar@9 404 18 45
alpar@9 405 18 48
alpar@9 406 18 49
alpar@9 407 18 50
alpar@9 408 19 22
alpar@9 409 19 24
alpar@9 410 19 28
alpar@9 411 19 29
alpar@9 412 19 36
alpar@9 413 19 37
alpar@9 414 19 39
alpar@9 415 19 41
alpar@9 416 19 43
alpar@9 417 19 45
alpar@9 418 19 48
alpar@9 419 19 49
alpar@9 420 20 21
alpar@9 421 20 22
alpar@9 422 20 24
alpar@9 423 20 25
alpar@9 424 20 26
alpar@9 425 20 27
alpar@9 426 20 29
alpar@9 427 20 30
alpar@9 428 20 31
alpar@9 429 20 33
alpar@9 430 20 34
alpar@9 431 20 35
alpar@9 432 20 38
alpar@9 433 20 39
alpar@9 434 20 41
alpar@9 435 20 42
alpar@9 436 20 43
alpar@9 437 20 44
alpar@9 438 20 45
alpar@9 439 20 46
alpar@9 440 20 48
alpar@9 441 20 49
alpar@9 442 21 22
alpar@9 443 21 23
alpar@9 444 21 29
alpar@9 445 21 31
alpar@9 446 21 35
alpar@9 447 21 38
alpar@9 448 21 42
alpar@9 449 21 46
alpar@9 450 21 47
alpar@9 451 22 23
alpar@9 452 22 26
alpar@9 453 22 27
alpar@9 454 22 28
alpar@9 455 22 29
alpar@9 456 22 30
alpar@9 457 22 39
alpar@9 458 22 40
alpar@9 459 22 41
alpar@9 460 22 42
alpar@9 461 22 44
alpar@9 462 22 45
alpar@9 463 22 46
alpar@9 464 22 47
alpar@9 465 22 49
alpar@9 466 22 50
alpar@9 467 23 28
alpar@9 468 23 31
alpar@9 469 23 32
alpar@9 470 23 33
alpar@9 471 23 34
alpar@9 472 23 35
alpar@9 473 23 36
alpar@9 474 23 39
alpar@9 475 23 40
alpar@9 476 23 41
alpar@9 477 23 42
alpar@9 478 23 44
alpar@9 479 23 45
alpar@9 480 23 48
alpar@9 481 23 49
alpar@9 482 23 50
alpar@9 483 24 25
alpar@9 484 24 27
alpar@9 485 24 29
alpar@9 486 24 30
alpar@9 487 24 31
alpar@9 488 24 33
alpar@9 489 24 34
alpar@9 490 24 38
alpar@9 491 24 42
alpar@9 492 24 43
alpar@9 493 24 44
alpar@9 494 24 49
alpar@9 495 24 50
alpar@9 496 25 26
alpar@9 497 25 27
alpar@9 498 25 29
alpar@9 499 25 30
alpar@9 500 25 33
alpar@9 501 25 34
alpar@9 502 25 36
alpar@9 503 25 38
alpar@9 504 25 40
alpar@9 505 25 41
alpar@9 506 25 42
alpar@9 507 25 44
alpar@9 508 25 46
alpar@9 509 25 47
alpar@9 510 25 48
alpar@9 511 25 49
alpar@9 512 26 28
alpar@9 513 26 31
alpar@9 514 26 32
alpar@9 515 26 33
alpar@9 516 26 37
alpar@9 517 26 38
alpar@9 518 26 39
alpar@9 519 26 40
alpar@9 520 26 41
alpar@9 521 26 42
alpar@9 522 26 45
alpar@9 523 26 47
alpar@9 524 26 48
alpar@9 525 26 49
alpar@9 526 27 29
alpar@9 527 27 30
alpar@9 528 27 33
alpar@9 529 27 34
alpar@9 530 27 35
alpar@9 531 27 39
alpar@9 532 27 40
alpar@9 533 27 46
alpar@9 534 27 48
alpar@9 535 28 29
alpar@9 536 28 37
alpar@9 537 28 40
alpar@9 538 28 42
alpar@9 539 28 44
alpar@9 540 28 46
alpar@9 541 28 47
alpar@9 542 28 50
alpar@9 543 29 35
alpar@9 544 29 38
alpar@9 545 29 39
alpar@9 546 29 41
alpar@9 547 29 42
alpar@9 548 29 48
alpar@9 549 30 31
alpar@9 550 30 32
alpar@9 551 30 35
alpar@9 552 30 37
alpar@9 553 30 38
alpar@9 554 30 40
alpar@9 555 30 43
alpar@9 556 30 45
alpar@9 557 30 46
alpar@9 558 30 47
alpar@9 559 30 48
alpar@9 560 31 33
alpar@9 561 31 35
alpar@9 562 31 38
alpar@9 563 31 40
alpar@9 564 31 41
alpar@9 565 31 42
alpar@9 566 31 44
alpar@9 567 31 46
alpar@9 568 31 47
alpar@9 569 31 50
alpar@9 570 32 33
alpar@9 571 32 35
alpar@9 572 32 39
alpar@9 573 32 40
alpar@9 574 32 46
alpar@9 575 32 49
alpar@9 576 32 50
alpar@9 577 33 34
alpar@9 578 33 36
alpar@9 579 33 37
alpar@9 580 33 40
alpar@9 581 33 42
alpar@9 582 33 43
alpar@9 583 33 44
alpar@9 584 33 45
alpar@9 585 33 50
alpar@9 586 34 35
alpar@9 587 34 36
alpar@9 588 34 37
alpar@9 589 34 38
alpar@9 590 34 40
alpar@9 591 34 43
alpar@9 592 34 44
alpar@9 593 34 49
alpar@9 594 34 50
alpar@9 595 35 36
alpar@9 596 35 38
alpar@9 597 35 41
alpar@9 598 35 42
alpar@9 599 35 43
alpar@9 600 35 45
alpar@9 601 35 46
alpar@9 602 35 47
alpar@9 603 35 49
alpar@9 604 35 50
alpar@9 605 36 37
alpar@9 606 36 39
alpar@9 607 36 40
alpar@9 608 36 41
alpar@9 609 36 42
alpar@9 610 36 43
alpar@9 611 36 48
alpar@9 612 36 50
alpar@9 613 37 38
alpar@9 614 37 41
alpar@9 615 37 43
alpar@9 616 37 46
alpar@9 617 37 47
alpar@9 618 37 48
alpar@9 619 37 49
alpar@9 620 37 50
alpar@9 621 38 41
alpar@9 622 38 45
alpar@9 623 38 46
alpar@9 624 38 48
alpar@9 625 38 49
alpar@9 626 38 50
alpar@9 627 39 43
alpar@9 628 39 46
alpar@9 629 39 47
alpar@9 630 39 48
alpar@9 631 39 49
alpar@9 632 40 43
alpar@9 633 40 45
alpar@9 634 40 48
alpar@9 635 40 50
alpar@9 636 41 42
alpar@9 637 41 43
alpar@9 638 41 44
alpar@9 639 41 45
alpar@9 640 41 46
alpar@9 641 41 48
alpar@9 642 41 49
alpar@9 643 42 43
alpar@9 644 42 44
alpar@9 645 42 46
alpar@9 646 42 48
alpar@9 647 42 49
alpar@9 648 43 45
alpar@9 649 43 46
alpar@9 650 43 48
alpar@9 651 43 50
alpar@9 652 44 45
alpar@9 653 44 48
alpar@9 654 45 46
alpar@9 655 45 47
alpar@9 656 45 48
alpar@9 657 46 49
alpar@9 658 47 49
alpar@9 659 47 50
alpar@9 660 48 49
alpar@9 661 48 50
alpar@9 662 49 50
alpar@9 663 ;
alpar@9 664
alpar@9 665 end;