NetworkSimplex

Declared in lemon/network_simplex.h, in the group Minimum Cost Flow Algorithms; the same class on the Doxygen site.

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

Implementation of the primal Network Simplex algorithm for finding a minimum cost flow.

NetworkSimplex implements the primal Network Simplex algorithm for finding a minimum cost flow [1], [9], [26]. 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.

Note

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

Warning

Both V and C must be signed number types.

Warning

With integer types all input data (capacities, supply values, and costs) must be integer. With floating-point types they need not be: the reduced costs and the flow left on the artificial arcs are compared against a tolerance of 10^6 units in the last place of the largest absolute value of the costs and of the supplies and the finite bounds, respectively, unless tolerances() sets them, so that rounding errors make neither a degenerate pivot for ever nor a feasible problem infeasible.

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.

Parameters

The parameters of the algorithm can be specified using these functions.

template< typename LowerMap >
inline NetworkSimplex & lowerMap( const LowerMap & map )

Set the lower bounds on the arcs.

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)

template< typename UpperMap >
inline NetworkSimplex & upperMap( const UpperMap & map )

Set the upper bounds (capacities) on the arcs.

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)

template< typename CostMap >
inline NetworkSimplex & costMap( const CostMap & map )

Set the costs of the arcs.

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)

template< typename SupplyMap >
inline NetworkSimplex & supplyMap( const SupplyMap & map )

Set the supply values of the nodes.

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.

See also

supplyType()

Parameters:

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

Returns:

(*this)

inline NetworkSimplex & stSupply( const Node & s , const Node & t , Value k )

Set single source and target nodes and a supply value.

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)

inline NetworkSimplex & supplyType( SupplyType supply_type )

Set the type of the supply constraints.

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)

Execution Control

The algorithm can be executed using run().

inline ProblemType run( PivotRule pivot_rule = BLOCK_SEARCH )

Run the algorithm.

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 problem is feasible and its objective function is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.

inline std::vector< Arc > unboundedCycle() const

The cycle that proves the problem unbounded.

This function gives a directed cycle of negative cost whose arcs have infinite upper bounds, which proves the problem unbounded since the last run() found it feasible: the flow may be increased along it without limit, and the cost decreases with it. The arcs are given in the direction of the flow. It is the cycle of the pivot that the algorithm cannot perform, i.e., the entering arc and the path of the tree of the basis between its two ends, unless that path goes through an artificial arc, in which case it is found by the algorithm of Bellman and Ford on the arcs of infinite upper bound.

The cycle is empty if the last run() did not return UNBOUNDED.

inline std::vector< Node > infeasibleCut() const

The set of nodes that proves the problem infeasible.

This function gives a set \(N'\) of nodes that proves the problem infeasible since the last run() found it so. With the GEQ supply type, the supply of \(N'\) exceeds what can leave it, i.e.,

\[ \sum_{u\in N'} sup(u) > \sum_{uv\in A, u\in N', v\notin N'} upper(uv) - \sum_{uv\in A, u\notin N', v\in N'} lower(uv) \]
and no arc out of \(N'\) has an infinite upper bound; with the LEQ supply type, the demand of \(N'\) exceeds what can enter it, i.e., the same holds with \(-sup\) in place of \(sup\) and every arc taken backwards. It is the side of the source of a minimum cut of the maximum flow problem that sends the supplies to the demands (Gale, 1957; Hoffman, 1960), and the inequality is checked on the given data before the set is given.

The set is empty if the last run() did not return INFEASIBLE, or if, in floating point, the inequality does not hold beyond the round-off.

Pre:

The data and the supply type must be those of the last run(): the set is computed and checked on them as they are when this function is called.

inline std::vector< std::vector< Node > > infeasibleCuts( int k ) const

The k sets of nodes that prove the problem infeasible best.

This function gives the k sets of nodes of largest violation of the inequality of infeasibleCut(), in the order of their violations, at most k and only those that prove the problem infeasible: Lawler’s partition by the nodes that a set contains or not, with a maximum flow for each part (Hamacher, Picard and Queyranne, 1984), i.e., at most n maximum flows for each set. They are empty if the last run() did not return INFEASIBLE.

Pre:

The data and the supply type must be those of the last run(): the sets are computed and checked on them as they are when this function is called.

inline std::vector< std::vector< Node > > disjointInfeasibleCuts() const

Disjoint sets of nodes that prove the problem infeasible.

This function gives sets of nodes that prove the problem infeasible as infeasibleCut() does and that are pairwise disjoint, with no arc between two of them: the weakly connected components of the set of infeasibleCut() whose violation is positive, in the order of their violations, which sum to at least the violation of that set. They are empty if the last run() did not return INFEASIBLE.

Pre:

The data and the supply type must be those of the last run(): the sets are computed and checked on them as they are when this function is called.

inline std::vector< std::vector< Arc > > unboundedCycles( int k ) const

Arc-disjoint cycles that prove the problem unbounded.

This function gives at most k directed cycles of negative cost whose arcs have infinite upper bounds, pairwise arc-disjoint, in the order of their mean costs: the cycles of minimum mean cost of the strongly connected components of those arcs, which one run of Howard’s algorithm gives together and are pairwise node-disjoint, the first being of minimum mean of all, then those of the arcs not yet taken, and so on while fewer than k are found. The cycle of minimum total cost would be NP-hard to find. They are empty if the last run() did not return UNBOUNDED.

inline NetworkSimplex & tolerances( Value flow , Cost cost )

Sets the tolerances on the flows and on the reduced costs.

An excess, a deficit or a residual capacity within the tolerance on the flows is taken as zero, and a reduced cost above the opposite of the tolerance on the costs as nonnegative. A negative value, the default, leaves the tolerance to the algorithm: zero for an exact type, and otherwise 10^6 units in the last place of the largest supply or finite bound and of the largest cost, respectively. With floating-point data, a tolerance of zero lets rounding errors keep the algorithm going for ever, as in LEMON 1.3.1.

Returns:

(*this)

inline FlowTolerance flowTolerance() const

The tolerance on the flows in use.

The one set by tolerances(), if any, and otherwise the one of the data [see tolerances()], as a Tolerance, whose epsilon is zero for an exact type.

inline CostTolerance costTolerance() const

The tolerance on the reduced costs in use.

As flowTolerance(), for the reduced costs.

inline NetworkSimplex & resetParams()

Reset all the parameters that have been given before.

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();

See also

reset(), run()

Returns:

(*this)

inline NetworkSimplex & reset()

Reset the internal data structures and all the parameters that have been given before.

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.

See also

resetParams(), run()

Returns:

(*this)

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 >
inline Number totalCost() const

Return the total cost of the found flow.

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.

Pre:

run() must be called before using this function.

inline Value flow( const Arc & a ) const

Return the flow on the given arc.

This function returns the flow on the given arc.

Pre:

run() must be called before using this function.

template< typename FlowMap >
inline void flowMap( FlowMap & map ) const

Copy the flow values (the primal solution) into the given map.

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.

Pre:

run() must be called before using this function.

inline Cost potential( const Node & n ) const

Return the potential (dual value) of the given node.

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

Pre:

run() must be called before using this function.

template< typename PotentialMap >
inline void potentialMap( PotentialMap & map ) const

Copy the potential values (the dual solution) into the given map.

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.

Pre:

run() must be called before using this function.

Public Types

enum ProblemType

Problem type constants for the run() function.

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

Values:

enumerator INFEASIBLE

The problem has no feasible solution (flow).

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

enumerator UNBOUNDED

The problem is feasible and its objective function is unbounded, i.e. there is a directed cycle having negative total cost and infinite upper bound.

enum SupplyType

Constants for selecting the type of the supply constraints.

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.

Values:

enumerator GEQ

This option means that there are “greater or equal” supply/demand constraints in the definition of the problem.

enumerator LEQ

This option means that there are “less or equal” supply/demand constraints in the definition of the problem.

enum PivotRule

Constants for selecting the pivot rule.

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.

Values:

enumerator FIRST_ELIGIBLE

The First Eligible pivot rule. The next eligible arc is selected in a wraparound fashion in every iteration.

enumerator BEST_ELIGIBLE

The Best Eligible pivot rule. The best eligible arc is selected in every iteration.

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

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

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

typedef V Value

The type of the flow amounts, capacity bounds and supply values.

typedef C Cost

The type of the arc costs.

typedef lemon::Tolerance< Value > FlowTolerance

The type of the tolerance on the flows [see flowTolerance()].

typedef lemon::Tolerance< Cost > CostTolerance

The type of the tolerance on the reduced costs [see costTolerance()].

Public Functions

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

Constructor.

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.

Public Members

const Value INF

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