NetworkSimplex implements the primal Network Simplex algorithm for finding a minimum cost flow. This algorithm is a specialized version of the linear programming simplex method directly for the minimum cost flow problem. It is one of the most efficient solution methods.
In general this class is the fastest implementation available in LEMON for the minimum cost flow problem. Moreover it supports both directions of the supply/demand inequality constraints. For more information see SupplyType.
Most of the parameters of the problem (except for the digraph) can be given using separate functions, and the algorithm can be executed using the run() function. If some parameters are not specified, then default values will be used.
GR | The digraph type the algorithm runs on. |
V | The value type used for flow amounts, capacity bounds and supply values in the algorithm. By default it is int . |
C | The value type used for costs and potentials in the algorithm. By default it is the same as V . |
#include <lemon/network_simplex.h>
Public Types | |
enum | ProblemType { INFEASIBLE, OPTIMAL, UNBOUNDED } |
Problem type constants for the | |
enum | SupplyType { GEQ, LEQ } |
Constants for selecting the type of the supply constraints. More... | |
enum | PivotRule { FIRST_ELIGIBLE, BEST_ELIGIBLE, BLOCK_SEARCH, CANDIDATE_LIST, ALTERING_LIST } |
Constants for selecting the pivot rule. More... | |
typedef V | Value |
The type of the flow amounts, capacity bounds and supply values. | |
typedef C | Cost |
The type of the arc costs. | |
Public Member Functions | |
NetworkSimplex (const GR &graph) | |
Constructor. | |
Parameters | |
The parameters of the algorithm can be specified using these functions. | |
template<typename LowerMap > | |
NetworkSimplex & | lowerMap (const LowerMap &map) |
Set the lower bounds on the arcs. | |
template<typename UpperMap > | |
NetworkSimplex & | upperMap (const UpperMap &map) |
Set the upper bounds (capacities) on the arcs. | |
template<typename CostMap > | |
NetworkSimplex & | costMap (const CostMap &map) |
Set the costs of the arcs. | |
template<typename SupplyMap > | |
NetworkSimplex & | supplyMap (const SupplyMap &map) |
Set the supply values of the nodes. | |
NetworkSimplex & | stSupply (const Node &s, const Node &t, Value k) |
Set single source and target nodes and a supply value. | |
NetworkSimplex & | supplyType (SupplyType supply_type) |
Set the type of the supply constraints. | |
Execution Control | |
The algorithm can be executed using run(). | |
ProblemType | run (PivotRule pivot_rule=BLOCK_SEARCH) |
Run the algorithm. | |
NetworkSimplex & | reset () |
Reset all the parameters that have been given before. | |
Query Functions | |
The results of the algorithm can be obtained using these functions. | |
template<typename Number > | |
Number | totalCost () const |
Return the total cost of the found flow. | |
Value | flow (const Arc &a) const |
Return the flow on the given arc. | |
template<typename FlowMap > | |
void | flowMap (FlowMap &map) const |
Return the flow map (the primal solution). | |
Cost | potential (const Node &n) const |
Return the potential (dual value) of the given node. | |
template<typename PotentialMap > | |
void | potentialMap (PotentialMap &map) const |
Return the potential map (the dual solution). | |
Public Attributes | |
const Value | INF |
Constant for infinite upper bounds (capacities). |
enum ProblemType |
Enum type containing the problem type constants that can be returned by the run() function of the algorithm.
enum SupplyType |
Enum type containing constants for selecting the supply type, i.e. the direction of the inequalities in the supply/demand constraints of the minimum cost flow problem.
The default supply type is GEQ
, the LEQ
type can be selected using supplyType(). The equality form is a special case of both supply types.
enum PivotRule |
Enum type containing constants for selecting the pivot rule for the run() function.
NetworkSimplex provides five different pivot rule implementations that significantly affect the running time of the algorithm. By default Block Search is used, which proved to be the most efficient and the most robust on various test inputs according to our benchmark tests. However another pivot rule can be selected using the run() function with the proper parameter.
NetworkSimplex | ( | const GR & | graph | ) | [inline] |
The constructor of the class.
graph | The digraph the algorithm runs on. |
NetworkSimplex& lowerMap | ( | const LowerMap & | map | ) | [inline] |
This function sets the lower bounds on the arcs. If it is not used before calling run(), the lower bounds will be set to zero on all arcs.
map | An arc map storing the lower bounds. Its Value type must be convertible to the Value type of the algorithm. |
(*this)
NetworkSimplex& upperMap | ( | const UpperMap & | map | ) | [inline] |
This function sets the upper bounds (capacities) on the arcs. If it is not used before calling run(), the upper bounds will be set to INF on all arcs (i.e. the flow value will be unbounded from above on each arc).
map | An arc map storing the upper bounds. Its Value type must be convertible to the Value type of the algorithm. |
(*this)
NetworkSimplex& costMap | ( | const CostMap & | map | ) | [inline] |
This function sets the costs of the arcs. If it is not used before calling run(), the costs will be set to 1
on all arcs.
map | An arc map storing the costs. Its Value type must be convertible to the Cost type of the algorithm. |
(*this)
NetworkSimplex& supplyMap | ( | const SupplyMap & | map | ) | [inline] |
This function sets the supply values of the nodes. If neither this function nor stSupply() is used before calling run(), the supply of each node will be set to zero. (It makes sense only if non-zero lower bounds are given.)
map | A node map storing the supply values. Its Value type must be convertible to the Value type of the algorithm. |
(*this)
NetworkSimplex& stSupply | ( | const Node & | s, |
const Node & | t, | ||
Value | k | ||
) | [inline] |
This function sets a single source node and a single target node and the required flow value. If neither this function nor supplyMap() is used before calling run(), the supply of each node will be set to zero. (It makes sense only if non-zero lower bounds are given.)
Using this function has the same effect as using supplyMap() with such a map in which k
is assigned to s
, -k
is assigned to t
and all other nodes have zero supply value.
s | The source node. |
t | The target node. |
k | The required amount of flow from node s to node t (i.e. the supply of s and the demand of t ). |
(*this)
NetworkSimplex& supplyType | ( | SupplyType | supply_type | ) | [inline] |
This function sets the type of the supply/demand constraints. If it is not used before calling run(), the GEQ supply type will be used.
For more information see SupplyType.
(*this)
ProblemType run | ( | PivotRule | pivot_rule = BLOCK_SEARCH | ) | [inline] |
This function runs the algorithm. The paramters can be specified using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(), supplyType(). For example,
NetworkSimplex<ListDigraph> ns(graph); ns.lowerMap(lower).upperMap(upper).costMap(cost) .supplyMap(sup).run();
This function can be called more than once. All the parameters that have been given are kept for the next call, unless reset() is called, thus only the modified parameters have to be set again. See reset() for examples. However the underlying digraph must not be modified after this class have been constructed, since it copies and extends the graph.
pivot_rule | The pivot rule that will be used during the algorithm. For more information see PivotRule. |
INFEASIBLE
if no feasible flow exists, OPTIMAL
if the problem has optimal solution (i.e. it is feasible and bounded), and the algorithm has found optimal flow and node potentials (primal and dual solutions), UNBOUNDED
if the objective function of the problem is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.NetworkSimplex& reset | ( | ) | [inline] |
This function resets all the paramaters that have been given before using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(), supplyType().
It is useful for multiple run() calls. If this function is not used, all the parameters given before are kept for the next run() call. However the underlying digraph must not be modified after this class have been constructed, since it copies and extends the graph.
For example,
NetworkSimplex<ListDigraph> ns(graph); // First run ns.lowerMap(lower).upperMap(upper).costMap(cost) .supplyMap(sup).run(); // Run again with modified cost map (reset() is not called, // so only the cost map have to be set again) cost[e] += 100; ns.costMap(cost).run(); // Run again from scratch using reset() // (the lower bounds will be set to zero on all arcs) ns.reset(); ns.upperMap(capacity).costMap(cost) .supplyMap(sup).run();
(*this)
Number totalCost | ( | ) | const [inline] |
This function returns the total cost of the found flow. Its complexity is O(e).
ns.totalCost<double>();
Cost
type of the algorithm, which is the default return type of the function.Value flow | ( | const Arc & | a | ) | const [inline] |
This function returns the flow on the given arc.
void flowMap | ( | FlowMap & | map | ) | const [inline] |
This function copies the flow value on each arc into the given map. The Value
type of the algorithm must be convertible to the Value
type of the map.
Cost potential | ( | const Node & | n | ) | const [inline] |
This function returns the potential (dual value) of the given node.
void potentialMap | ( | PotentialMap & | map | ) | const [inline] |
This function copies the potential (dual value) of each node into the given map. The Cost
type of the algorithm must be convertible to the Value
type of the map.