Lower Bounds for RCPSP/max instances with n=100, Testset D, based on constraint propagation and linear programming (Brucker, Knust [2003]) Inst. LB UBbest LBnew ------------------------- 1 536 536 536 2 479 511 479 3 337 384 339 * 4 516 543 516 5 446 446 446 6 449 540 449 7 363 392 367 * 8 618 618 618 9 451 590 451 10 387 437 392 * 11 394 400 394 12 434 434 434 13 372 373 372 14 453 453 453 15 463 463 463 16 404 404 404 17 422 422 422 18 428 428 428 19 456 456 456 20 364 364 364 21 414 414 414 22 450 450 450 23 497 497 497 24 405 405 405 25 347 347 347 26 451 451 451 27 357 357 357 28 374 374 374 29 388 388 388 30 428 428 428 31 465 650 465 32 507 679 508 * 33 390 582 397 * 34 402 622 402 35 337 494 341 * 36 600 802 600 37 527 588 527 38 476 551 478 * 39 486 579 486 40 487 535 489 * 41 274 274 274 42 484 484 484 43 666 666 666 44 479 479 479 45 358 358 358 46 365 365 365 47 490 490 490 48 495 495 495 49 398 398 398 50 397 417 404 * 51 351 351 351 52 357 357 357 53 337 337 337 54 531 531 531 55 419 419 419 56 341 341 341 57 314 314 314 58 305 305 305 59 309 309 309 60 426 426 426 61 475 670 475 62 663 804 663 63 389 600 422 * 64 559 711 559 65 410 541 440 * 66 404 527 405 * 67 478 570 478 68 450 633 469 * 69 501 580 501 70 451 740 511 * 71 332 389 332 72 380 380 380 73 391 391 391 74 358 358 358 75 273 282 273 76 491 491 491 77 407 407 407 78 424 498 424 79 377 377 377 80 398 398 398 81 438 438 438 82 543 543 543 83 408 408 408 84 406 406 406 85 392 392 392 86 520 520 520 87 317 317 317 88 390 421 390 89 484 484 484 90 392 392 392 91 492 615 493 * 92 392 429 399 * 93 334 425 340 * 94 451 552 452 * 95 454 454 454 96 431 460 434 * 97 428 538 428 98 519 656 519 99 322 389 322 100 446 479 446 101 488 488 488 102 422 422 422 103 499 499 499 104 392 392 392 105 447 447 447 106 410 410 410 107 346 346 346 108 338 338 338 109 404 404 404 110 479 479 479 111 392 392 392 112 415 415 415 113 449 449 449 114 370 370 370 115 341 341 341 116 463 463 463 117 366 366 366 118 501 501 501 119 444 444 444 120 430 430 430 121 383 383 383 122 641 682 641 123 445 585 445 124 529 750 529 125 487 577 487 126 371 513 373 * 127 428 454 428 128 504 754 505 * 129 518 563 518 130 521 724 521 131 393 393 393 132 445 445 445 133 424 424 424 134 427 598 434 * 135 310 310 310 136 311 311 311 137 412 412 412 138 384 384 384 139 382 382 382 140 355 355 355 141 369 369 369 142 450 450 450 143 468 468 468 144 435 435 435 145 486 486 486 146 397 397 397 147 380 380 380 148 353 353 353 149 308 308 308 150 300 300 300 151 485 696 485 152 448 534 451 * 153 413 596 434 * 154 513 513 513 155 379 578 396 * 156 422 613 428 * 157 523 723 523 158 511 812 542 * 159 529 543 531 * 160 457 675 457 161 335 335 335 162 356 356 356 163 428 428 428 164 499 499 499 165 394 457 400 * 166 358 456 365 * 167 418 454 418 168 418 418 418 169 366 405 366 170 446 446 446 171 493 493 493 172 399 399 399 173 369 369 369 174 320 320 320 175 424 424 424 176 440 440 440 177 406 406 406 178 444 444 444 179 338 338 338 180 369 369 369 181 527 527 527 182 450 464 450 183 563 628 563 184 653 659 658 * 185 510 510 510 186 602 602 602 187 594 627 594 188 585 587 587 * 189 556 637 575 * 190 486 541 493 * 191 500 500 500 192 588 588 588 193 545 545 545 194 442 442 442 195 636 636 636 196 500 500 500 197 421 421 421 198 502 502 502 199 380 380 380 200 438 438 438 201 422 422 422 202 525 525 525 203 382 382 382 204 344 344 344 205 590 590 590 206 507 507 507 207 461 461 461 208 532 532 532 209 434 434 434 210 522 522 522 211 593 703 598 * 212 466 518 466 213 427 508 429 * 214 450 512 450 215 615 663 623 * 216 594 594 594 217 623 678 625 * 218 598 613 598 219 403 551 406 * 220 633 693 661 * 221 466 466 466 222 551 551 551 223 480 480 480 224 624 624 624 225 614 615 614 226 663 663 663 227 486 486 486 228 491 491 491 229 444 444 444 230 433 433 433 231 332 332 332 232 633 633 633 233 337 337 337 234 514 514 514 235 461 461 461 236 727 727 727 237 450 450 450 238 510 510 510 239 584 584 584 240 485 485 485 241 649 873 737 * 242 570 859 673 * 243 570 819 574 * 244 534 0 615 !!!! 245 441 548 454 * 246 378 588 384 * 247 379 545 395 * 248 656 664 656 249 627 730 637 * 250 629 629 629 251 483 484 483 252 538 600 546 * 253 578 578 578 254 390 405 394 * 255 484 484 484 256 499 499 499 257 616 616 616 258 529 543 533 * 259 549 549 549 260 490 490 490 261 618 618 618 262 421 421 421 263 447 447 447 264 466 466 466 265 450 450 450 266 681 681 681 267 693 693 693 268 510 565 510 269 416 416 416 270 512 512 512 271 622 678 622 272 575 622 582 * 273 715 715 715 274 465 517 469 * 275 603 624 603 276 523 547 523 277 558 602 558 278 562 562 562 279 621 621 621 280 652 665 652 281 462 462 462 282 506 506 506 283 586 586 586 284 548 548 548 285 652 652 652 286 549 549 549 287 633 633 633 288 411 411 411 289 430 430 430 290 414 414 414 291 417 417 417 292 374 374 374 293 475 475 475 294 463 463 463 295 484 484 484 296 521 521 521 297 449 449 449 298 502 502 502 299 532 532 532 300 407 407 407 301 590 0 0 302 657 666 657 303 443 592 446 * 304 423 489 429 * 305 603 762 603 306 554 614 554 307 524 524 524 308 577 583 577 309 742 772 742 310 512 523 512 311 484 484 484 312 486 486 486 313 528 528 528 314 470 470 470 315 507 507 507 316 589 589 589 317 420 420 420 318 492 492 492 319 431 439 439 * 320 564 564 564 321 554 554 554 322 508 508 508 323 586 586 586 324 627 627 627 325 445 445 445 326 619 619 619 327 449 449 449 328 423 423 423 329 473 473 473 330 472 472 472 331 555 567 555 332 620 761 641 * 333 561 652 564 * 334 581 648 581 335 510 0 0 336 623 663 627 * 337 479 618 484 * 338 631 677 631 339 689 866 689 340 582 850 609 * 341 509 509 509 342 509 515 515 * 343 495 522 508 * 344 502 502 502 345 659 659 659 346 425 461 425 347 491 491 491 348 433 463 439 * 349 633 633 633 350 508 508 508 351 507 507 507 352 453 453 453 353 599 599 599 354 516 516 516 355 428 442 428 356 420 420 420 357 546 546 546 358 586 588 586 359 481 481 481 360 495 495 495 361 533 582 535 * 362 632 632 632 363 341 473 359 * 364 696 696 696 365 766 766 766 366 497 603 516 * 367 472 477 472 368 598 599 599 * 369 485 512 498 * 370 659 662 660 * 371 634 634 634 372 431 436 436 * 373 583 583 583 374 651 651 651 375 526 530 530 * 376 610 610 610 377 376 376 376 378 609 609 609 379 392 392 392 380 610 610 610 381 602 602 602 382 621 621 621 383 445 445 445 384 701 701 701 385 393 393 393 386 545 545 545 387 590 590 590 388 485 485 485 389 449 449 449 390 572 572 572 391 596 706 600 * 392 608 634 617 * 393 615 684 636 * 394 429 549 448 * 395 449 0 0 396 613 711 653 * 397 594 688 605 * 398 359 493 360 * 399 492 604 501 * 400 713 723 714 * 401 686 686 686 402 540 540 540 403 512 512 512 404 456 456 456 405 526 526 526 406 495 495 495 407 407 407 407 408 491 491 491 409 544 544 544 410 527 527 527 411 662 662 662 412 562 562 562 413 638 638 638 414 395 398 398 * 415 631 631 631 416 605 605 605 417 659 659 659 418 629 629 629 419 542 551 550 * 420 494 494 494 421 475 631 509 * 422 726 731 728 * 423 635 846 702 * 424 596 796 689 * 425 627 856 733 * 426 700 707 706 * 427 583 640 583 428 550 598 570 * 429 517 701 568 * 430 729 844 729 431 387 429 387 432 319 319 319 433 416 429 416 434 553 553 553 435 504 504 504 436 474 477 474 437 565 578 569 * 438 520 520 520 439 458 458 458 440 597 619 617 * 441 711 711 711 442 579 579 579 443 728 728 728 444 497 497 497 445 461 461 461 446 522 522 522 447 417 417 416 448 799 799 799 449 732 732 732 450 372 372 372 451 676 676 676 452 571 622 578 * 453 582 0 0 454 631 631 631 455 530 550 539 * 456 665 719 672 * 457 533 553 537 * 458 532 538 533 * 459 731 744 744 * 460 709 709 709 461 752 752 752 462 369 373 369 463 603 0 0 464 370 370 370 465 436 436 436 466 491 491 491 467 633 633 633 468 633 633 633 469 509 509 509 470 467 483 469 * 471 558 558 558 472 684 684 684 473 725 725 725 474 624 624 624 475 451 453 453 * 476 639 639 639 477 413 413 413 478 444 444 444 479 463 470 470 * 480 441 441 441 481 524 546 529 * 482 629 662 633 * 483 576 591 576 484 777 801 787 * 485 575 653 594 * 486 679 703 679 487 630 673 635 * 488 697 697 697 489 551 699 590 * 490 749 786 766 * 491 770 770 770 492 442 442 442 493 590 590 590 494 489 489 489 495 846 846 846 496 451 452 452 * 497 351 351 351 498 503 508 503 499 499 499 499 500 562 562 562 501 663 669 663 502 456 456 456 503 735 735 735 504 433 438 433 505 627 627 627 506 578 578 578 507 526 527 526 508 650 650 650 509 726 726 726 510 681 681 681 511 712 719 716 * 512 503 637 518 * 513 509 665 523 * 514 787 809 794 * 515 547 0 0 516 784 801 794 * 517 587 603 589 * 518 661 721 674 * 519 502 622 522 * 520 661 716 665 * 521 540 0 0 522 427 431 430 * 523 392 413 393 * 524 475 533 478 * 525 590 590 590 526 633 633 633 527 610 610 610 528 448 450 448 529 417 421 417 530 484 486 484 531 579 579 579 532 501 501 501 533 498 498 498 534 495 495 495 535 615 615 615 536 701 701 701 537 359 359 359 538 425 425 425 539 619 619 619 540 502 514 502 --------------------------- feasible instances: 532 verified: 340 average error: 4.2 maximal error: 35.4 average time: 17.05 maximal time: 93.40 IScount: 482 LPcount: 51 osbetter: 121 --------------------------- old values: verified: 330 average error: 4.6 maximal error: 39.1