On 2014-09-15, Nathann Cohen <[email protected]> wrote: > Yo ! > >> 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. > > Indeed. But it is much, much, much better in most cases. > >> 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. > > I can discard forget them too with my code. I don't really need to keep them. > >> 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. > > They cannot be pruned. There is nothing to prune. I only keep the minimal > ones. > >> 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... > > In this case the list of no-sets is known from the start, and it is > small. And the boolean function can be quickly evaluated. Clearly not > what this function is meant to handle.
you wanted to know a function f that might be harded for your algorithm vs ILP, and I give you one, as above. I won't tell you it comes from a graph. (and I implement it to be very slow on small-size subsets :-)) -- 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.
