On Monday, September 15, 2014 9:31:53 AM UTC+1, Nathann Cohen wrote:
>
> Yo !
>
> > In this language, your code enumerates true/false assigments to the
> variables
> > x_j, so that all these NO clauses hold true.
> > These NO clauses are just an encoding of your "matrix of NOs" that I
> understood
> > you write out completely. But now you write that you can't do this.
> > Oh well.
>
> Yes, but in this formalism they consider the function as a black box,
> which is exactly what I am doing when I run the function I mentionned
> in this thread.
>
> The matrix that I build in this function does not contain all no-sets.
> At first it contains none. And every time the function F is called, we
> 'learn' either a yes-set (that we store) or a no-set (that we add to
> the matrix, in order to filter other sets later). I cannot enumerate
> all no-set and all yes-sets, for the union of them is 2^n. But the
> function tries to do its job by only having to meet the inclusionwise
> mininal no-sets, which it computes while the functions does its
> exploring.
>
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)
Dima
> 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.
