The Pseudo-Boolean Optimization Website

 Small-b

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

680

872

725

1,382

801

1,268

986

1,094

854

1,441
30 1,243 1,296 1,047 1,716 2,352 1,965 2,917 2,664 3,572 2,651
40 1,301 2,364 2,935 2,341 2,507 2,573 4,260 3,811 4,050 3,984
50 2,327 3,933 3,356 4,521 4,092 4,427 8,105 6,549 5,033 7,393
60 2,234 4,058 5,081 4,908 4,988 4,820 7,010 8,432 7,234 6,525
70 3,337 4,394 5,436 5,929 6,023 12,391 7,433 9,448 9,315 9,099
80 4,250 4,867 5,992 8,920 9,325 9,599 10,052 9,713 11,482 12,264
90 5,767 5,691 8,806 9,880 11,738 13,487 11,220 12,520 15,646 14,952
100 5,790 8,353 11,348 10,000 12,040 14,499 13,824 17,039 14,331 18,264
Problem Set #2
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

387

898

883

642

816

717

1,841

1,302

1,223

1,491
30 786 1,733 1,305 1,530 2,072 2,409 2,669 2,391 2,171 2,900
40 1,634 2,489 2,911 2,732 2,876 3,423 5,419 4,384 5,220 4,533
50 2,605 3,176 3,849 3,506 4,204 4,834 4,341 4,019 5,332 6,182
60 2,620 3,017 4,203 4,852 7,984 6,469 6,787 6,955 6,343 8,968
70 4,604 4,695 5,176 6,790 7,094 7,551 8,543 8,946 9,375 10,887
80 5,062 6,329 6,374 7,882 9,149 9,988 11,275 10,711 10,774 10,129
90 5,063 6,102 6,834 9,241 9,828 12,302 11,038 12,012 14,349 14,188
100 4,519 7,380 8,699 10,949 11,400 14,807 14,185 14,276 16,355 17,150
Problem Set #3
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

792

688

1,269

1,168

1,062

791

1,218

1,449

758

1,153
30 1,033 1,249 2,253 1,737 1,457 2,356 1,507 3,116 2,561 2,028
40 904 2,810 2,643 3,799 2,801 3,206 3,551 3,450 3,794 5,460
50 2,024 3,204 3,547 4,711 3,935 4,239 5,762 4,941 6,102 6,909
60 3,412 3,746 3,216 5,050 6,474 5,555 5,413 5,809 6,544 7,012
70 3,558 5,775 5,320 6,384 6,478 9,224 9,883 8,183 10,972 9,821
80 3,053 5,826 6,593 7,476 10,612 10,789 9,705 9,149 8,884 12,141
90 4,519 5,832 6,489 8,633 8,766 10,946 15,693 14,698 15,760 15,765
100 5,679 8,589 10,399 10,303 10,439 12,645 12,152 14,707 15,444 16,193
Problem Set #4
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,077

717

800

696

1,340

1,173

1,516

1,307

1,015

1,248
30 1,199 954 1,802 1,689 1,738 2,282 1,990 1,714 3,264 2,074
40 1,331 1,933 1,982 2,425 3,332 3,627 3,290 3,645 3,888 5,317
50 2,302 2,668 3,883 4,355 5,106 5,762 5,238 7,067 7,270 6,556
60 3,055 3,206 4,821 4,863 5,907 5,385 6,768 7,626 7,104 10,192
70 2,517 4,953 5,503 5,309 5,744 7,165 5,751 8,430 9,437 10,003
80 3,623 4,585 6,710 7,211 9,513 10,086 11,613 10,491 13,765 13,251
90 4,444 5,702 6,718 9,528 10,565 11,970 10,308 15,222 14,999 17,116
100 5,879 7,955 8,275 12,756 11,817 15,447 17,014 16,065 17,382 16,658
Problem Set #5
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

408

737

1,389

926

992

1,048

1,431

1,002

1,915

1,041
30 1,070 1,402 1,770 1,795 2,540 2,553 1,715 2,714 3,087 2,473
40 1,454 2,137 3,446 3,157 2,954 3,190 4,379 4,076 3,417 4,873
50 2,233 2,183 4,277 3,320 2,930 4,115 4,669 5,042 5,355 8,449
60 2,441 4,550 3,770 4,190 6,133 6,003 5,398 6,250 7,946 8,110
70 2,899 4,849 6,126 6,752 7,926 8,932 7,479 9,767 10,258 8,603
80 3,981 6,162 6,341 8,734 8,894 11,144 12,896 10,427 10,699 10,620
90 4,925 7,464 6,271 11,990 8,673 9,960 11,545 13,044 13,002 14,929
100 6,123 8,361 8,699 10,332 14,685 14,801 15,490 15,485 19,961 16,472
Problem Set #6
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

300

613

947

821

893

1,299

1,261

977

1,716

2,445
30 1,092 1,099 1,487 2,328 1,810 1,703 1,732 2,612 1,973 2,918
40 1,913 2,466 2,966 2,872 2,806 4,106 3,245 3,792 3,611 3,608
50 2,499 2,964 3,198 3,675 2,777 3,966 5,198 4,641 5,928 6,923
60 2,876 3,457 5,373 6,158 4,318 7,073 5,100 6,554 5,998 7,388
70 3,856 3,948 5,587 8,644 9,195 7,868 10,555 7,110 10,118 10,022
80 4,177 4,927 6,865 6,458 9,505 9,496 10,229 11,572 14,334 14,687
90 5,088 6,245 7,707 7,341 11,497 13,391 12,017 14,195 15,054 13,927
100 6,279 7,401 11,503 11,803 11,121 13,779 15,966 12,139 15,756 19,209
Problem Set #7
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

803

471

1,471

610

666

1,248

1,317

1,710

2,141

892
30 1,394 1,140 1,614 1,895 1,847 2,208 2,010 2,288 2,715 2,514
40 1,021 2,388 2,414 3,319 2,233 2,964 3,330 3,457 4,197 3,471
50 2,092 3,173 3,071 3,270 4,983 4,044 5,490 5,897 3,913 6,895
60 2,741 3,876 5,176 4,638 4,896 5,064 7,309 6,774 7,251 10,637
70 2,885 4,917 5,272 6,073 7,541 8,101 9,605 8,699 8,956 11,483
80 4,327 5,087 6,386 7,658 10,064 9,133 9,207 12,183 13,315 12,950
90 5,067 5,840 7,658 8,688 8,498 11,233 13,886 14,433 15,353 13,242
100 6,142 8,925 8,639 11,418 11,366 12,536 13,626 14,554 16,486 17,765
Problem Set #8
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

432

1,010

1,318

1,075

1,046

1,613

1,598

1,246

1,612

1,709
30 961 867 1,837 2,330 1,668 1,895 2,183 2,229 3,581 2,591
40 1,270 2,376 2,484 2,130 3,260 3,561 2,742 3,984 3,340 4,120
50 2,474 2,728 3,499 3,027 3,926 5,032 5,693 4,443 5,132 7,504
60 2,746 3,000 4,560 5,969 8,392 6,495 7,895 5,925 6,850 7,250
70 2,428 4,789 6,557 6,854 8,184 7,312 7,588 8,484 6,899 11,108
80 4,066 6,330 5,065 9,853 10,296 11,475 10,508 11,239 12,289 10,624
90 5,451 6,286 7,472 8,813 9,236 10,917 13,629 13,999 12,416 11,408
100 6,050 7,820 9,495 11,520 12,832 12,073 12,360 12,464 12,648 18,042
Problem Set #9
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

426

675

1,449

669

1,205

1,324

1,673

1,383

1,710

1,223
30 840 2,116 1,429 2,057 2,552 1,725 2,216 3,431 3,853 2,409
40 1,483 2,323 2,462 2,926 2,809 3,712 3,036 4,255 3,942 4,446
50 2,956 3,209 3,589 3,423 5,104 4,024 6,240 7,604 5,191 6,771
60 2,465 3,950 3,804 6,065 6,693 6,043 6,251 7,006 6,939 7,885
70 2,875 5,256 4,804 8,202 6,462 7,801 9,348 10,885 9,113 11,671
80 3,996 4,569 5,131 8,738 9,262 9,013 10,671 11,720 11,826 11,869
90 5,218 6,557 9,435 10,985 8,881 11,718 12,413 13,622 13,324 13,252
100 6,729 7,017 8,967 11,336 8,948 14,511 15,979 18,416 16,818 16,352
Problem Set #10
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

525

1,026

812

990

1,069

1,084

1,538

1,224

1,781

1,413
30 1,838 858 1,241 1,967 1,463 2,163 1,856 2,770 2,880 3,461
40 2,011 1,683 1,915 2,273 3,047 3,534 4,161 4,716 4,864 4,405
50 2,004 3,188 3,568 3,979 4,706 5,110 4,140 6,636 5,780 5,259
60 2,918 3,140 4,500 3,589 3,825 5,582 6,667 6,966 9,431 9,682
70 2,241 5,354 5,559 5,754 6,379 8,237 8,224 9,551 10,429 8,367
80 4,065 4,903 7,161 8,783 7,854 8,134 10,208 11,355 12,001 11,916
90 4,542 5,541 8,291 9,058 10,409 12,230 15,188 12,373 12,286 16,569
100 6,090 7,750 8,903 10,964 12,072 14,100 13,230 12,400 13,575 17,551
 

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