The Pseudo-Boolean Optimization Website

 Small-d

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

1,758

2,193

2,986

3,056

3,814

6,661

4,648

5,420

6,568

7,336
30 3,890 4,274 4,513 9,616 6,510 9,077 11,175 9,233 11,430 11,186
40 4,303 9,359 8,108 8,262 13,649 11,328 13,155 14,248 13,679 13,939
50 9,489 13,380 13,230 13,159 15,652 25,496 29,526 22,366 25,589 22,911
60 10,450 13,786 19,818 17,647 15,706 21,904 27,266 30,773 21,013 27,513
70 12,986 14,977 21,431 24,119 27,920 24,789 39,136 35,208 35,927 33,515
80 14,433 18,741 30,426 32,304 34,691 30,951 38,812 38,424 54,898 50,560
90 16,361 21,457 30,684 33,488 48,279 53,601 47,917 64,908 54,266 59,923
100 19,319 33,709 39,152 40,600 42,812 48,968 57,904 72,030 72,391 55,701
Problem Set #2
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,474

4,012

3,484

2,120

3,605

3,956

6,225

3,001

4,970

6,125
30 2,902 6,380 6,363 6,845 11,320 9,632 9,764 16,844 10,440 10,793
40 4,480 6,624 9,123 8,771 14,034 11,060 14,436 15,518 19,330 15,482
50 8,338 12,228 11,971 20,126 14,295 18,323 25,060 17,287 21,707 25,139
60 7,740 13,301 15,390 24,728 19,607 22,336 19,911 31,208 25,959 31,756
70 11,778 16,348 22,413 22,730 37,114 32,188 29,306 34,259 38,458 35,332
80 15,440 25,564 28,167 28,408 29,217 36,570 51,161 40,518 35,838 51,292
90 15,809 29,593 34,148 40,381 44,346 38,489 49,699 55,986 55,566 57,136
100 24,581 31,245 36,395 42,376 44,895 44,167 62,053 51,368 62,321 75,512
Problem Set #3
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,175

2,836

3,093

3,733

3,730

5,792

4,199

7,447

4,444

6,144
30 2,710 5,369 6,421 5,489 7,354 9,232 8,518 12,696 11,494 13,260
40 5,889 8,567 12,641 9,844 11,444 12,165 12,208 11,920 17,182 20,967
50 6,251 10,348 16,368 13,894 16,795 17,716 20,421 16,078 22,512 26,208
60 11,052 11,284 16,269 21,146 23,184 23,223 23,340 26,047 25,268 33,790
70 11,137 19,789 26,755 20,894 31,095 37,519 34,877 33,457 36,570 41,114
80 15,501 22,797 31,068 27,607 36,788 46,510 38,984 33,328 37,700 55,362
90 15,942 25,005 32,101 41,451 45,138 48,798 39,699 53,229 59,260 63,208
100 21,237 27,737 40,018 45,381 39,403 49,769 58,913 53,898 79,804 72,607
Problem Set #4
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,211

4,298

3,443

3,918

1,827

3,798

5,306

4,234

4,249

4,664
30 2,188 3,765 4,754 8,187 5,541 8,454 10,693 11,411 8,204 11,402
40 6,924 7,782 8,556 12,530 11,263 11,438 14,599 14,658 19,132 24,292
50 5,838 10,926 15,508 14,150 18,266 15,881 19,987 17,672 25,069 25,015
60 11,890 14,386 19,271 17,619 28,032 26,707 22,983 29,928 28,866 35,253
70 11,142 20,069 22,950 20,204 22,090 22,860 30,364 33,213 37,857 42,761
80 13,630 24,537 24,456 30,368 27,227 37,249 44,054 38,207 52,118 45,704
90 17,957 29,098 32,753 38,167 45,165 48,488 40,704 59,014 56,801 64,092
100 20,526 29,570 29,801 44,031 52,597 49,182 51,661 60,535 54,888 71,247
Problem Set #5
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,143

2,484

3,999

3,771

5,351

4,360

3,305

3,901

8,777

5,027
30 2,139 5,096 5,288 6,043 10,199 5,420 9,780 7,157 7,839 13,927
40 7,008 5,823 10,683 13,491 10,938 14,472 12,748 16,909 19,372 15,079
50 5,210 14,691 12,237 13,815 15,077 17,842 20,659 20,314 21,377 26,509
60 10,335 14,058 20,892 21,819 17,737 19,631 26,449 27,493 30,848 29,689
70 11,662 18,082 19,501 26,894 29,545 27,464 37,405 41,147 42,877 39,422
80 15,013 20,335 28,829 31,511 38,984 42,649 33,458 43,866 48,586 36,380
90 16,505 26,695 32,921 34,011 44,254 40,681 51,818 50,305 57,215 59,570
100 23,806 26,073 34,373 44,055 52,172 51,283 62,414 55,671 69,977 61,185
Problem Set #6
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,248

2,055

2,779

2,559

3,320

5,360

4,552

4,177

8,676

6,407
30 3,229 2,644 4,682 7,766 9,045 8,734 8,909 12,130 9,461 11,718
40 6,032 7,850 9,140 11,817 14,121 14,099 11,991 16,951 14,496 15,169
50 6,765 9,934 14,088 14,772 17,279 15,521 17,999 25,342 23,906 28,650
60 9,225 12,946 19,772 16,067 22,410 18,170 28,287 33,865 34,684 28,106
70 9,938 20,038 20,044 23,399 26,463 30,127 37,653 32,660 34,310 32,679
80 15,045 19,634 27,673 37,789 32,816 43,560 40,147 35,566 51,569 39,512
90 14,930 26,527 27,197 36,939 54,230 50,135 43,086 42,978 64,707 57,234
100 20,081 26,599 34,786 40,202 46,383 53,265 60,649 55,407 66,398 72,290
Problem Set #7
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

783

1,854

3,996

3,176

3,977

6,353

4,730

5,770

6,015

4,134
30 2,325 4,943 4,223 4,508 8,107 11,106 12,377 7,349 8,873 12,328
40 6,458 3,868 10,156 9,617 12,542 14,707 12,168 14,233 17,236 18,151
50 8,901 9,275 12,898 14,275 14,292 20,276 18,413 23,174 18,426 27,461
60 10,651 11,805 12,612 21,267 18,955 17,287 24,751 32,641 29,871 28,438
70 13,637 19,819 20,401 21,106 23,830 34,060 34,607 33,838 37,677 38,114
80 13,492 19,511 25,096 28,950 36,426 43,007 41,238 49,640 35,774 53,333
90 16,756 26,158 36,127 33,796 49,265 44,140 55,229 54,451 46,289 46,903
100 20,648 20,566 44,794 38,249 43,150 44,586 66,955 58,755 51,984 51,167
Problem Set #8
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,948

3,010

4,678

2,577

4,102

5,746

3,709

4,352

4,338

5,854
30 3,884 3,569 5,534 9,167 7,762 8,359 10,430 9,820 7,364 7,491
40 5,097 5,283 9,761 10,851 10,286 12,671 14,084 13,978 17,708 19,673
50 7,075 14,739 8,686 17,024 15,475 13,841 16,373 19,283 25,002 30,735
60 9,606 9,541 17,946 20,057 21,344 23,881 32,270 26,184 27,060 30,879
70 9,643 20,593 21,541 24,711 24,718 29,065 32,812 35,257 36,484 41,254
80 13,642 22,979 32,519 32,046 38,861 42,004 31,348 41,623 51,731 46,847
90 16,365 29,966 31,775 33,046 33,923 50,061 47,354 53,721 46,973 47,323
100 23,045 40,186 42,756 47,453 48,222 54,846 58,980 64,377 61,552 64,583
Problem Set #9
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

2,002

1,843

2,687

3,592

4,486

5,863

5,413

6,324

8,494

7,007
30 3,106 5,006 5,792 7,181 8,043 8,682 6,531 10,161 10,907 10,978
40 6,421 7,295 6,956 8,832 13,180 12,837 15,711 15,402 14,807 17,937
50 8,723 12,584 11,996 16,839 15,993 16,745 17,536 21,955 24,839 26,172
60 10,041 11,684 14,570 15,572 21,408 22,947 27,221 21,733 31,215 26,753
70 13,020 20,494 17,535 23,362 26,243 30,873 37,009 36,320 33,218 40,533
80 18,176 17,979 22,684 32,734 34,290 44,195 45,568 43,831 39,988 47,287
90 14,582 24,474 34,681 35,968 38,656 60,813 54,131 51,139 54,696 55,282
100 24,249 29,177 37,166 48,254 47,371 42,315 55,816 54,281 69,600 64,542
Problem Set #10
n/d 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
20

1,848

2,125

2,209

4,285

2,931

3,415

4,597

3,963

6,007

3,371
30 3,098 4,742 6,328 9,053 8,146 8,346 12,197 10,269 11,565 9,997
40 8,100 6,229 11,457 13,049 9,002 12,834 13,112 16,671 21,748 15,833
50 8,199 11,293 12,379 17,208 16,928 23,693 18,394 22,633 25,206 17,989
60 8,394 15,445 16,944 16,964 19,379 28,547 21,939 31,243 30,686 29,916
70 11,041 18,107 26,236 32,241 22,190 35,605 43,423 36,511 36,441 38,865
80 12,653 23,456 28,764 28,699 30,917 33,735 36,546 41,922 32,375 46,382
90 19,460 33,432 41,582 34,734 34,960 43,163 45,787 54,695 54,484 49,511
100 19,319 32,385 42,801 44,673 44,412 59,396 54,886 50,487 69,795 80,742
 

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