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