On Monday, September 15, 2014 10:15:10 AM UTC+1, Nathann Cohen wrote:
>
> Yo !
>
> > I see. By the way, there is an approach to do this using ILP. At some
> point
> > you have a 0-1 LP with NO sets generated so far as inequalities (and
> > other inequalities that cut out the solutions found so far)
> > I.e. if {j_1,...,j_m} is a NO-set then the corresponding inequality is
> > x_{j_1}+...+x_{j_m}<=m-1, and the objective function is to maximize
> > sum_j x_j.
> >
> > If your ILP is ineafsible, you're done.
> >
> > If you find a solution, say,
> > x_{j_1}=...=x_{j_m}=1, and the remaining x_k=0,
> > you add the inequality x_{j_1}+...+x_{j_m}<=m-1 to your list;
> > (this cuts out this solution from being considered again)
> >
> > you also test the solution with your f, and if it passes, you store it.
> >
> > Now start with empty 0-1 LP, and run the ILP solver again and again,
> until
> > done.
> >
> > You end up with a list of stored solutions (ordered by size, in fact)
> >
> > Implementing this would need a fast way to re-start the ILP solver
> > (which CPLEX and GUROBI should do very well, I suppose)
>
> It is very kind of you to explain me how to write a LP.
>
> There are at least two problems with what you say:
>
> 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)
>
> 2) If you fix it by minimizing instead of maximizing, (and by adding a
> constraint when you find a yes-set, and by adding a constraint when you add
> a no-set) then you are back to what my implementation does, except that you
> are solving a LP at each node while it can be done directly with the code I
> wrote. Faster.
>
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...
> 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.
