Class CapacityScalingMinimumCostFlow<V,E>
 java.lang.Object

 org.jgrapht.alg.flow.mincost.CapacityScalingMinimumCostFlow<V,E>

 Type Parameters:
V
 graph vertex typeE
 graph edge type
 All Implemented Interfaces:
FlowAlgorithm<V,E>
,MinimumCostFlowAlgorithm<V,E>
public class CapacityScalingMinimumCostFlow<V,E> extends Object implements MinimumCostFlowAlgorithm<V,E>
This class computes a solution to a minimum cost flow problem using the successive shortest path algorithm with capacity scaling. More precisely, this class computes a bflow of minimum cost, i.e. for each node $v$ in the network the sum of all outgoing flows minus the sum of all incoming flows should be equal to the node supply $b_v$The minimum cost flow problem is defined as follows: \[ \begin{align} \mbox{minimize}~& \sum_{e\in \delta^+(s)}c_e\cdot f_e &\\ \mbox{s.t. }&\sum_{e\in \delta^(i)} f_e  \sum_{e\in \delta^+(i)} f_e = b_e & \forall i\in V\\ &l_e\leq f_e \leq u_e & \forall e\in E \end{align} \] Here $\delta^+(i)$ and $\delta^(i)$ denote the outgoing and incoming edges of vertex $i$ respectively. The parameters $c_{e}$ define a cost for each unit of flow on the arc $e$, $l_{e}$ define minimum arc flow and $u_{e}$ define maximum arc flow. If $u_{e}$ is equal to
CAP_INF
, then arbitrary large flow can be sent across the arc $e$. Parameters $b_{e}$ define the nodes demands: positive demand means that a node is a supply node, 0 demand means that it is a transhipment node, negative demand means that it is a demand node. Parameters $b_{e}$, $l_{e}$ and $u_{e}$ can be specified viaMinimumCostFlowProblem
, graph edge weights are considered to be parameters $c_{e}$, which can be negative.This algorithm supports two modes: with and without scaling. An integral scaling factor can be specified during construction time. If the specified scaling factor is less than 2, then the algorithm solves the specified problem using regular successive shortest path. The default scaling factor is
DEFAULT_SCALING_FACTOR
.Essentially, the capacity scaling technique is breaking down the solution of the problem into $O(\log U)$ phases $\left[\Delta_i, \Delta_{i +1}\right],\ \Delta_i = 2^{i}, i = 0, 1, \dots, \log_a(U)  1$. At each phase the algorithm carries at least $\delta_i$ units of flow. This technique ensures weakly polynomial time bound on the running time complexity of the algorithm. Smaller scaling factors guarantee smaller constant in the asymptotic time bound. The best choice of scaling factor is between $2$ and $16$, which depends on the characteristics of the flow network. Choosing $100$ as a scaling factor is almost equivalent to using the algorithm without scaling. In the case the algorithm is used without scaling, it has pseudopolynomial time complexity $\mathcal{O}(nU(m + n)\log n)$.
Currently the algorithm doesn't support undirected flow networks. The algorithm also imposes two constraints on the directed flow networks, namely, is doesn't support infinite capacity arcs with negative cost and selfloops. Note, that in the case the network contains an infinite capacity arc with negative cost, the cost of a flow on the network can be bounded from below by some constant, i.e. a feasible finite weight solution can exist.
An arc with capacity greater that or equal to
CAP_INF
is considered to be an infinite capacity arc. The algorithm also usesCOST_INF
during the computation, therefore, the magnitude of the cost of any arc can't exceed this values.In the capacity scaling mode, the algorithm performs $\mathcal{O}(log_a U)$ $\Delta$scaling phases, where $U$ is the largest magnitude of any supply/demand or finite arc capacity, and $a$ is a scaling factor, which is considered to be constant. During each $\Delta$scaling phase the algorithm first ensures that all arc with capacity with capacity greater than or equal to $\Delta$ satisfy optimality condition, i.e. its reduced cost must be nonnegative (saturated arcs don't belong to the residual network). After saturating all arcs in the $\Delta$residual network with negative reduced cost the sum of the excesses is bounded by $2\Delta(m + n)$. Since the algorithm ensures that each augmentation carries at least $\Delta$ units of flow, at most $\mathcal{O}(m)$ flow augmentations are performed during each scaling phase. Therefore, the overall running time of the algorithm with capacity scaling is $\mathcal{O}(m\log_a U(m + n)\log n)$, which is a weakly polynomial time bound.
If the algorithm is used without scaling, each flow augmentation carries at least $\mathcal{O}(1)$ flow units, therefore the overall time complexity if $\mathcal{O}(nU(m + n)\log n)$, which is a pseudopolynomial time bound.
For more information about the capacity scaling algorithm see: K. Ahuja, Ravindra & L. Magnanti, Thomas & Orlin, James. (1993). Network Flows. This implementation is based on the algorithm description presented in this book.
 Author:
 Timofey Chudakov
 See Also:
MinimumCostFlowProblem
,MinimumCostFlowAlgorithm


Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumCostFlowAlgorithm
MinimumCostFlowAlgorithm.MinimumCostFlow<E>, MinimumCostFlowAlgorithm.MinimumCostFlowImpl<E>


Field Summary
Fields Modifier and Type Field Description static int
CAP_INF
A capacity which is considered to be infinite.static double
COST_INF
A cost which is considered to be infinite.static int
DEFAULT_SCALING_FACTOR
Default scaling factor

Constructor Summary
Constructors Constructor Description CapacityScalingMinimumCostFlow()
Constructs a new instance of the algorithm which uses default scaling factor.CapacityScalingMinimumCostFlow(int scalingFactor)
Constructs a new instance of the algorithm with customscalingFactor
.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Map<V,Double>
getDualSolution()
Returns solution to the dual linear program formulated on the network.V
getFlowDirection(E edge)
For the specifiededge
$(u, v)$ returns vertex $v$ if the flow goes from $u$ to $v$, or returns vertex $u$ otherwise.Map<E,Double>
getFlowMap()
Returns mapping from edge to flow value through this particular edgeMinimumCostFlowAlgorithm.MinimumCostFlow<E>
getMinimumCostFlow(MinimumCostFlowProblem<V,E> minimumCostFlowProblem)
Calculates feasible flow of minimum cost for the minimum cost flow problem.boolean
testOptimality(double eps)
Tests the optimality conditions after a flow of minimum cost has been computed.
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
getFlow

Methods inherited from interface org.jgrapht.alg.interfaces.MinimumCostFlowAlgorithm
getFlowCost




Field Detail

CAP_INF
public static final int CAP_INF
A capacity which is considered to be infinite. Every arc, which has upper capacity greater that or equal to this value is considered to be an infinite capacity arc. See Also:
 Constant Field Values

COST_INF
public static final double COST_INF
A cost which is considered to be infinite. This value is used internally for flow network transformation. That is why arcs with cost magnitude greater than or equal to this value are not allowed. See Also:
 Constant Field Values

DEFAULT_SCALING_FACTOR
public static final int DEFAULT_SCALING_FACTOR
Default scaling factor See Also:
 Constant Field Values


Constructor Detail

CapacityScalingMinimumCostFlow
public CapacityScalingMinimumCostFlow()
Constructs a new instance of the algorithm which uses default scaling factor.

CapacityScalingMinimumCostFlow
public CapacityScalingMinimumCostFlow(int scalingFactor)
Constructs a new instance of the algorithm with customscalingFactor
. If thescalingFactor
is less than 2, the algorithm doesn't use scaling. Parameters:
scalingFactor
 custom scaling factor


Method Detail

getFlowMap
public Map<E,Double> getFlowMap()
Returns mapping from edge to flow value through this particular edge Specified by:
getFlowMap
in interfaceFlowAlgorithm<V,E>
 Returns:
 maximum flow mapping, or null if a MinimumCostFlowProblem has not yet been solved.

getFlowDirection
public V getFlowDirection(E edge)
For the specifiededge
$(u, v)$ returns vertex $v$ if the flow goes from $u$ to $v$, or returns vertex $u$ otherwise. For directed flow networks the result is always the head of the specified arc.Note: not all flow algorithms may support undirected graphs.
 Specified by:
getFlowDirection
in interfaceFlowAlgorithm<V,E>
 Parameters:
edge
 an edge from the specified flow network Returns:
 the direction of the flow on the
edge

getMinimumCostFlow
public MinimumCostFlowAlgorithm.MinimumCostFlow<E> getMinimumCostFlow(MinimumCostFlowProblem<V,E> minimumCostFlowProblem)
Calculates feasible flow of minimum cost for the minimum cost flow problem. Specified by:
getMinimumCostFlow
in interfaceMinimumCostFlowAlgorithm<V,E>
 Parameters:
minimumCostFlowProblem
 minimum cost flow problem Returns:
 minimum cost flow

getDualSolution
public Map<V,Double> getDualSolution()
Returns solution to the dual linear program formulated on the network. Serves as a certificate of optimality.It is represented as a mapping from graph nodes to their potentials (dual variables). Reduced cost of a arc $(a, b)$ is defined as $cost((a, b)) + potential(b)  potential(b)$. According to the reduced cost optimality conditions, a feasible solution to the minimum cost flow problem is optimal if and only if reduced cost of every nonsaturated arc is greater than or equal to $0$.
 Returns:
 solution to the dual linear program formulated on the network, or null if a MinimumCostFlowProblem has not yet been solved.

testOptimality
public boolean testOptimality(double eps)
Tests the optimality conditions after a flow of minimum cost has been computed.More precisely, tests, whether the reduced cost of every nonsaturated arc in the residual network is nonnegative. This validation is performed with precision of
eps
. If the solution doesn't meet this condition, returns, false.In general, this method should always return true unless the algorithm implementation has a bug.
 Parameters:
eps
 the precision to use Returns:
 true, if the computed solution is optimal, false otherwise.

