Hell everybody !!!
I'm sorry to answer this late but I don't always read the sage-combinat
posts ^^;
Well, here's the thing if you did not work it out already :
With Sage's MILP support, you will be able to answer easily those two
questions :
Is there a subcollection of sets that partition your point set ?
What is the family that covers your point set and has the least possible
amount of points covered several times (with multiplicity)
You cannot really get all the answers right now, except it you really,
really want them are if you are not ashamed of the algorithmic implications
of what you want Sage to compute. Anyway, if you really want to do it don't
tell me, 'cause it hurts :-P
Here's the code :
from sage.numerical.mip import MIPSolverException
# Set collection
n = 15
S = [Subsets(range(n)).random_element() for i in range(30)]
# A Mixed Integer Linear Program object
p = MixedIntegerLinearProgram(maximization = False)
# You associate a binary variable b[s] to each of your set s
b = p.new_variable(binary = True)
# You want all points to be covered at least once (a covering of your
vertex set)
for i in range(n):
p.add_constraint( p.sum([b[s] for s in S if i in s]) = 1)
# You want to minimize the number of times each point is taken, with
multiplicity. Actually, you want to minimize the sum of the cardinalities
of the sets you take !
p.set_objective(p.sum([ len(s)*b[s] for s in S]))
# compute the solution
try:
p.solve()
print Here's the answer :
b_sol = p.get_values(b)
print [s for s in S if b_sol[s] == 1]
except MIPSolverException:
print No answer !
So once more, Sage cannot tell you right now all solutions as you may
want. I would like to, though. But...
If you rey want it, what you can do is the following :
Run the LP code above
Use the solution, do whatever you want to it
Add to the LP a constraint which excludes ONLY the solution you just
received
Solve the LP again, which will give you another solution.
Here's the kind of constraint I have in mind :
p.add_constraint( p.sum([(1-b[s] if b_sol[s] else b[s]) for s in S ]) = 1)
That is to say I want ANY of the values b_sol[s] to be different from what
they were just before.
Hope that helps. I don't want to know if this second trick helps, as I told
you it hurts me to think of what it does :-P
And for anything about the most practical aspects of LP, two pages whose
only purpose is to make it understandable :
http://steinertriples.fr/ncohen/tut/LP/
http://steinertriples.fr/ncohen/tut/LP_examples/
Have funnn !!!
Nathann
--
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.
