{{Infobox Software
, logo =
, released = {{start date, 2004, 9, 30
, latest release version = 1.3.1
, latest release date = {{start date, 2014, 7, 7
, programming language = C++
, operating system =
Cross-platform
In computing, cross-platform software (also called multi-platform software, platform-agnostic software, or platform-independent software) is computer software that is designed to work in several computing platforms. Some cross-platform software r ...
Visual Studio
Visual Studio is an integrated development environment (IDE) from Microsoft. It is used to develop computer programs including web site, websites, web apps, web services and mobile apps. Visual Studio uses Microsoft software development platfor ...
Graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
and
Network Optimization
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
Library
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
, license =
Free software
Free software or libre software is computer software distributed under terms that allow users to run the software for any purpose as well as to study, change, and distribute it and any adapted versions. Free software is a matter of liberty, no ...
open source
Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
library
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
written in the
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
language providing implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks. The library is part of the
COIN-OR
Computational Infrastructure for Operations Research (COIN-OR), is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature (e.g., a research journal) provides the operat ...
project.
LEMON is an abbreviation of ''Library for Efficient Modeling and Optimization in Networks''.
Design
LEMON employs
genericity
Generic programming is a style of computer programming in which algorithms are written in terms of data type, types ''to-be-specified-later'' that are then ''instantiated'' when needed for specific types provided as parameter (computer programmi ...
in C++ by using
templates
Template may refer to:
Tools
* Die (manufacturing), used to cut or shape material
* Mold, in a molding process
* Stencil, a pattern or overlay used in graphic arts (drawing, painting, etc.) and sewing to replicate letters, shapes or designs
Co ...
. The tools of the library are designed to be versatile, convenient and highly efficient. They can be combined easily to solve complex real-life optimization problems. For example, LEMON’s graphs can differ in many ways (depending on the representation and other specialities), but all have to satisfy one or more graph concepts, which are standardized interfaces to work with the rest of the library.
Graph search algorithm
In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal ...
s
*
Shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
algorithms
*
Maximum flow
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
Minimum cut
In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric.
Variations of the minimum cut problem consider weighted graphs, directed graphs, term ...
algorithms
*
Connectivity
Connectivity may refer to:
Computing and technology
* Connectivity (media), the ability of the social media to accumulate economic capital from the users connections and activities
* Internet connectivity, the means by which individual terminals, ...
and other graph properties
* Maximum cardinality and minimum cost
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
s
* Auxiliary algorithms
LEMON also contains some
metaheuristic
In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...
optimization tools and provides a general high-level interface for several LP and MIP solvers, such as
GLPK
The GNU Linear Programming Kit (GLPK) is a software package intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the fo ...
, ILOG CPLEX, CLP, CBC, SoPlex.
LEMON has its own graph storing format, the so called ''Lemon Graph Format'' and includes general EPS drawing methods and special graph exporting tools.
LEMON also includes several miscellaneous tools. For example, it provides simple tools for measuring the performance of algorithms, which can be used to compare different implementations of the same problem.