CostScaling
Declared in lemon/cost_scaling.h, in the group Minimum Cost Flow Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename V , typename C , typename TR >
class CostScaling Implementation of the Cost Scaling algorithm for finding a minimum cost flow.
CostScaling implements a cost scaling algorithm that performs push/augment and relabel operations for finding a minimum cost flow [1], [18], [19], [2]. It is a highly efficient primal-dual solution method, which can be viewed as the generalization of the preflow push-relabel algorithm for the maximum flow problem. It is a polynomial algorithm, its running time complexity is \(O(n^2m\log(nK))\), where K denotes the maximum arc cost.
In general, NetworkSimplex and CostScaling are the fastest implementations available in LEMON for solving this problem. (For more information, see the module page.)
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
CostScaling provides three different internal methods, from which the most efficient one is used by default. For more information, see Method.
Warning
Both
VandCmust 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: an excess, a deficit or a residual capacity within 10^6 units in the last place of the largest supply or finite bound is taken as zero, and a reduced cost within 10^6 units in the last place of the largest cost as nonnegative, so that rounding errors neither keep the algorithm sending round-off around for ever nor make a feasible problem infeasible; the scaling phases go on until epsilon is within the latter, which the optimal flow then meets.
- 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.TR – The traits class that defines various types used by the algorithm. By default, it is CostScalingDefaultTraits< GR , V , C >. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.
Parameters
The parameters of the algorithm can be specified using these functions.
-
template< typename LowerMap >
inline CostScaling & 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.
-
template< typename UpperMap >
inline CostScaling & 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).
-
template< typename CostMap >
inline CostScaling & 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
1on all arcs.
-
template< typename SupplyMap >
inline CostScaling & 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.
-
inline CostScaling & 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
kis assigned tos,-kis assigned totand all other nodes have zero supply value.- Parameters:
s – The source node.
t – The target node.
k – The required amount of flow from node
sto nodet(i.e. the supply ofsand the demand oft).
- Returns:
(*this)
Execution control
The algorithm can be executed using run().
-
inline ProblemType run( Method method = PARTIAL_AUGMENT , int factor = 16 )
Run the algorithm.
This function runs the algorithm. The paramters can be specified using functions lowerMap(), upperMap(), costMap(), supplyMap(), stSupply(). For example,
CostScaling< ListDigraph > cs( graph ); cs.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.
See also
See also
- Parameters:
method – The internal method that will be used in the algorithm. For more information, see Method.
factor – The cost scaling factor. It must be at least two.
- Returns:
INFEASIBLEif no feasible flow exists,OPTIMALif 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),UNBOUNDEDif 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, in the direction of the flow, which proves the problem unbounded since the last run() found it feasible, as in unboundedCycle(). It is found by the algorithm of Bellman and Ford on the arcs of infinite upper bound, and it 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 whose supply 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) \]with no arc of infinite upper bound out of \(N'\), which proves the problem infeasible since the last run() found it so. It is the set that the algorithm has at hand when it finds no feasible flow, at no further cost: the nodes above the level that the push-relabel algorithm of its starting flow leaves empty, together with the node it was lifting, from which no residual arc leaves; if that set does not prove it (in floating point, beyond the round-off), it is the set of largest violation, from a maximum flow, as in infeasibleCut(). It is empty if the last run() did not return INFEASIBLE, or if, in floating point, the inequality does not hold beyond the round-off.
-
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(), i.e., of the supply less what can leave the set, 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.
-
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.
-
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 CostScaling & 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()] that the last run() used (zero before the first one), 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 CostScaling & 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().
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,
CostScaling< ListDigraph > cs( graph ); // First run cs.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; cs.costMap( cost ).run(); // Run again from scratch using resetParams() // (the lower bounds will be set to zero on all arcs) cs.resetParams(); cs.upperMap( capacity ).costMap( cost ).supplyMap( sup ).run();
- Returns:
(*this)
-
inline CostScaling & 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().
It is useful for multiple run() calls. By default, 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
- 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,
It is useful if the total cost cannot be stored in thecs.totalCost< double >();
Costtype 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
Valuetype of the algorithm must be convertible to theValuetype 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
Costtype of the algorithm must be convertible to theValuetype 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.
-
enumerator INFEASIBLE
-
enum Method
Constants for selecting the internal method.
Enum type containing constants for selecting the internal method for the run() function.
CostScaling provides three internal methods that differ mainly in their base operations, which are used in conjunction with the relabel operation. By default, the so called Partial Augment-Relabel method is used, which turned out to be the most efficient and the most robust on various test inputs. However, the other methods can be selected using the run() function with the proper parameter.
Values:
-
enumerator PUSH
Local push operations are used, i.e. flow is moved only on one admissible arc at once.
-
enumerator AUGMENT
Augment operations are used, i.e. flow is moved on admissible paths from a node with excess to a node with deficit.
-
enumerator PARTIAL_AUGMENT
Partial augment operations are used, i.e. flow is moved on admissible paths started from a node with excess, but the lengths of these paths are limited. This method can be viewed as a combined version of the previous two operations.
-
enumerator PUSH
-
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()].
-
typedef TR::LargeCost LargeCost
The large cost type.
The large cost type used for internal computations. By default, it is
longlongif theCosttype is integer, otherwise it isdouble.
-
typedef TR Traits
The traits class of the algorithm.
Public Functions
Public Members
Protected Functions
-
inline CostScaling()
-
template< typename T >
struct SetLargeCost : public CostScaling< GR , V , C , SetLargeCostTraits< T > > Named parameter for setting
LargeCosttype.Named parameter for setting
LargeCosttype, which is used for internal computations in the algorithm.Costmust be convertible toLargeCost.Public Types
-
typedef CostScaling< GR , V , C , SetLargeCostTraits< T > > Create
-
typedef CostScaling< GR , V , C , SetLargeCostTraits< T > > Create