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 [AMO93], [Dan63], [KO91]. This algorithm is a highly efficient specialized version of the linear programming simplex method directly for the minimum cost flow problem.
In general, NetworkSimplex is the fastest implementation available in LEMON for this 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.
- 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 number types must be signed and all input data 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.
|
| NetworkSimplex (const GR &graph, bool arc_mixing=false) |
| Constructor.
|
|
|
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.
|
|
|
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.
|
|
|
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 |
| 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).
|
|
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. However, another pivot rule can 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 the several best eligible arcs from the former candidate list and extends this list in every iteration.
|
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 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()
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);
ns.lowerMap(lower).upperMap(upper).costMap(cost)
.supplyMap(sup).run();
cost[e] += 100;
ns.costMap(cost).run();
ns.resetParams();
ns.upperMap(capacity).costMap(cost)
.supplyMap(sup).run();
- Returns
(*this)
- See Also
- reset(), run()
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()