CostScaling implements a cost scaling algorithm that performs push/augment and relabel operations for finding a minimum cost flow[amo93networkflows], [goldberg90approximation], [goldberg97efficient], [bunnagel98efficient]. 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 , 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.
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.
Warning
Both V and C must be signed number types.
All input data (capacities, supply values, and costs) must be integer.
This algorithm does not support negative costs for arcs having infinite upper bound.
Note
CostScaling provides three different internal methods, from which the most efficient one is used by default. For more information, see Method.
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 digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.
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.
Enumerator
PUSH
Local push operations are used, i.e. flow is moved only on one admissible arc at once.
AUGMENT
Augment operations are used, i.e. flow is moved on admissible paths from a node with excess to a node with deficit.
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.
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.
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.
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).
Implementation of the Cost Scaling algorithm for finding a minimum cost flow.
Definition cost_scaling.h:139
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
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
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 digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.
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.
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.
template<typename GR , typename V , typename C , typename TR >
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.
Constant for infinite upper bounds (capacities). It is std::numeric_limits<Value>::infinity() if available, std::numeric_limits<Value>::max() otherwise.
Generated on Mon Jul 25 2022 18:36:57 for My Project by 1.12.0