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