Re: [sage-combinat-devel] Integer solutions with Sage
Hi Nathann On 03/16/12 11:06, Nathann Cohen wrote: the availability of a feature in Sage's support of LP : iterate/count integer solutions. SCIP already has counting/enumeration of integer solutions built-in. Because of the license issues, it will probably never be a standard package, but it could be used for benchmarking/testing. Best -- Robert Schwarz signature.asc Description: OpenPGP digital signature
Re: [sage-devel] Enumeration of the integer points of a polytope
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 06/08/2010 11:30 AM, Nathann Cohen wrote: A long, long time ago there had been some discussion going on about the possible enumeration of the integer points of a polytope... By sheer luck, I learned today of such a software named PORTA : http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/ A more recent version is available at http://www.zib.de/Optimization/Software/Porta/ I'm not sure, how well it could be used as a library, though. There is also the PPL at http://www.cs.unipr.it/ppl/ that includes the same functionality, but is designed as a library, and is in active developement. There might be license issues though, the PPL uses GPL3. Making the latter available to Sage would certainly interest me. - -- Robert Schwarz rschwarz.net -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkwOJbwACgkQQEmQCGIkeRoPPgCfRtT1XncRXs836H99t5N0OlWa WIUAn2IPKW1nIqOwMKs5yESD82Lla+bn =95NA -END PGP SIGNATURE- -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Enumeration of the integer points of a polytope
On 06/08/2010 07:50 PM, Volker Braun wrote: Can PPL find integral points in polyhedra with not necessarily integral vertices (mixed integer programming)? I'm somewhat familiar with the library but I don't see how to do that. Code sample? To be honest, I've only used it to compute linear descriptions of convex hulls of binary points. Scanning through the documentation, I can't find any enumeration method either. Only tests for (integer) set elements in the Polyhedron class, and the MIP class can also produce _a_ feasible point. The Grid abstraction PPL provides doesn't seem to help either, sorry for the false advertising. -- Robert Schwarz -- rschwarz.net -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
[sage-devel] Re: Polymake Status / Porta
Chris Swierczewski wrote: Hello, I see that in the past there was some interest in polymake. I'm suddenly interested as well in the package and was wondering if anyone out there had done any work on it since the most recent discussion in the mailing list back in June: http://groups.google.com/group/sage-devel/browse_thread/thread/2720927446e35cd1/3759590c6affdcdb?lnk=gstq=polymake#3759590c6affdcdb I tried installing the spkg on my local Sage install on sage.math and, as expected there were errors. I can post those errors if anyone is interested. Installing Polymake didn't even work from any of the source packages for me. Mostly Perl related problems, I guess. What I really need is the functionality in Porta. (http://www.iwr.uni- heidelberg.de/groups/comopt/software/PORTA/) Porta is integrated into Polymake. If there is an overwhelming request for someone to take another stab at Polymake then I can certainly make an attempt. Otherwise, I'll just see if I can write up a wrapper for Porta. Porta is all executable binaries so, with the subprocess module, it shouldn't be to difficult to wrap. There is a more recent version of PORTA available at http://www.zib.de/Optimization/Software/Porta/ Anyways, all of PORTA's functionality is also covered by the Parma Polyhedral Library (http://www.cs.unipr.it/ppl/) which is a feature-rich modern C++ library with active developement. They also have some interfaces to programming languages, not including Python, though. The PPL could be interesting for Sage for more applications than polyhedral computations, I hope. And it's guaranteed to build well, since it's now a dependency for gcc4.2 ?! -- Robert Schwarz m...@rschwarz.net Get my public key at http://rschwarz.net/key.asc --~--~-~--~~~---~--~~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] possible bug in permutation/quotient group?
Hi all, I was just playing around with permutations, when something
puzzled me:
sage: G = SymmetricGroup(4)
sage: H = G.normal_subgroups()[1]
sage: H
Permutation Group with generators [(1,3)(2,4), (1,4)(2,3)]
sage: G.quotient_group(H)
Permutation Group with generators [(1,2)(3,6)(4,5), (1,3,5)(2,4,6)
Where do the 5 and 6 suddenly come from? In my understanding the
elements of the quotient group G/H are classes of elements of G, which
operates on {1, 2, 3, 4}.
Also, there is a method of G called quotient, which raises and
NotImplementedError, which is a little confusing, given an
implementation of the quotient group is actually available.
Running Sage 4.1 on Arch Linux 64 bit.
--
Robert Schwarz m...@rschwarz.net
Get my public key at http://rschwarz.net/key.asc
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: possible bug in permutation/quotient group?
javier wrote:
On Jul 31, 4:47 pm, David Joyner wdjoy...@gmail.com wrote:
Maybe I don't understand your question. It seems you are claiming
thatif G is a permutation group and H is a normal subgroup then
the quotient G/H embeds into G. Are you sure that is true?
In general, no it isn't. We have the short exact sequence
1 -- H -- G -- G/H --1
to embed G/H into G we would need it to split, which would mean that
the extension is trivial, or that G factorizes as a product of H and
G/H.
OK, my fault, too much wishful thinking here.
kcrisman wrote:
Look at
sage: G.quotient_group??
It turns out that Sage asks GAP to create the image of the morphism G -
G/H, as far as I can tell, and in so doing creates that image as a
separate (sub)permutation group. In particular, it using
RegularActionHomomorphism to do this, and at
http://www.gap-system.org/Manuals/doc/htm/ref/CHAP039.htm#SSEC007.2 it
says returns an isomorphism from G onto the regular permutation
representation of G and certainly in this case G/H (the relevant
group) has six elements!
Though I agree that this could be confusing, the good part is that
this creates (an isomorphic) group without having to talk about which
element of the coset you pick each time. It would be misleading to
say that (1234) was an element of G/H (which I think is what David was
getting at). There are ways to get cosets in GAP, of course (maybe
wrapped in Sage?) but I don't know much about them.
I hope this helps!
Yes, the cosets are, what I really want (although generators would be
very nice, too, if they exist, e.g. if the quotient is normal).
The application was the following: Suppose you have a linear equation
with multi-indexed variables, like x_1,2 + x_2,3 + x_3,1 == 0, which
also holds for all permutations of {1, 2, 3}, and I want to enumerate
all possible equations, but without duplicates. I hoped it was possible
to first compute the permutations under whose operation the exact same
equation result, then take the subgroup H generated by those and use
representants from the cosets of S_n/H to get all unique equations.
Looks like it's not that simple, since H doesn't even have to be normal,
in general.
Thanks a lot , though.
--
Robert Schwarz m...@rschwarz.net
Get my public key at http://rschwarz.net/key.asc
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: possible bug in permutation/quotient group?
javier wrote:
If that you want are the cosets you can get them simply using
cosets = Set([Set([h*g for h in H]) for g in G])
or if you want to get a representative of each coset you can then use
reps = [x[0] for x in cosets]
this should work even if H is not normal, the only issue being that
the set of cosets is not a group. Not sure if it will help with your
problem, though.
Yes, I will use that, for now, although I was hoping to get a nice
representation of the set of cosets, in terms of generators.
Anyway, it looks like I wasn't expecting too much after all. On
http://en.wikipedia.org/wiki/Group_action or S. Lang: Algebra (p. 28)
I find exactly what I want, supposing a group G acts transitively on a
set X:
If G does not act faithfully on X, one can easily modify the group to
obtain a faithful action. If we define N = {g in G : g·x = x for all x
in X}, then N is a normal subgroup of G; indeed, it is the kernel of the
homomorphism G → Sym(X). The factor group G/N acts faithfully on X by
setting (gN)·x = g·x. The original action of G on X is faithful if and
only if N = {e}.
So what I need, computationally, is not a map from G - G/N, but more
the other way round. More explicitly I want a (nice, simple, concise)
description of X (= orbit of G) in terms of elements of G. The cosets
will do that, but not really simpler than X itself. Provided I come up
with something sufficiently general, there will be a patch with a new
feature :-)
Thanks, again
--
Robert Schwarz m...@rschwarz.net
Get my public key at http://rschwarz.net/key.asc
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: Linear Programming and MIP... Let's start something huge !
). I hope many of you will be interested by LP and MIP in Sage and will be willing to work on it too ! I have my version of it, so I can wait without any problem, but SAGE --needs-- LP and MIP solvers ;-) Have fun ! Nathann -- Robert Schwarz m...@rschwarz.net Get my public key at http://rschwarz.net/key.asc --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: linear programming via lp_solve in sage
David Joyner wrote: The paper http://www.lehigh.edu/~tkr2/research/papers/MILP04.pdf provides a survey of non-commercial LP solvers. It appears that COIN-OR's Symphany package solves a wider class of problems by that (in one comparison at least) lp_solve is relatively fast. Do you agree? Can you offer other comparisons with Symphany? Sage currently ships only with cvxopt but, AFAIK, cvxopt does not handle MILPs. See also http://wiki.sagemath.org/optimization for plans to include solvers in Sage. I've just read a benchmark paper comparing lp_solve, glpk and Coin-Or's clp, the last always winning by 1 or 2 orders of magnitude in computation time, but it's from 2006, so maybe a bit dated. -- Robert Schwarz m...@rschwarz.net Get my public key at http://rschwarz.net/key.asc signature.asc Description: OpenPGP digital signature
[sage-devel] Re: book that uses sage
On page 4, under Background, it says: The reader [...] must have know the basics of groups, rings, [...] This is minor, but you'll sure be happy for every error fixed before the book's in print. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: book that uses sage
On page 4, under Background, it says: The reader [...] must have know the basics of groups [...], which seems to be a typo. It's not important at all, but I bet you'll be happy for every error fixed before the book's in print. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
