The Pseudo-Boolean Optimization Website

 Small-a

Home Up Next

 

Best Known Lower Bound to the Maximum
Problem Set #1
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

841

744

424

756

521

694

463

903

1,302

504
30 916 667 1,036 1,240 874 1,107 839 862 1,313 1,483
40 747 811 1,209 1,095 1,384 2,571 1,694 1,749 1,490 2,479
50 1,349 1,290 2,194 2,146 1,900 3,341 2,583 3,708 3,369 4,151
60 1,540 1,836 2,566 3,345 2,828 3,091 2,815 3,411 3,885 4,014
70 2,131 2,482 2,703 3,695 4,176 3,113 4,724 4,833 5,141 6,536
80 3,527 2,128 3,135 4,104 4,059 5,406 4,576 4,946 6,764 6,105
90 3,262 3,755 4,706 4,876 4,704 6,212 7,304 6,672 7,091 7,531
100 2,874 3,821 5,380 7,333 7,437 6,937 8,625 7,078 10,289 8,964
Problem Set #2
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

479

516

695

352

564

683

792

967

973

886
30 762 1,015 1,087 768 1,224 1,348 1,307 1,292 1,621 2,237
40 1,508 1,217 1,079 2,312 1,579 1,825 3,150 2,070 2,807 1,780
50 1,594 1,602 1,168 2,513 2,630 3,672 2,946 3,323 3,205 3,263
60 1,386 2,036 1,647 2,463 2,743 3,598 4,028 3,433 4,320 3,603
70 2,477 2,794 3,414 2,951 5,007 3,488 3,819 4,700 5,295 5,996
80 2,904 2,624 4,272 3,527 5,569 5,512 6,631 5,430 7,101 6,640
90 2,685 3,848 4,637 4,534 5,300 5,571 6,085 8,169 6,981 7,878
100 3,712 3,487 5,126 5,746 6,805 7,083 7,172 7,266 8,726 8,840
Problem Set #3
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

480

690

395

310

710

869

707

1,022

1,000

748
30 539 1,338 963 831 1,519 995 1,479 1,422 1,538 1,647
40 1,371 1,075 1,437 1,547 1,750 2,234 1,998 2,533 2,035 2,224
50 1,649 1,247 1,772 1,992 2,324 2,624 2,994 2,992 3,115 3,735
60 1,530 1,954 2,339 2,330 3,473 3,097 4,295 3,054 4,364 4,053
70 2,106 3,967 2,880 3,310 3,378 5,382 3,693 4,136 6,259 5,142
80 3,282 3,707 4,270 4,292 4,410 6,443 5,222 4,580 7,187 5,690
90 3,323 4,218 4,327 4,782 6,221 6,180 5,508 7,096 7,436 7,227
100 3,311 3,477 5,141 6,203 7,070 5,082 7,681 9,215 9,732 9,608
Problem Set #4
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

654

550

153

433

740

656

521

768

1,113

555
30 749 833 903 1,151 1,294 990 1,149 1,441 702 1,674
40 1,171 1,522 1,342 1,866 1,801 978 2,260 2,484 2,122 2,815
50 1,579 2,074 1,724 1,528 2,305 2,456 3,277 3,085 2,836 3,189
60 1,895 2,173 2,102 2,275 2,565 3,573 3,119 3,366 4,807 3,893
70 2,020 2,202 3,714 3,781 4,204 3,438 4,154 4,954 5,384 4,292
80 2,517 4,077 3,287 5,379 4,316 5,434 5,427 6,297 5,198 6,698
90 2,784 3,560 4,974 4,721 5,120 5,707 5,741 5,926 8,096 7,848
100 3,897 4,774 4,317 5,776 5,478 7,854 7,372 8,305 7,123 9,649
Problem Set #5
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

319

420

735

792

539

665

939

800

869

1,126
30 707 795 1,031 622 852 842 951 1,541 2,291 2,200
40 952 1,571 1,774 1,985 1,544 1,699 1,809 2,317 2,410 2,994
50 1,850 1,991 2,127 2,710 1,754 3,052 2,975 3,771 2,374 2,764
60 2,557 2,038 2,304 3,645 3,479 3,098 3,633 4,481 4,223 5,549
70 2,258 2,295 3,331 2,760 3,643 3,999 3,927 3,835 4,868 6,443
80 3,240 3,564 4,011 3,934 4,841 5,475 5,305 4,807 6,003 5,328
90 2,259 3,560 4,030 5,018 5,497 5,091 6,199 7,213 7,176 7,667
100 3,438 3,412 4,591 6,477 5,755 5,468 6,882 6,104 7,774 8,876
Problem Set #6
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

366

747

603

403

1,063

785

528

861

574

605
30 492 1,147 1,311 1,263 1,238 1,303 1,357 1,779 1,547 1,236
40 897 1,524 1,181 2,017 2,221 1,744 1,956 2,202 1,916 2,077
50 1,357 1,347 1,571 2,506 1,880 2,349 2,696 2,152 2,727 2,866
60 1,692 2,548 2,374 3,032 3,013 2,447 3,177 3,064 4,690 4,139
70 2,038 2,554 2,505 4,176 4,268 4,276 4,166 4,287 4,670 5,717
80 3,018 3,139 4,390 4,646 5,331 5,085 5,273 6,273 6,096 6,824
90 3,194 3,861 3,632 5,970 5,322 5,412 6,082 8,503 5,987 6,646
100 3,678 4,344 6,576 5,433 6,216 7,494 7,166 9,741 6,600 9,182
Problem Set #7
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

296

491

482

629

779

881

722

530

1,018

966
30 475 874 910 1,070 1,221 1,319 1,004 1,355 975 1,870
40 1,336 1,183 1,166 1,794 1,914 2,251 2,173 2,012 2,419 3,377
50 1,157 2,245 2,285 2,620 2,433 1,983 2,344 3,532 3,777 2,494
60 1,818 2,771 3,283 1,904 3,661 2,518 4,663 3,739 4,061 3,258
70 1,944 2,817 3,588 3,037 3,636 4,928 4,079 4,313 4,642 5,030
80 2,130 2,875 4,287 5,022 3,704 4,257 5,429 6,247 5,572 6,570
90 2,737 4,207 4,354 5,639 4,997 5,750 6,916 6,094 6,354 7,871
100 4,593 4,022 6,051 6,731 6,531 6,075 8,226 7,619 9,023 10,004
Problem Set #8
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

615

608

810

449

842

600

937

709

882

877
30 556 811 1,073 1,038 861 1,052 1,554 1,460 774 1,065
40 984 1,360 1,084 1,638 1,393 1,617 1,750 1,980 2,144 1,865
50 1,675 2,093 2,208 2,301 1,967 2,701 2,872 2,809 2,854 2,736
60 1,647 1,539 2,202 1,886 3,379 3,492 3,059 2,772 4,148 5,619
70 2,306 2,698 3,749 3,559 3,908 4,390 5,075 6,174 5,004 6,091
80 2,959 2,830 4,278 3,540 4,681 5,972 5,919 5,897 6,098 6,660
90 2,861 4,356 5,092 5,380 6,404 5,186 6,166 7,865 6,755 8,795
100 3,854 3,911 4,621 6,007 6,407 6,378 7,764 8,477 8,046 10,972
Problem Set #9
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

594

600

518

519

537

533

1,194

1,188

911

934
30 715 1,014 1,070 1,434 1,049 1,562 1,735 1,361 1,051 2,171
40 1,269 1,252 1,488 1,833 1,715 2,132 2,192 2,572 1,739 2,003
50 1,357 1,665 2,092 2,157 2,274 2,204 3,100 2,900 3,031 3,952
60 1,751 2,609 2,138 2,333 3,729 3,292 3,511 3,329 4,098 3,242
70 2,184 2,977 3,056 3,197 3,348 4,823 4,958 4,346 4,872 3,761
80 3,364 3,616 2,711 3,687 4,521 5,006 6,030 5,543 6,253 7,777
90 2,769 3,705 4,198 4,764 6,103 6,287 6,131 7,528 6,886 9,283
100 3,339 4,103 5,856 5,060 6,421 6,318 8,040 8,245 8,141 8,409
Problem Set #10
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

437

697

368

486

667

589

511

645

654

1,047
30 811 651 1,043 1,441 1,159 1,690 1,559 1,606 1,187 1,884
40 805 1,885 1,477 970 1,262 2,162 2,034 1,971 2,244 1,572
50 1,469 1,817 1,970 2,775 2,223 2,325 2,542 2,894 3,485 2,502
60 1,854 2,714 1,915 2,949 2,388 3,082 3,792 2,931 4,791 4,651
70 2,381 2,929 2,892 4,089 3,890 3,948 4,243 5,211 4,955 5,057
80 2,212 2,789 3,622 5,157 4,912 5,967 5,968 6,333 7,176 6,645
90 3,137 4,134 5,110 5,472 5,704 6,121 6,726 6,174 5,958 7,403
100 3,551 4,303 5,125 6,693 4,886 6,615 7,008 7,955 6,733 8,416
 

Copyright © 2003 RUTCOR.
For problems or questions regarding the PBO website contact pbo@rutcor.rutgers.edu.
Last updated: May 20, 2004.