Code for Constraint Satisfaction Problems

Xilman has asked for the wisdom of the Perl Monks concerning the following question:

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.
[download]

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}
[download]

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

Comment on Code for Constraint Satisfaction Problems Select or Download Code

Replies are listed 'Best First'.
Re: Code for Constraint Satisfaction Problems by blokhead (Monsignor) on Jan 16, 2010 at 17:42 UTC
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. blokhead	[reply]
Re: Code for Constraint Satisfaction Problems by jdporter (Paladin) on Jan 17, 2010 at 03:44 UTC
And there's always AI-Prolog. :-)	[reply]
Re: Code for Constraint Satisfaction Problems by andreas1234567 (Vicar) on Jan 16, 2010 at 22:59 UTC
Perhaps GLPK and Math::GLPK could be useful? Otherwise I'd suggest AMPL (for pay, non-perl). -- No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]	[reply]
Re: Code for Constraint Satisfaction Problems by BrowserUk (Patriarch) on Jan 17, 2010 at 15:40 UTC
implies that the largest possible acceptable set has 32 members. Update: Ignore or downvote <Reveal this spoiler or all in this thread> Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "I'd rather go naked than blow up my ass"	[reply] [d/l]
Re^2: Code for Constraint Satisfaction Problems by salva (Canon) on Jan 17, 2010 at 16:12 UTC
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	[reply]
Re^3: Code for Constraint Satisfaction Problems by BrowserUk (Patriarch) on Jan 17, 2010 at 17:16 UTC
Grrr. You're right! There is a big difference between: `my $n = unpack '%32b', ( $set[ $x ] ^ $set[ $y ] );` [download] and my $n = unpack '%32b', pack 'N`', ( $set[ $x ] ^ $set[ $y ] ) +; [download] Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "I'd rather go naked than blow up my ass"	[reply] [d/l] [select]
Re: Code for Constraint Satisfaction Problems by BrowserUk (Patriarch) on Jan 18, 2010 at 22:42 UTC
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 [download] 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. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "I'd rather go naked than blow up my ass"	[reply] [d/l]
Re^2: Code for Constraint Satisfaction Problems by salva (Canon) on Jan 19, 2010 at 14:32 UTC
aren't you forgetting something?	[reply]