NEWS
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 1047 ddd3c0d3d9bf
parent 712 e652b6f9a29f
child 1005 ffc2d2559fc9
child 1281 c08d0f04c117
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     1 2010-03-19 Version 1.2 released
     2 
     3         This is major feature release
     4 
     5         * New algorithms
     6           * Bellman-Ford algorithm (#51)
     7           * Minimum mean cycle algorithms (#179)
     8             * Karp, Hartman-Orlin and Howard algorithms
     9           * New minimum cost flow algorithms (#180)
    10             * Cost Scaling algorithms
    11             * Capacity Scaling algorithm
    12             * Cycle-Canceling algorithms
    13           * Planarity related algorithms (#62)
    14             * Planarity checking algorithm
    15             * Planar embedding algorithm
    16             * Schnyder's planar drawing algorithm
    17             * Coloring planar graphs with five or six colors
    18           * Fractional matching algorithms (#314)
    19         * New data structures
    20           * StaticDigraph structure (#68)
    21           * Several new priority queue structures (#50, #301)
    22             * Fibonacci, Radix, Bucket, Pairing, Binomial
    23               D-ary and fourary heaps (#301)
    24           * Iterable map structures (#73)
    25         * Other new tools and functionality
    26           * Map utility functions (#320)
    27           * Reserve functions are added to ListGraph and SmartGraph (#311)
    28           * A resize() function is added to HypercubeGraph (#311)
    29           * A count() function is added to CrossRefMap (#302)
    30           * Support for multiple targets in Suurballe using fullInit() (#181)
    31           * Traits class and named parameters for Suurballe (#323)
    32           * Separate reset() and resetParams() functions in NetworkSimplex
    33             to handle graph changes (#327)
    34           * tolerance() functions are added to HaoOrlin (#306)
    35         * Implementation improvements
    36           * Improvements in weighted matching algorithms (#314)
    37             * Jumpstart initialization
    38           * ArcIt iteration is based on out-arc lists instead of in-arc lists
    39             in ListDigraph (#311)
    40           * Faster add row operation in CbcMip (#203)
    41           * Better implementation for split() in ListDigraph (#311)
    42           * ArgParser can also throw exception instead of exit(1) (#332)
    43         * Miscellaneous
    44           * A simple interactive bootstrap script
    45           * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
    46                 #316,#319)
    47             * BibTeX references in the doc (#184)
    48           * Optionally use valgrind when running tests
    49           * Also check ReferenceMapTag in concept checks (#312)
    50           * dimacs-solver uses long long type by default.
    51         * Several bugfixes (compared to release 1.1):
    52           #295: Suppress MSVC warnings using pragmas
    53           ----: Various CMAKE related improvements
    54                 * Remove duplications from doc/CMakeLists.txt
    55                 * Rename documentation install folder from 'docs' to 'html'
    56                 * Add tools/CMakeLists.txt to the tarball
    57                 * Generate and install LEMONConfig.cmake
    58                 * Change the label of the html project in Visual Studio
    59                 * Fix the check for the 'long long' type
    60                 * Put the version string into config.h
    61                 * Minor CMake improvements
    62                 * Set the version to 'hg-tip' if everything fails
    63           #311: Add missing 'explicit' keywords
    64           #302: Fix the implementation and doc of CrossRefMap
    65           #308: Remove duplicate list_graph.h entry from source list
    66           #307: Bugfix in Preflow and Circulation
    67           #305: Bugfix and extension in the rename script
    68           #312: Also check ReferenceMapTag in concept checks
    69           #250: Bugfix in pathSource() and pathTarget()
    70           #321: Use pathCopy(from,to) instead of copyPath(to,from)
    71           #322: Distribure LEMONConfig.cmake.in
    72           #330: Bug fix in map_extender.h
    73           #336: Fix the date field comment of graphToEps() output
    74           #323: Bug fix in Suurballe
    75           #335: Fix clear() function in ExtendFindEnum
    76           #337: Use void* as the LPX object pointer
    77           #317: Fix (and improve) error message in mip_test.cc
    78                 Remove unnecessary OsiCbc dependency
    79           #356: Allow multiple executions of weighted matching algorithms (#356)
    80 
    81 2009-05-13 Version 1.1 released
    82 
    83         This is the second stable release of the 1.x series. It
    84         features a better coverage of the tools available in the 0.x
    85         series, a thoroughly reworked LP/MIP interface plus various
    86         improvements in the existing tools.
    87 
    88         * Much improved M$ Windows support
    89           * Various improvements in the CMAKE build system
    90           * Compilation warnings are fixed/suppressed
    91         * Support IBM xlC compiler
    92         * New algorithms
    93           * Connectivity related algorithms (#61)
    94           * Euler walks (#65)
    95           * Preflow push-relabel max. flow algorithm (#176)
    96           * Circulation algorithm (push-relabel based) (#175)
    97           * Suurballe algorithm (#47)
    98           * Gomory-Hu algorithm (#66)
    99           * Hao-Orlin algorithm (#58)
   100           * Edmond's maximum cardinality and weighted matching algorithms
   101             in general graphs (#48,#265)
   102           * Minimum cost arborescence/branching (#60)
   103           * Network Simplex min. cost flow algorithm (#234)
   104         * New data structures
   105           * Full graph structure (#57)
   106           * Grid graph structure (#57)
   107           * Hypercube graph structure (#57)
   108           * Graph adaptors (#67)
   109           * ArcSet and EdgeSet classes (#67)
   110           * Elevator class (#174)
   111         * Other new tools
   112           * LP/MIP interface (#44)
   113             * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC
   114           * Reader for the Nauty file format (#55)
   115           * DIMACS readers (#167)
   116           * Radix sort algorithms (#72)
   117           * RangeIdMap and CrossRefMap (#160)
   118         * New command line tools
   119           * DIMACS to LGF converter (#182)
   120           * lgf-gen - a graph generator (#45)
   121           * DIMACS solver utility (#226)
   122         * Other code improvements
   123           * Lognormal distribution added to Random (#102)
   124           * Better (i.e. O(1) time) item counting in SmartGraph (#3)
   125           * The standard maps of graphs are guaranteed to be
   126             reference maps (#190)
   127         * Miscellaneous
   128           * Various doc improvements
   129           * Improved 0.x -> 1.x converter script
   130 
   131         * Several bugfixes (compared to release 1.0):
   132           #170: Bugfix SmartDigraph::split()
   133           #171: Bugfix in SmartGraph::restoreSnapshot()
   134           #172: Extended test cases for graphs and digraphs
   135           #173: Bugfix in Random
   136                 * operator()s always return a double now
   137                 * the faulty real<Num>(Num) and real<Num>(Num,Num)
   138                   have been removed
   139           #187: Remove DijkstraWidestPathOperationTraits
   140           #61:  Bugfix in DfsVisit
   141           #193: Bugfix in GraphReader::skipSection()
   142           #195: Bugfix in ConEdgeIt()
   143           #197: Bugfix in heap unionfind
   144                 * This bug affects Edmond's general matching algorithms
   145           #207: Fix 'make install' without 'make html' using CMAKE
   146           #208: Suppress or fix VS2008 compilation warnings
   147           ----: Update the LEMON icon
   148           ----: Enable the component-based installer
   149                 (in installers made by CPACK)
   150           ----: Set the proper version for CMAKE in the tarballs
   151                 (made by autotools)
   152           ----: Minor clarification in the LICENSE file
   153           ----: Add missing unistd.h include to time_measure.h
   154           #204: Compilation bug fixed in graph_to_eps.h with VS2005
   155           #214,#215: windows.h should never be included by LEMON headers
   156           #230: Build systems check the availability of 'long long' type
   157           #229: Default implementation of Tolerance<> is used for integer types
   158           #211,#212: Various fixes for compiling on AIX
   159           ----: Improvements in CMAKE config
   160                 - docs is installed in share/doc/
   161                 - detects newer versions of Ghostscript
   162           #239: Fix missing 'inline' specifier in time_measure.h
   163           #274,#280: Install lemon/config.h
   164           #275: Prefix macro names with LEMON_ in lemon/config.h
   165           ----: Small script for making the release tarballs added
   166           ----: Minor improvement in unify-sources.sh (a76f55d7d397)
   167 
   168 2009-03-27 LEMON joins to the COIN-OR initiative
   169 
   170         COIN-OR (Computational Infrastructure for Operations Research,
   171         http://www.coin-or.org) project is an initiative to spur the
   172         development of open-source software for the operations research
   173         community.
   174 
   175 2008-10-13 Version 1.0 released
   176 
   177         This is the first stable release of LEMON. Compared to the 0.x
   178         release series, it features a considerably smaller but more
   179         matured set of tools. The API has also completely revised and
   180         changed in several places.
   181 
   182         * The major name changes compared to the 0.x series (see the
   183           Migration Guide in the doc for more details)
   184           * Graph -> Digraph, UGraph -> Graph
   185           * Edge -> Arc, UEdge -> Edge
   186           * source(UEdge)/target(UEdge) -> u(Edge)/v(Edge)
   187         * Other improvements
   188           * Better documentation
   189           * Reviewed and cleaned up codebase
   190           * CMake based build system (along with the autotools based one)
   191         * Contents of the library (ported from 0.x)
   192           * Algorithms
   193             * breadth-first search (bfs.h)
   194             * depth-first search (dfs.h)
   195             * Dijkstra's algorithm (dijkstra.h)
   196             * Kruskal's algorithm (kruskal.h)
   197           * Data structures
   198             * graph data structures (list_graph.h, smart_graph.h)
   199             * path data structures (path.h)
   200             * binary heap data structure (bin_heap.h)
   201             * union-find data structures (unionfind.h)
   202             * miscellaneous property maps (maps.h)
   203             * two dimensional vector and bounding box (dim2.h)
   204           * Concepts
   205             * graph structure concepts (concepts/digraph.h, concepts/graph.h,
   206               concepts/graph_components.h)
   207             * concepts for other structures (concepts/heap.h, concepts/maps.h,
   208               concepts/path.h)
   209           * Tools
   210             * Mersenne twister random number generator (random.h)
   211             * tools for measuring cpu and wall clock time (time_measure.h)
   212             * tools for counting steps and events (counter.h)
   213             * tool for parsing command line arguments (arg_parser.h)
   214             * tool for visualizing graphs (graph_to_eps.h)
   215             * tools for reading and writing data in LEMON Graph Format
   216               (lgf_reader.h, lgf_writer.h)
   217             * tools to handle the anomalies of calculations with
   218               floating point numbers (tolerance.h)
   219             * tools to manage RGB colors (color.h)
   220           * Infrastructure
   221             * extended assertion handling (assert.h)
   222             * exception classes and error handling (error.h)
   223             * concept checking (concept_check.h)
   224             * commonly used mathematical constants (math.h)