#9910: Longest path
----------------------------------------------+-----------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-4.6.2
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: Robert Miller, Minh Van Nguyen | Merged:
Work_issues: |
----------------------------------------------+-----------------------------
Comment(by ncohen):
Hello !
> Is the situation for paths instead of circuits much different?
The situation for directed graphs is not different at all : by just
replacing each undirected edge by two edges, on in each direction, you
transform one problem into the other. Besides, your algorithms shouldn't
make much more operations than necessary because of the transformation.
> Is a MILP algorithm better than listing all elementary paths by a
Johnson-like algorithm and finding the max lenght? Maybe MILP is better in
practice but is it in theory?
Let me first begin by saying that I can not *stand* complexity theory. I
mean -- I like the theory, some of its conjectures, it sometimes says
interesting things, and even though it is most of the times for bad
reasons (see *) it motivates people to do research on maths, which is
perfectly nice.
This being said, many recent results and directions of research in
complexity have forgotten practice a long time ago. They are still
interesting results, they are still analysis of what our modelling of
"what is an efficient algorith" is, (*) but there is a point where this
modelling is not representative of the reality anymore (at which point we
are expected to adapt our theory).
So in theory, no there are no differences between those two algorithms.
Well, perhaps there is one : it is very hard to analyse the runtime of a
specific linear program, especially when it makes use of many heuristics
hidden in the LP solvers (and CPLEX and GLPK may behave very differently
on the same instance, even though they are given the same formulations).
On the other hand, I suspect it should be possible to produce graphs for
which listing all the paths before finding one of maximum length (usually
you would need to enumerat them all to be sure you found the best one, but
if you happen to find a hamiltonian path at some point you needn't press
further) takes an exponential time.
Which means I can not prove the LP is faster than the complete
enumeration. Of course -- nothing more than that -- it is probably
possible to do it anyway, my ignorance hopefully being a personnal drama
:-D
To answer further, there is an heuristic added to the Longest Path method
in Sage. It works by randomly extending paths, for as long as possible,
with some other healthy rules to go back in the exploration if bad choices
have been made. It isn't the algorithm you mentionned, but it is a good
way to get an idea of their relative performances without having to
implement the actual enumeration.
Let me also add that if you were willing to implement this enumeration
(and then again, I of course have no proof LP is better. Especially when
we can put complexity analysis to death by saying -- "we are just
interested in practical instances", which can not be defined. That's
precisely where a simple programming trick can divide the running time by
100 even though Theory does not see the difference), using the NetworkX
implementation would be a very bad choice, considering it is written in
Python. I had to write an enumeration algorithm in Cython for the graph
methods subgraph_search*, and the Python version I had written previously
was just .... not working. I didn't say "slow", I said that the running
time of the SAME algorithm was comparatively so large that it wasn't even
worthy of being used for small instances. Yeah, there again they both have
the same asymptotic complexity. Python is extremely slow for complete
enumerations, so you really want to save running time by writing low-level
code as soon as possible :-)
In the end, one thing to remember : I have no way to prove one is better
than the other, but I suspect it is (LP is actually enumerating all the
solutions -- with many heuristics -- but it is able to say very early "I
do not need to search further in this direction, because reasons that have
no graph-theoretic meaning (the relaxed version of my LP) tell me there
will be no solution this way). LP are very nice because they are easy to
write, but it is very hard to know how efficient they are in practice. And
complete enumeration in Python is often a waste of time :-)
Note for myself : if I want to lead my war against complexity further, I
first need to study it much more :-)
Happy new year !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9910#comment:14>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
