Recall that the integer-programming approach giving unequal numbers of bottles for different codewords was proposed early on here by Thomas (on 11/20), who took as codewords all words of length 10 with weights 0, 1, 2, or 3, and having the number of rats assigned to each bin be 45, 13, 5, and 5, respectively. This is the optimal fully symmetric (that is, invariant under the full S_10 group acting on the rats) solution. If you don't constrain to integers, the fraction of bottles discarded is 40 / 397 (which would be a little over 100.75), and the fraction of rats assigned to codewords of each weight is 17/397, 5/397, 2/397, 2/397 respectively. So as to Veit's underlying question: this capped-union-codes approach is nice in that it's a computationally more-approachable restriction of the problem that seems to be doing pretty well, but I certainly don't see any reason to think that the optimal code should involve partitioning bottles close to uniformly among used codewords. --Michael On Sun, Jan 27, 2013 at 2:41 PM, Veit Elser <ve10@cornell.edu> wrote:
I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist.
Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code!
Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats:
Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49.
Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes.
I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats:
n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49
The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop!
-Veit
On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10@cornell.edu> wrote:
Wow -- that was fast!
wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.