Code for Constraint Satisfaction Problems

[Xilman]

I have a fairly typical constraint satisfaction problem (CSP) and I expected to be able to find a Perl module to help me solve it. No such luck --- either it doesn't exist or I haven't yet found the correct set of search terms.

Here is the problem:

Find a set of B-bit integers such that:
    the size of the set is at least S AND
    for every pair (x, y) where y!=x, of set elements, w(x^y) >= W.

Here, w(x) is defined as the number of non-zero bits in x.

For concreteness, let B=12, W=5 and S=20. This is an acceptable set:

{0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0,
 0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21,
 0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}

because it has 21 values and 21 >= S.

http://www.win.tue.nl/~aeb/codes/binary-1.html implies that the largest possible acceptable set has 32 members.

A simple-minded approach of choosing random integers in the range 0 ... 0xfff and testing for consistency with previously chosen integers has found sets with 24 members.

Question: can anyone point me to a module / script which can find significantly larger acceptable sets in a reasonable amount of computation. Brute force searching of a (2<<12)<<32 sized space is not reasonable!

Paul

[blokhead]

If you just want the optimal binary code for a certain set of parameters, then the easiest way would be to track down the references from that website and get ahold of the actual articles/books (or perhaps the authors). ;)

If you really want to do be able to do it computationally, this seems exceedingly difficult. One possible simplifying idea that I can suggest is to only look for linear codes. This will add some much-needed structure to the search space to exploit. You "only" need to search for a good parity-check matrix for the code. However, this might still be pretty computationally intensive. And since the numbers in that table are mostly powers of two, it is at least plausible that a linear code (whose number of codewords is always a power of two) can achieve the optimal parameters.

[jdporter]

And there's always AI-Prolog. :-)

[andreas1234567]

Perhaps GLPK and Math::GLPK could be useful? Otherwise I'd suggest AMPL (for pay, non-perl).

[BrowserUk]

implies that the largest possible acceptable set has 32 members.

Update: Ignore or downvote

I don't believe that to be the case:

C:\test>817762 -B=12 -W=5
The following set contains 128 12-bit integers where w( x ^ y ) >= 5
31 32 64 96 128 160 192 224 256 288 320 352 384 416 448 480 512 544 57
+6 608 640
672 704 736 768 800 832 864 896 928 960 992 1024 1056 1088 1120 1152 1
+184 1216 
1248 1280 1312 1344 1376 1408 1440 1472 1504 1536 1568 1600 1632 1664 
[phone] 
1760 1792 1824 1856 1888 1920 1952 1984 2016 2048 2080 2112 2144 2176 
[phone] 
2272 2304 2336 2368 2400 2432 2464 2496 2528 2560 2592 2624 2656 2688 
[phone] 
2784 2816 2848 2880 2912 2944 2976 3008 3040 3072 3104 3136 3168 3200 
[phone] 
3296 3328 3360 3392 3424 3456 3488 3520 3552 3584 3616 3648 3680 3712 
[phone] 
3808 3840 3872 3904 3936 3968 4000 4032 4064

C:\test>817762 -B=12 -W=6
The following set contains 64 12-bit integers where w( x ^ y ) >= 6
63 64 128 192 256 320 384 448 512 576 640 704 768 832 896 960 1024 108
+8 1152 
1216 1280 1344 1408 1472 1536 1600 1664 1728 1792 1856 1920 1984 2048 
[phone] 
2240 2304 2368 2432 2496 2560 2624 2688 2752 2816 2880 2944 3008 3072 
[phone] 
3264 3328 3392 3456 3520 3584 3648 3712 3776 3840 3904 3968 4032

C:\test>817762 -B=12 -W=7
The following set contains 32 12-bit integers where w( x ^ y ) >= 7
127 128 256 384 512 640 768 896 1024 1152 1280 1408 1536 1664 1792 192
+0 2048 
2176 2304 2432 2560 2688 2816 2944 3072 3200 3328 3456 3584 3712 3840 
+3968

C:\test>817762 -B=14 -W=7
The following set contains 128 14-bit integers where w( x ^ y ) >= 7
127 128 256 384 512 640 768 896 1024 1152 1280 1408 1536 1664 1792 192
+0 2048 
2176 2304 2432 2560 2688 2816 2944 3072 3200 3328 3456 3584 3712 3840 
+3968 
4096 4224 4352 4480 4608 4736 4864 4992 5120 5248 5376 5504 5632 5760 
+5888 
6016 6144 6272 6400 6528 6656 6784 6912 7040 7168 7296 7424 7552 7680 
+7808 
7936 8064 8192 8320 8448 8576 8704 8832 8960 9088 9216 9344 9472 9600 
+9728 
9856 9984 10112 10240 10368 10496 10624 10752 10880 11008 11136 11264 
+11392
11520 11648 11776 11904 12032 12160 12288 12416 12544 12672 12800 1292
+8 
13056 13184 13312 13440 13568 13696 13824 13952 14080 14208 14336 1446
+4 
14592 14720 14848 14976 15104 15232 15360 15488 15616 15744 15872 1600
+0 
16128 16256

C:\test>817762 -B=14 -W=8
The following set contains 64 14-bit integers where w( x ^ y ) >= 8
255 256 512 768 1024 1280 1536 1792 2048 2304 2560 2816 3072 3328 3584
+ 3840 
4096 4352 4608 4864 5120 5376 5632 5888 6144 6400 6656 6912 7168 7424 
+7680 
7936 8192 8448 8704 8960 9216 9472 9728 9984 10240 10496 10752 11008 1
+1264 
11520 11776 12032 12288 12544 12800 13056 13312 13568 13824 14080 1433
+6 
14592 14848 15104 15360 15616 15872 16128

C:\test>817762 -B=14 -W=9
The following set contains 32 14-bit integers where w( x ^ y ) >= 9
511 512 1024 1536 2048 2560 3072 3584 4096 4608 5120 5632 6144 6656 71
+68 
7680 8192 8704 9216 9728 10240 10752 11264 11776 12288 12800 13312 138
+24 
14336 14848 15360 15872

[salva]

The following set contains 128 12-bit integers where w( x ^ y ) >= 5

31 32 64 96 128 160 192 224 256 288 320 352 384 416 448 480 512 544 576 608 640...

check your program, w(32 ^ 64) is 2 < 5

[BrowserUk]

Grrr. You're right! There is a big difference between:

        my $n = unpack '%32b*', ( $set[ $x ] ^ $set[ $y ] );

and

        my $n = unpack '%32b*', pack 'N`', ( $set[ $x ] ^ $set[ $y ] )
+;

[BrowserUk]

For your example of B=12 and W=5, there are 140 sets for S=24; 15 for S=25 and 7 for the maximum S=26:

C:\test>817762-3 -B=12 -W=5 -S=24
25 : 55 64 139 252 773 794 994 1320 1359 1425 1619 1670 1769 1908 
     1983 2390 2425 2444 2606 2704 2783 3101 3258 3303 3875
26 : 187 192 259 284 493 548 591 881 982 1109 1130 1446 1554 1673 
     1788 1855 2166 2190 2480 2648 2709 2787 2858 3105 3419 3908
26 : 188 192 259 349 526 561 727 868 1003 1114 1127 1320 1430 1521 
     1673 1855 2153 2203 2418 2469 2510 2722 2840 3076 3708 3905
26 : 189 192 259 348 526 560 727 869 1002 1115 1126 1320 1430 1521 
     1673 1855 2153 2202 2418 2468 2511 2723 2841 3077 3708 3904
26 : 190 192 259 348 525 560 727 870 1001 1115 1125 1320 1429 1522 
     1674 1855 2154 2201 2417 2468 2511 2723 2842 3078 3708 3904
25 : 208 231 257 286 546 573 970 1099 1164 1380 1458 1622 1927 2041 
     2152 2203 2419 2477 2629 2814 2964 3421 3608 3745 3886
25 : 209 230 256 287 547 572 970 1099 1164 1381 1458 1622 1927 2041 
     2152 2202 2419 2477 2629 2815 2964 3420 3609 3744 3886
25 : 210 229 256 287 547 572 969 1099 1164 1382 1457 1621 1927 2042 
     2152 2201 2419 2478 2630 2815 2964 3420 3610 3744 3885
25 : 211 228 256 287 547 572 969 1098 1165 1383 1457 1621 1926 2042 
     2153 2200 2418 2478 2630 2815 2965 3420 3611 3744 3885
25 : 248 256 287 483 549 586 659 886 973 1067 1105 1158 1388 1461 
     1564 1791 2098 2119 2185 2478 2516 2873 3418 3680 3843
25 : 304 323 396 511 517 538 736 1062 1096 1169 1651 1724 1743 1833 
     1876 1922 2091 2134 2685 2967 3017 3301 3322 3357 3950
25 : 305 322 396 511 517 538 736 1062 1097 1168 1651 1725 1742 1832 
     1876 1923 2091 2135 2684 2966 3017 3301 3322 3357 3951
25 : 306 321 396 511 518 537 736 1061 1098 1168 1651 1726 1741 1832 
     1876 1923 2091 2135 2684 2965 3018 3302 3321 3358 3951
25 : 307 320 397 510 518 537 737 1061 1099 1168 1650 1727 1740 1832 
     1877 1923 2090 2135 2684 2964 3018 3302 3321 3358 3951
25 : 308 321 394 511 518 537 736 1059 1100 1168 1653 1726 1739 1832 
     1874 1925 2093 2135 2682 2963 3020 3302 3321 3358 3951
25 : 309 320 395 510 518 537 737 1059 1101 1168 1652 1727 1738 1832 
     1875 1925 2092 2135 2682 2962 3020 3302 3321 3358 3951
25 : 310 320 395 509 517 538 738 1059 1102 1168 1652 1727 1737 1832 
     1875 1926 2092 2135 2681 2961 3020 3301 3322 3357 3951
25 : 311 320 395 508 517 538 738 1064 1103 1169 1652 1727 1875 1926 
     2025 2134 2169 2188 2862 2960 3039 3301 3357 3514 3619
26 : 312 321 390 511 522 533 736 1059 1100 1168 1654 1709 1755 2084 
     2130 2185 2671 2739 2780 3103 3306 3317 3840 3961 4030 4039
26 : 313 320 391 510 522 533 737 1059 1101 1168 1654 1708 1755 2084 
     2131 2185 2671 2738 2780 3102 3306 3317 3841 3960 4031 4038
26 : 314 320 391 509 521 534 738 1059 1102 1168 1653 1708 1755 2084 
     2131 2186 2671 2737 2780 3101 3305 3318 3842 3960 4031 4037
25 : 315 320 391 508 521 534 738 1060 1103 1169 1656 1727 1875 1930 
     2021 2133 2188 2779 2862 2960 3098 3305 3318 3619 3869

The script that produced the above is brute force, but finds all possible sets (for S=1 through S=26 inclusive) in under 1 minute.

[salva]

aren't you forgetting something?