COIN-OR::LEMON - Graph Library

Changeset 1038:a2d142bb5d3c in lemon-main for doc/groups.dox

03/01/13 17:59:08 (8 years ago)
Alpar Juttner <alpar@…>
1030:4936be66d2f5 (diff), 1037:d3dcc49e6403 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Merge #386

2 edited


  • doc/groups.dox

    r1003 r1038  
    559559\image latex planar.eps "Plane graph" width=\textwidth
     563@defgroup tsp Traveling Salesman Problem
     564@ingroup algs
     565\brief Algorithms for the symmetric traveling salesman problem
     567This group contains basic heuristic algorithms for the the symmetric
     568\e traveling \e salesman \e problem (TSP).
     569Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
     570the problem is to find a shortest possible tour that visits each node exactly
     571once (i.e. the minimum cost Hamiltonian cycle).
     573These TSP algorithms are intended to be used with a \e metric \e cost
     574\e function, i.e. the edge costs should satisfy the triangle inequality.
     575Otherwise the algorithms could yield worse results.
     577LEMON provides five well-known heuristics for solving symmetric TSP:
     578 - \ref NearestNeighborTsp Neareast neighbor algorithm
     579 - \ref GreedyTsp Greedy algorithm
     580 - \ref InsertionTsp Insertion heuristic (with four selection methods)
     581 - \ref ChristofidesTsp Christofides algorithm
     582 - \ref Opt2Tsp 2-opt algorithm
     584\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
     585solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
     587\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
     588approximation factor: 3/2.
     590\ref Opt2Tsp usually provides the best results in practice, but
     591it is the slowest method. It can also be used to improve given tours,
     592for example, the results of other algorithms.
     594\image html tsp.png
     595\image latex tsp.eps "Traveling salesman problem" width=\textwidth
  • doc/groups.dox

    r1036 r1038  
    407407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    409 In general NetworkSimplex is the most efficient implementation,
    410 but in special cases other algorithms could be faster.
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     411\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
     412several thousands of nodes) and on dense graphs, while \ref CostScaling is
     413typically more efficient on large graphs (e.g. hundreds of thousands of
     414nodes or above), especially if they are sparse.
     415However, other algorithms could be faster in special cases.
    411416For example, if the total supply and/or capacities are rather small,
    412 CapacityScaling is usually the fastest algorithm (without effective scaling).
     417\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     419These classes are intended to be used with integer-valued input data
     420(capacities, supply values, and costs), except for \ref CapacityScaling,
     421which is capable of handling real-valued arc costs (other numerical
     422data are required to be integer).
    450460This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     461\ref amo93networkflows, \ref karp78characterization.
    453463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    466476LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     477- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
    469478- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     479  version of Karp's algorithm \ref hartmann93finding.
    471480- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
    474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     481  \ref dasdan98minmeancycle, \ref dasdan04experimental.
     483In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
    475484most efficient one, though the best known theoretical bound on its running
    476485time is exponential.
    542 @defgroup planar Planarity Embedding and Drawing
     551@defgroup planar Planar Embedding and Drawing
    543552@ingroup algs
    544553\brief Algorithms for planarity checking, embedding and drawing
Note: See TracChangeset for help on using the changeset viewer.