On Monday, September 15, 2014 10:40:31 AM UTC+1, Nathann Cohen wrote: > > Yo ! > > >> 1) Make it run in your head with a boolean function f constant to > "False". It will enumerate the 2^n no-sets. > > > > corner cases are hard, in theory too :-) > > You can certainly add a pre-testing by evaluating f on all singletons > and pairs, say. > > (and this would also speed up things for functions having some NO > singletons and pairs quite a bit) > > This is not a corner case. What it tells you is that you do not > enumerate inclusionwise minimal no-sets, and that you will pay for it. > Make it run with lambda x: len(x)<5 on a set X of size 15, same > result. >
enumerating inclusion-wise minimal no-sets is not a remedy: if f =(lambda x: len(x)<k) for |X|=2k, you're pretty much out of luck. > > not necessarily faster. Your code completely ignores the polyhedral > nature of the problem; e.g. the ILP can potentially terminate quite fast, > > due to it finding that the polyhedron defined at some point is already > empty, while your code will keep looking for non-existing things... > > It will not. And you can think of the "polyhedral nature" of binary > vectors all you want, if you need to enumerate them just do it the > straightforward way, not with a LP solver. > we don't need them all, we only need the maximal ones. LP won't even look at subsets of an already discovered yes-set. > > In this special case I don't see how a LP could beat a code where > feasibility is checked by intersection of bitsets. But if you care I > would be glad to see by how much it beats the LP method :-P > your bitsets are not pruned, and eventually you might end up with too many of them to be efficient. Whereas ILP solver would discard redundant inequalities. As well, as you know, there are combinatorial problems, e.g. finding a maximum clique in a graph, where ILP might beat the straight combinatorial algorithms. Now make your f report True on a graph clique, and False on a non-clique, and wait forever for your code to finish... > > Nathann > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
