Loading...
Searching...
No Matches
NetworkSimplex< GR, V, C > Class Template Reference
Algorithms » Minimum Cost Flow Algorithms

## Detailed Description

template<typename GR, typename V = int, typename C = V>
class lemon::NetworkSimplex< GR, V, C >

NetworkSimplex implements the primal Network Simplex algorithm for finding a minimum cost flow [amo93networkflows], [dantzig63linearprog], [kellyoneill91netsimplex]. This algorithm is a highly efficient specialized version of the linear programming simplex method directly for the minimum cost flow problem.

In general, NetworkSimplex and CostScaling are the fastest implementations available in LEMON for solving this problem. (For more information, see the module page.) Furthermore, this class 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.

Template Parameters

  GR | The digraph type the algorithm runs on.
  V | The number type used for flow amounts, capacity bounds and supply values in the algorithm. By default, it is `int`.
  C | The number type used for costs and potentials in the algorithm. By default, it is the same as `V`.

Warning
  Both `V` and `C` must be signed number types.
  All input data (capacities, supply values, and costs) must be integer.

Note
  NetworkSimplex provides five different pivot rule implementations, from which the most efficient one is used by default. For more information, see PivotRule.

`#include <lemon/network_simplex.h>`

## Public Types

enum | ProblemType { INFEASIBLE , OPTIMAL , UNBOUNDED }
| Problem type constants for the `run()` function. More...
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, bool arc_mixing=true)
| 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 & | resetParams ()
| Reset all the parameters that have been given before.
NetworkSimplex & | reset ()
| Reset the internal data structures and all the parameters that have been given before.
Query Functions
The results of the algorithm can be obtained using these functions. The run() function must be called before using them.
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
| Copy the flow values (the primal solution) into the given map.
Cost | potential (const Node &n) const
| Return the potential (dual value) of the given node.
template<typename PotentialMap>
void | potentialMap (PotentialMap &map) const
| Copy the potential values (the dual solution) into the given map.

## Public Attributes

const Value | INF
| Constant for infinite upper bounds (capacities).

## Member Enumeration Documentation

## ProblemType

template<typename GR, typename V = int, typename C = V>

enum ProblemType

Enum type containing the problem type constants that can be returned by the run() function of the algorithm.

Enumerator
INFEASIBLE | The problem has no feasible solution (flow).
OPTIMAL | 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 | The objective function of the problem is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.

## SupplyType

template<typename GR, typename V = int, typename C = V>

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.

Enumerator
GEQ | This option means that there are "greater or equal" supply/demand constraints in the definition of the problem.
LEQ | This option means that there are "less or equal" supply/demand constraints in the definition of the problem.

## PivotRule

template<typename GR, typename V = int, typename C = V>

enum PivotRule

Enum type containing constants for selecting the pivot rule for the run() function.

NetworkSimplex provides five different implementations for the pivot strategy that significantly affects the running time of the algorithm. According to experimental tests conducted on various problem instances, Block Search and Altering Candidate List rules turned out to be the most efficient. Since Block Search is a simpler strategy that seemed to be slightly more robust, it is used by default. However, another pivot rule can easily be selected using the run() function with the proper parameter.

Enumerator
FIRST_ELIGIBLE | The First Eligible pivot rule. The next eligible arc is selected in a wraparound fashion in every iteration.
BEST_ELIGIBLE | The Best Eligible pivot rule. The best eligible arc is selected in every iteration.
BLOCK_SEARCH | The Block Search pivot rule. A specified number of arcs are examined in every iteration in a wraparound fashion and the best eligible arc is selected from this block.
CANDIDATE_LIST | The Candidate List pivot rule. In a major iteration a candidate list is built from eligible arcs in a wraparound fashion and in the following minor iterations the best eligible arc is selected from this list.
ALTERING_LIST | The Altering Candidate List pivot rule. It is a modified version of the Candidate List method. It keeps only a few of the best eligible arcs from the former candidate list and extends this list in every iteration.

## Constructor & Destructor Documentation

## NetworkSimplex()

template<typename GR, typename V = int, typename C = V>

NetworkSimplex | ( | const GR & | graph,
|  | bool | arc_mixing = true )

inline

The constructor of the class.

Parameters

  graph | The digraph the algorithm runs on.
  arc_mixing | Indicate if the arcs will be stored in a mixed order in the internal data structure. In general, it leads to similar performance as using the original arc order, but it makes the algorithm more robust and in special cases, even significantly faster. Therefore, it is enabled by default.

## Member Function Documentation

## lowerMap()

template<typename GR, typename V = int, typename C = V>
template<typename LowerMap>

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.

Parameters

  map | An arc map storing the lower bounds. Its `Value` type must be convertible to the `Value` type of the algorithm.

Returns
  (*this)

## upperMap()

template<typename GR, typename V = int, typename C = V>
template<typename UpperMap>

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).

Parameters

  map | An arc map storing the upper bounds. Its `Value` type must be convertible to the `Value` type of the algorithm.

Returns
  (*this)

## costMap()

template<typename GR, typename V = int, typename C = V>
template<typename CostMap>

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.

Parameters

  map | An arc map storing the costs. Its `Value` type must be convertible to the `Cost` type of the algorithm.

Returns
  (*this)

## supplyMap()

template<typename GR, typename V = int, typename C = V>
template<typename SupplyMap>

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.

Parameters

  map | A node map storing the supply values. Its `Value` type must be convertible to the `Value` type of the algorithm.

Returns
  (*this)

See also
  supplyType()

## stSupply()

template<typename GR, typename V = int, typename C = V>

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.

Using this function has the same effect as using supplyMap() with a map in which `k` is assigned to `s`, `-k` is assigned to `t` and all other nodes have zero supply value.

Parameters

  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`).

Returns
  (*this)

## supplyType()

template<typename GR, typename V = int, typename C = V>

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.

Returns
  (*this)

## run()

template<typename GR, typename V = int, typename C = V>

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();
lemon::NetworkSimplex::NetworkSimplex
NetworkSimplex(const GR &graph, bool arc_mixing=true)
Constructor.
Definition network_simplex.h:649

This function can be called more than once. All the given parameters are kept for the next call, unless resetParams() or reset() is used, thus only the modified parameters have to be set again. If the underlying digraph was also modified after the construction of the class (or the last reset() call), then the reset() function must be called.

Parameters

  pivot_rule | The pivot rule that will be used during the algorithm. For more information, see PivotRule.

Returns
  `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.

See also
  ProblemType, PivotRule
  resetParams(), reset()

## resetParams()

template<typename GR, typename V = int, typename C = V>

NetworkSimplex & resetParams | ( |  | ) |

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. Basically, all the given parameters are kept for the next run() call, unless resetParams() or reset() is used. If the underlying digraph was also modified after the construction of the class or the last reset() call, then the reset() function must be used, otherwise resetParams() is sufficient.

For example,

NetworkSimplex<ListDigraph> ns(graph);
// First run
ns.lowerMap(lower).upperMap(upper).costMap(cost)
.supplyMap(sup).run();
// Run again with modified cost map (resetParams() 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 resetParams()
// (the lower bounds will be set to zero on all arcs)
ns.resetParams();
ns.upperMap(capacity).costMap(cost)
.supplyMap(sup).run();

Returns
  (*this)

See also
  reset(), run()

## reset()

template<typename GR, typename V = int, typename C = V>

NetworkSimplex & reset | ( |  | ) |

inline

This function resets the internal data structures and all the paramaters that have been given before using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(), supplyType().

It is useful for multiple run() calls. Basically, all the given parameters are kept for the next run() call, unless resetParams() or reset() is used. If the underlying digraph was also modified after the construction of the class or the last reset() call, then the reset() function must be used, otherwise resetParams() is sufficient.

See resetParams() for examples.

Returns
  (*this)

See also
  resetParams(), run()

## totalCost()

template<typename GR, typename V = int, typename C = V>
template<typename Number>

Number totalCost | ( |  | ) | const

inline

This function returns the total cost of the found flow. Its complexity is O(m).

Note
  The return type of the function can be specified as a template parameter. For example,
  ns.totalCost<double>();
  It is useful if the total cost cannot be stored in the `Cost` type of the algorithm, which is the default return type of the function.

Precondition
  run() must be called before using this function.

## flow()

template<typename GR, typename V = int, typename C = V>

Value flow | ( | const Arc & | a | ) | const

inline

This function returns the flow on the given arc.

Precondition
  run() must be called before using this function.

## flowMap()

template<typename GR, typename V = int, typename C = V>
template<typename FlowMap>

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.

Precondition
  run() must be called before using this function.

## potential()

template<typename GR, typename V = int, typename C = V>

Cost potential | ( | const Node & | n | ) | const

inline

This function returns the potential (dual value) of the given node.

Precondition
  run() must be called before using this function.

## potentialMap()

template<typename GR, typename V = int, typename C = V>
template<typename PotentialMap>

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.

Precondition
  run() must be called before using this function.

## Member Data Documentation

## INF

template<typename GR, typename V = int, typename C = V>

const Value INF

Constant for infinite upper bounds (capacities). It is `std::numeric_limits<Value>::infinity()` if available, `std::numeric_limits<Value>::max()` otherwise.