[sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Nicolas,
On 2013-04-16, Nicolas M. Thiery nicolas.thi...@u-psud.fr wrote:
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
How can this be done in Sage?
Thank you,
Simon
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Gary, On 2013-04-15, Gary McConnell garymako...@googlemail.com wrote: I'm struggling a little to understand what the programming bottleneck is in all this. Clearly you do not want a completely naive search as you said above; but are the 'tests' of the f_i on each m expensive in time, and is the proof of the zero-dimensionality of the ideal also a slow process (ie I assume you have to proceed via Groebner bases over the poly ring in some number t of indeterminates over F_p right?) Yes, it involves Gröbner bases. But to my experience, the test is not overly expensive. Nevertheless, I would not like to test more than a couple of hundred candidates. That's why I want to reduce the number of candidates, on the one hand, but also I want to start with those candidates where I see a good likelyhood that they yield a last parameter. Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-combinat-devel] Re: Relabelled cartan types
Hi, Nicolas et al: Thanks for taking care! I am orry for not having done this myself. I am just overworked. If I have the time I'll try to test it during the weekend. Cheers, Jesús -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
On Tue, Apr 16, 2013 at 09:09:19AM +, Simon King wrote:
On 2013-04-16, Nicolas M. Thiery nicolas.thi...@u-psud.fr wrote:
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
How can this be done in Sage?
sage: MixedIntegerLinearProgram?
:-)
But Nathann will be the one to tell you about the status for the
iteration feature.
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
