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.
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.
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 sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
