Class CapacityScalingMinimumCostFlow<V,E>
- Type Parameters:
V
- graph vertex typeE
- graph edge type
- All Implemented Interfaces:
FlowAlgorithm<V,
,E> MinimumCostFlowAlgorithm<V,
E>
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 via
MinimumCostFlowProblem
, 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 pseudo-polynomial 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 self-loops. 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 uses
COST_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 non-negative (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 pseudo-polynomial 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.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
Supporting data structure for theCapacityScalingMinimumCostFlow
.private static class
Supporting data structure for theCapacityScalingMinimumCostFlow
.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
FieldsModifier and TypeFieldDescriptionprivate CapacityScalingMinimumCostFlow.Arc[]
Array of internal arcs.static final int
A capacity which is considered to be infinite.static final double
A cost which is considered to be infinite.private int
Variable that is used to determine whether a vertex has been labeled temporarily or permanently during Dijkstra's algorithmprivate static final boolean
Debug variablestatic final int
Default scaling factorList of edges of the flow network.List of vertices of the flow network.private int
Number of edges in the networkComputed minimum cost flowprivate int
Number of vertices in the networkprivate CapacityScalingMinimumCostFlow.Node[]
Array of internal nodes used by the algorithm.private MinimumCostFlowProblem
<V, E> Specified minimum cost flow problemprivate final int
Scaling factor of this algorithm -
Constructor Summary
ConstructorsConstructorDescriptionConstructs 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
Modifier and TypeMethodDescriptionprivate void
Augments the path fromstart
to theend
sending as much flow as possible.private void
Calculated a solution to the specified minimum cost flow problem.finish()
Finishes the computation by checking the flow feasibility, computing arc flows, and creating an instance ofMinimumCostFlowAlgorithm.MinimumCostFlow
.Returns solution to the dual linear program formulated on the network.getFlowDirection
(E edge) For the specifiededge
$(u, v)$ returns vertex $v$ if the flow goes from $u$ to $v$, or returns vertex $u$ otherwise.Returns mapping from edge to flow value through this particular edgegetMinimumCostFlow
(MinimumCostFlowProblem<V, E> minimumCostFlowProblem) Calculates feasible flow of minimum cost for the minimum cost flow problem.private int
getU()
Returns the largest magnitude of any supply/demand or finite arc capacity.private void
init()
Converts the flow network in the form convenient for the algorithm.private void
pushAllFlow
(List<CapacityScalingMinimumCostFlow.Node> positiveExcessNodes, Set<CapacityScalingMinimumCostFlow.Node> negativeExcessNodes, int delta) For every node in thepositiveExcessNodes
pushes all flow away from it until its excess is less thandelta
.private void
pushDijkstra
(CapacityScalingMinimumCostFlow.Node start, Set<CapacityScalingMinimumCostFlow.Node> negativeExcessNodes, int delta) Runs the Dijkstra's algorithm in the residual network usingCapacityScalingMinimumCostFlow.Arc.getReducedCost()
as arc distances.scale
(int delta) Performs a scaling phase by saturating all negative reduced cost arcs with residual capacity greater than or equal to thedelta
, so that they don't belong to the $\Delta$-residual network and, hence, don't violate optimality conditions.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 Details
-
CAP_INF
public static final int CAP_INFA 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:
-
COST_INF
public static final double COST_INFA 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:
-
DEFAULT_SCALING_FACTOR
public static final int DEFAULT_SCALING_FACTORDefault scaling factor- See Also:
-
DEBUG
private static final boolean DEBUGDebug variable- See Also:
-
scalingFactor
private final int scalingFactorScaling factor of this algorithm -
n
private int nNumber of vertices in the network -
m
private int mNumber of edges in the network -
counter
private int counterVariable that is used to determine whether a vertex has been labeled temporarily or permanently during Dijkstra's algorithm -
problem
Specified minimum cost flow problem -
minimumCostFlow
Computed minimum cost flow -
nodes
Array of internal nodes used by the algorithm. Node: these nodes are stored in the same order as vertices of the specified flow network. This allows to determine quickly their counterparts in the network. -
arcs
Array of internal arcs. Note: these arcs are stored in the same order as edges of the specified flow network. This allows to determine quickly their counterparts in the network. -
graphVertices
List of vertices of the flow network. -
graphEdges
List of edges of the flow network.
-
-
Constructor Details
-
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 Details
-
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
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
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 non-saturated 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.
-
calculateMinimumCostFlow
private void calculateMinimumCostFlow()Calculated a solution to the specified minimum cost flow problem. If the scaling factor is greater than 1, performs scaling phases, otherwise uses simple capacity scaling algorithm. -
init
private void init()Converts the flow network in the form convenient for the algorithm. Validated the arc capacities and costs.Also, adds a dummy node to the network and arcs from every node to this dummy node, and from this dummy node to every other node. These added arcs have infinite capacities
CAP_INF
and infinite costsCOST_INF
. This ensures, that every search for an augmenting path to send at least $\Delta$ units of flow succeeds.If the flow network has a feasible solution, at the end there will be no flow on the added arcs. Otherwise, the specified problem has no feasible solution.
-
getU
private int getU()Returns the largest magnitude of any supply/demand or finite arc capacity.- Returns:
- the largest magnitude of any supply/demand or finite arc capacity.
-
scale
private Pair<List<CapacityScalingMinimumCostFlow.Node>,Set<CapacityScalingMinimumCostFlow.Node>> scale(int delta) Performs a scaling phase by saturating all negative reduced cost arcs with residual capacity greater than or equal to thedelta
, so that they don't belong to the $\Delta$-residual network and, hence, don't violate optimality conditions. After that this method computes and returns nodes with positive excess greater than or equal to thedelta
and nodes with negative excesses that are less than or equal todelta
- Parameters:
delta
- current value of $\Delta$- Returns:
- the nodes with excesses no less than
delta
and no greater than-delta
-
pushAllFlow
private void pushAllFlow(List<CapacityScalingMinimumCostFlow.Node> positiveExcessNodes, Set<CapacityScalingMinimumCostFlow.Node> negativeExcessNodes, int delta) For every node in thepositiveExcessNodes
pushes all flow away from it until its excess is less thandelta
. This is always possible due to the performed flow network reduction during the initialization phase.- Parameters:
positiveExcessNodes
- nodes from the network with positive excesses no less thandelta
negativeExcessNodes
- nodes from the network with negative excesses no greater thandelta
delta
- the current value of $\Delta$
-
pushDijkstra
private void pushDijkstra(CapacityScalingMinimumCostFlow.Node start, Set<CapacityScalingMinimumCostFlow.Node> negativeExcessNodes, int delta) Runs the Dijkstra's algorithm in the residual network usingCapacityScalingMinimumCostFlow.Arc.getReducedCost()
as arc distances.After reaching a node with excess no greater than
-delta
, augments it. Since the search is performed in the $\Delta$-residual network, the augmentation carries at leastdelta
units of flow. The search always succeeds due to the flow network reduction performed during the initialization phase.Updates the potentials of the nodes so that they:
- Satisfy optimality conditions in the $\Delta$-residual network
- The reduced cost of the augmented path is equal to $0$
Let us denote some permanently labeled vertex as $u$, and the first permanently labeled vertex with negative excess as $v$. Let $dist(x)$ be the distance function in the residual network. Then we use the following formula to update the node potentials: $v.potential = v.potential + dist(v) - dist(u)$. The potentials of the temporarily labeled and unvisited vertices stay unchanged.
- Parameters:
start
- the start node for Dijkstra's algorithmnegativeExcessNodes
- nodes from the network with negative excesses no greater thandelta
delta
- the current value of $\Delta$
-
augmentPath
private void augmentPath(CapacityScalingMinimumCostFlow.Node start, CapacityScalingMinimumCostFlow.Node end) Augments the path fromstart
to theend
sending as much flow as possible. UsesCapacityScalingMinimumCostFlow.Node.parentArc
computed by the Dijkstra's algorithm. Updates the excesses of thestart
and theend
nodes.- Parameters:
start
- the start of the augmenting pathend
- the end of the augmenting path
-
finish
Finishes the computation by checking the flow feasibility, computing arc flows, and creating an instance ofMinimumCostFlowAlgorithm.MinimumCostFlow
. The resulting flow mapping contains all edges of the specified minimum cost flow problem.- Returns:
- the solution to the minimum cost flow problem
-
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 non-saturated arc in the residual network is non-negative. 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.
-