[Coin-announce] COIN-OR::LEMON 1.2 released

Alpár Jüttner alpar at cs.elte.hu
Fri Mar 19 04:51:43 EDT 2010

COIN-OR::LEMON 1.2 released

The LEMON development team announces COIN-OR::LEMON 1.2, the next major
release of the library. For the sources, binary packages and the
documentation please visit



LEMON is an open source C++ template library aimed at combinatorial
optimization tasks, especially those working with graphs and networks.
Its goal is to provide highly efficient, easy-to-use, and well
cooperating fundamental software components that help implementing
complex real-life optimization tasks. These components include graph
implementations and related data structures, fundamental graph and
network algorithms (such as graph search, shortest path, spanning tree
and network flow algorithms) and various auxiliary tools.

Both its design and the permissive licensing scheme target the
production/commercial use as well as research purposes.

Its supports a wide range of operating systems and compilers. Tested on
Linux, Windows, OSX and AIX systems and with the following compilers:
GCC, Intel C++, IBM xlC, Visual C++ 2005 and 2008.

LEMON is a member of the COIN-OR initiative, a collection of
operations research related open source projects.

What is new in LEMON 1.2

* New algorithms
   * Bellman-Ford algorithm (#51)
   * Minimum mean cycle algorithms (#179)
     * Karp, Hartman-Orlin and Howard algorithms
   * New minimum cost flow algorithms (#180)
     * Cost Scaling algorithms
     * Capacity Scaling algorithm
     * Cycle-Canceling algorithms
   * Planarity related algorithms (#62)
     * Planarity checking algorithm
     * Planar embedding algorithm
     * Schnyder's planar drawing algorithm
     * Coloring planar graphs with five or six colors
   * Fractional matching algorithms (#314)
* New data structures
   * StaticDigraph structure (#68)
   * Several new priority queue structures (#50, #301)
     * Fibonacci, Radix, Bucket, Pairing, Binomial
       D-ary and fourary heaps (#301)
   * Iterable map structures (#73)
* Other new tools and functionality
   * Map utility functions (#320)
   * Reserve functions are added to ListGraph and SmartGraph (#311)
   * A resize() function is added to HypercubeGraph (#311)
   * A count() function is added to CrossRefMap (#302)
   * Support for multiple targets in Suurballe using fullInit() (#181)
   * Traits class and named parameters for Suurballe (#323)
   * Separate reset() and resetParams() functions in NetworkSimplex
     to handle graph changes (#327)
   * tolerance() functions are added to HaoOrlin (#306)
* Implementation improvements
   * Improvements in weighted matching algorithms (#314)
     * Jumpstart initialization
   * ArcIt iteration is based on out-arc lists instead of in-arc lists
     in ListDigraph (#311)
   * Faster add row operation in CbcMip (#203)
   * Better implementation for split() in ListDigraph (#311)
   * ArgParser can also throw exception instead of exit(1) (#332)
* Miscellaneous
   * A simple interactive bootstrap script
   * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315,
     * BibTeX references in the doc (#184)
   * Optionally use valgrind when running tests
   * Also check ReferenceMapTag in concept checks (#312)
   * dimacs-solver uses long long type by default.
* Several bugfixes (compared to release 1.1):
   #295: Suppress MSVC warnings using pragmas
   ----: Various CMAKE related improvements
         * Remove duplications from doc/CMakeLists.txt
         * Rename documentation install folder from 'docs' to 'html'
         * Add tools/CMakeLists.txt to the tarball
         * Generate and install LEMONConfig.cmake
         * Change the label of the html project in Visual Studio
         * Fix the check for the 'long long' type
         * Put the version string into config.h
         * Minor CMake improvements
         * Set the version to 'hg-tip' if everything fails
   #311: Add missing 'explicit' keywords
   #302: Fix the implementation and doc of CrossRefMap
   #308: Remove duplicate list_graph.h entry from source list
   #307: Bugfix in Preflow and Circulation
   #305: Bugfix and extension in the rename script
   #312: Also check ReferenceMapTag in concept checks
   #250: Bugfix in pathSource() and pathTarget()
   #321: Use pathCopy(from,to) instead of copyPath(to,from)
   #322: Distribure LEMONConfig.cmake.in
   #330: Bug fix in map_extender.h
   #336: Fix the date field comment of graphToEps() output
   #323: Bug fix in Suurballe
   #335: Fix clear() function in ExtendFindEnum
   #337: Use void* as the LPX object pointer
   #317: Fix (and improve) error message in mip_test.cc
         Remove unnecessary OsiCbc dependency
   #356: Allow multiple executions of weighted matching algorithms 

More information about the Coin-announce mailing list