Hello everybody !!!
As already mentionned [1], I would like to change a lot of things in
the way the MixedIntegerLinearProgram works today...
It was originally just a way to solve linear programs for Graphs, and
to distribute them easily over several solvers available (for the
moment GLPK, Coin and CPLEX). I have received several emails already
from people who would like to have this or that feature available from
a specific solver (sometimes only one of them can do the job), and it
sounds like working a bit more on this class would make interesting
new possibilities available :
* With #9853 [2] one can now iterate over all the integer solution
of a MILP using CPLEX
* With #9923 [3], one can solve the feedback arc set problem
through constraint generation (it means that the constraints are being
added "while" the LP is being solved. It is a good trick to solve
problems whose number of constraints is exponential -- in this case
the number of circuits in a graph)
Now, this means that this MILP class becomes unsuited to the new
directions it is taking. I know who to blame , but it means most of
this code will have to be rewritten. I don't expect the interface to
change, but I think it would be ***much*** better to mimic what has
been done in the graph class by Robert : a MixedIntegerLinearProgram
object should have a Cython backend, and a Cython backend should be
written for each solver (*) . This would mean there would be no need
to cache information inside of a MILP object while it is already
stored inside of the MILP C structure at the moment, and it also means
we could hope to use methods like add_constraint through C calls ==>
much more efficiently than through Python when we are willing to
exchange some coding time against computational speed.
At the end of this, I intend to see the MILP class easier to work on
(from the developper's point of view. I find it a bit messy myself for
the moment). I do not intend to change its interface, and I would like
to make constraint/variable generation available to the users, but at
Ithe very least easy to work with through Cython. Since I have been
writing this patch for feedback arc set, I have been keeping myself
from writing a method to compute the Fractional Chromatic index of a
graph, and I would like to write it after everything else has been
done (which means I will probably spend many night on it not to wait
for too long :-D)
So here are the changes I plan. If anybody's willing to
join/help/complain/slap me, I'd be glad to discuss it, as I have
always been looking at this class from the developper's point of view,
and can not really guess what other people may think
smart/stupid/criminal in this code. The down side is that, of course,
two long patches are changing the files I intend to work on, namely
the two I mentionned already, #9853 and #9923, and that I can not
really begin to work on them until they are reviewed, in case they may
have to be modified during the review. So, if anybody felt like
looking at some Cython code :-)
Thank youuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!!
Nathann
(*) I first intend to write such backends, and to have -- for some
time -- the mip.pyx class able to work both with and without backend
(a use_backend = False optional keyword in the Constructor), to
finally make it the default behaviour
[1]
http://groups.google.com/group/sage-devel/browse_thread/thread/78bbbee7d9080875
[2] http://trac.sagemath.org/sage_trac/ticket/9853
[3] http://trac.sagemath.org/sage_trac/ticket/9923
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
