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