The Pseudo-Boolean Optimization Website

 Small-c

Back 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

616

1,142

2,910

2,085

2,899

1,611

3,488

1,507

2,726

2,486
30 1,852 3,038 2,626 3,433 3,458 5,998 4,957 3,811 7,132 3,607
40 1,509 3,738 4,785 5,357 7,065 7,709 7,929 7,054 7,831 9,460
50 4,459 5,005 5,492 7,303 7,899 8,836 8,984 8,478 10,144 12,307
60 4,084 8,675 6,929 8,411 14,101 10,072 14,705 15,973 16,327 18,271
70 5,563 9,421 7,466 12,295 16,128 15,852 12,772 23,674 20,406 17,146
80 7,965 12,515 15,647 15,605 17,442 19,624 24,036 25,069 25,118 28,483
90 10,521 10,987 16,269 16,562 22,350 21,260 22,852 25,937 23,304 26,610
100 11,696 18,259 16,108 22,985 25,895 22,135 31,714 42,744 31,258 39,937
Problem Set #2
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

721

922

1,428

1,880

1,279

2,565

2,658

2,744

4,124

1,885
30 1,818 2,273 2,013 2,703 3,460 4,639 5,242 4,229 3,974 4,415
40 2,700 1,953 5,166 5,361 4,422 6,809 7,658 8,197 8,721 6,026
50 3,534 4,844 6,766 7,045 8,884 9,273 9,518 9,664 10,981 10,463
60 4,109 6,111 9,252 9,340 14,525 10,237 12,522 11,455 14,244 14,978
70 6,208 11,529 13,948 11,928 14,377 15,228 17,043 21,035 16,910 15,443
80 6,925 11,818 15,349 16,620 18,050 15,702 21,106 21,478 20,983 23,823
90 9,610 17,171 19,101 17,737 20,211 21,709 32,596 22,652 23,177 23,869
100 11,520 15,156 22,030 20,587 21,616 28,912 29,825 31,472 35,701 36,828
Problem Set #3
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,279

663

1,308

1,715

2,246

3,219

1,498

2,075

2,964

1,700
30 1,927 1,879 3,183 3,496 2,867 6,443 5,140 4,393 5,078 7,362
40 3,932 4,925 3,835 4,142 5,274 5,942 7,581 7,788 9,288 7,477
50 3,821 5,159 7,230 7,969 9,858 11,422 9,069 9,457 10,264 9,192
60 5,225 7,104 9,781 14,116 9,222 10,251 14,010 16,979 12,627 16,199
70 5,270 8,837 12,771 13,466 11,630 18,464 17,531 15,340 20,856 18,553
80 7,395 11,822 9,536 18,164 12,449 17,096 24,616 20,063 23,849 23,263
90 8,736 12,038 13,873 19,444 20,636 26,432 20,882 27,074 25,529 32,481
100 9,661 13,520 24,565 24,144 22,542 23,706 33,178 30,799 32,663 32,837
Problem Set #4
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,292

1,342

2,272

1,623

1,466

2,122

2,719

2,322

2,179

3,656
30 2,250 2,666 2,323 3,432 4,253 3,747 4,988 4,514 4,777 5,167
40 2,119 4,335 6,342 6,557 6,546 7,296 7,517 12,274 5,628 8,369
50 3,665 5,178 5,269 7,506 6,697 8,727 7,907 10,378 13,635 15,646
60 4,682 5,146 10,105 9,587 13,681 10,823 12,617 14,624 16,867 17,183
70 5,720 8,916 13,554 13,978 13,560 16,823 17,564 17,744 20,269 24,399
80 6,842 9,100 11,835 15,372 18,191 17,872 23,787 21,784 24,750 23,181
90 10,654 13,316 15,640 21,907 19,780 22,051 20,168 24,412 22,974 27,710
100 10,490 13,998 15,248 27,252 22,974 22,916 26,307 32,459 32,659 35,855
Problem Set #5
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,109

1,313

1,646

3,818

1,691

3,753

2,782

2,554

2,513

2,806
30 2,198 2,130 4,241 3,751 2,746 3,122 5,197 5,473 5,434 4,812
40 3,315 4,427 3,921 7,000 6,860 7,145 5,628 8,354 8,341 9,947
50 2,906 5,246 6,994 8,086 9,778 10,567 10,693 10,013 8,573 11,073
60 5,223 6,874 7,303 7,864 10,614 14,988 13,023 13,663 13,253 17,135
70 6,566 8,301 10,735 12,816 10,509 15,163 19,763 25,248 19,666 20,124
80 7,289 11,529 14,522 15,363 18,133 17,663 20,222 20,255 19,234 28,933
90 8,498 11,498 15,196 22,501 18,989 19,883 20,592 20,296 27,051 28,926
100 11,141 15,786 15,969 22,347 30,503 30,198 26,840 33,871 28,856 37,538
Problem Set #6
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,049

1,657

1,668

2,162

3,078

3,042

2,927

2,563

2,522

3,996
30 1,501 1,818 2,786 3,121 3,401 3,388 5,073 4,108 6,694 5,766
40 2,585 4,957 4,439 6,408 5,624 5,417 9,480 8,087 6,295 6,838
50 4,122 6,273 6,768 5,458 8,396 11,689 10,780 12,228 11,617 10,911
60 4,617 6,546 8,487 8,630 11,980 9,429 13,041 16,851 12,914 15,593
70 5,748 7,914 10,620 13,489 12,746 15,412 16,825 17,616 20,321 24,712
80 6,670 13,633 11,675 14,413 16,989 17,090 19,352 17,858 26,191 24,290
90 10,738 12,085 16,618 16,389 23,649 21,501 26,161 22,504 25,539 33,620
100 10,820 16,225 19,503 24,399 26,086 24,206 27,139 28,699 26,935 35,638
Problem Set #7
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

936

1,397

1,310

2,878

2,136

1,849

1,986

3,150

3,618

1,980
30 2,050 1,660 2,447 4,093 3,327 3,948 6,031 5,832 3,911 6,792
40 1,989 4,550 3,725 6,577 4,977 8,390 8,116 8,214 8,332 8,958
50 4,091 4,520 7,594 7,295 8,675 11,442 9,262 8,394 7,747 13,261
60 5,381 8,872 8,739 12,051 9,122 11,896 11,482 14,469 14,904 14,010
70 6,928 8,081 10,776 12,745 13,265 16,364 19,867 19,744 21,145 24,166
80 8,919 8,925 13,315 16,945 19,444 19,943 20,213 23,756 20,595 25,833
90 8,309 14,391 18,874 17,921 21,813 21,119 25,183 20,621 25,664 28,724
100 12,940 15,947 18,141 22,647 22,549 27,286 26,294 27,814 29,353 32,315
Problem Set #8
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

849

817

1,618

1,802

1,779

1,734

2,089

3,576

2,179

2,876
30 2,413 2,725 3,279 2,382 3,642 3,443 3,063 4,063 8,239 5,641
40 2,704 4,340 4,043 5,488 6,691 7,187 5,449 5,850 6,515 6,450
50 4,434 6,569 5,481 5,852 10,529 8,114 8,371 8,998 9,395 14,569
60 4,307 7,329 9,300 10,419 13,686 14,669 14,932 13,444 14,147 13,979
70 5,624 9,409 8,910 14,923 13,554 14,148 14,906 17,197 18,818 18,077
80 7,961 12,127 13,749 14,846 15,840 18,431 19,457 22,832 24,229 23,519
90 8,662 12,833 16,186 18,956 23,695 22,011 19,366 26,253 29,671 30,394
100 11,777 13,651 19,438 21,534 23,423 28,202 24,285 30,531 28,668 38,463
Problem Set #9
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

781

953

1,520

1,375

1,589

1,649

3,705

2,857

4,096

2,362
30 2,045 2,229 3,205 2,690 4,083 3,737 5,494 4,477 3,994 7,667
40 3,261 4,261 3,719 4,435 4,305 6,246 7,525 8,689 7,004 7,020
50 4,425 6,928 7,387 7,393 10,724 11,510 9,845 12,883 10,520 11,807
60 6,329 7,137 8,206 9,326 10,250 13,259 11,568 13,300 14,057 14,797
70 5,082 10,197 10,028 10,695 13,027 19,577 16,963 14,231 20,352 19,515
80 6,883 12,499 13,448 15,684 17,344 18,079 15,999 21,969 21,263 23,881
90 7,274 13,979 12,562 15,662 18,340 17,507 23,142 23,756 29,580 26,924
100 10,395 13,755 20,075 17,632 26,030 28,490 22,486 34,117 34,710 35,083
Problem Set #10
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

510

1,388

1,866

1,254

1,469

2,218

2,521

2,774

2,049

3,193
30 1,993 1,849 3,073 3,597 4,353 4,481 5,607 6,071 3,825 7,581
40 2,403 3,200 4,773 6,347 6,236 6,255 7,619 6,667 9,851 10,931
50 3,770 6,658 6,079 9,826 8,813 6,097 8,168 10,211 12,504 10,042
60 5,862 6,323 5,893 10,296 9,764 12,307 9,857 15,527 18,070 16,618
70 4,518 9,158 10,005 14,339 14,199 15,192 16,125 19,578 18,852 16,344
80 7,086 9,787 16,036 13,676 15,318 18,683 23,695 26,665 28,428 20,873
90 8,195 17,616 16,185 16,258 19,083 22,280 22,618 24,179 28,620 32,009
100 9,971 16,430 22,235 17,597 21,047 22,342 24,138 26,708 30,557 34,373
 

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