KBestExtremeFlows
Declared in lemon/k_best_extreme_flows.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 KBestExtremeFlows The K best extreme flows of a minimum cost flow problem.
This class finds the K vertices of least cost of the polyhedron of the flows of a minimum cost flow problem with the
GEQsupply constraints, in the order of their costs: first an optimal vertex, then the other optimal ones, if any, then those whose cost exceeds the optimal one by at most a given gap. These are the flows that a Lagrangian or a Benders’ decomposition wants several of, since each gives a different (sub)gradient, while a flow inside a face gives a convex combination of those of its vertices.The algorithm is the ranking of the vertices of Murty [30], in which the next vertex is adjacent to one of those already given, i.e., one pivot of the network simplex away from one of their bases, along the cycle that a nonbasic arc closes with the tree of the basis, saturated. The candidates are kept in a queue by their costs, and the bases of a degenerate vertex, which the pivots along a cycle of zero amount reach, are all expanded. The first vertex is the optimal flow that NetworkSimplex finds, or one given by initFlow(), brought to a vertex first, if it is not one, by saturating the cycles of the arcs strictly within their bounds, whose costs are zero at an optimal flow.
On the dual side, runPotentials() gives distinct optimal potentials, the vertices of the dual polyhedron of the trees of the shortest paths of the reduced costs from and to each node.
Note
The number of the bases of a degenerate vertex can be large, and all of them are visited when the vertex is expanded; each pivot takes \(O(n)\) time, and each basis \(O(nm)\) for all its pivots. A candidate pivot waits in the queue as its cost alone, the basis it leads to being made when it is taken, so that the memory is \(O(n+m)\) for each basis expanded, and their number is bounded by basisLimit().
- Template Parameters:
GR – The digraph type the algorithm runs on.
V – The number type of the flow amounts, of the bounds and of the supplies; by default,
int.C – The number type of the costs; by default, the same as
V.
Public Types
-
enum Method
The ways the flows are generated [see method()].
Values:
-
enumerator RANKING
The ranking of Murty: the k best vertices, in order.
-
enumerator CYCLES
The cycles of least reduced cost: the optimal vertices that the cycles of zero reduced cost lead to, then the vertices one cycle away from them, in the order of their costs.
-
enumerator RANKING
-
enum PotentialMethod
The ways the optimal potentials are generated [see potentialMethod()].
Values:
-
enumerator PATHS
The trees of the shortest paths from and to each node.
-
enumerator PIVOTS
The pivots of the dual simplex from the optimal vertex.
-
enumerator PATHS
Public Functions
-
inline explicit KBestExtremeFlows( const GR & graph )
Constructor.
The bounds are 0 and infinite, the costs 1 and the supplies 0 until they are given.
-
template< typename LowerMap >
inline KBestExtremeFlows & lowerMap( const LowerMap & map ) Sets the lower bounds of the arcs.
-
template< typename UpperMap >
inline KBestExtremeFlows & upperMap( const UpperMap & map ) Sets the upper bounds of the arcs.
An upper bound that is infinite or the largest value of
Valuemeans no bound.
-
template< typename CostMap >
inline KBestExtremeFlows & costMap( const CostMap & map ) Sets the costs of the arcs.
-
template< typename SupplyMap >
inline KBestExtremeFlows & supplyMap( const SupplyMap & map ) Sets the supplies of the nodes (negative for the demands).
-
template< typename FlowMap >
inline KBestExtremeFlows & initFlow( const FlowMap & map ) Gives the optimal flow to start from.
The flow must be optimal for the data given, not necessarily a vertex; then no algorithm of minimum cost flow is run.
-
inline KBestExtremeFlows & tolerances( Value flow , Cost cost )
Sets the tolerances on the flows and on the reduced costs.
Those of the minimum cost flow algorithms [see NetworkSimplex::tolerances()], given to the NetworkSimplex that finds the optimal flow and used in the comparisons of this class; a negative value, the default, leaves the tolerance to the data.
- Returns:
(*this)
-
inline Tolerance< Value > flowTolerance() const
The tolerance on the flows in use, as a Tolerance.
The one set by tolerances(), if any, and otherwise the one of the data, whose epsilon is zero for an exact type.
-
inline Tolerance< Cost > costTolerance() const
The tolerance on the reduced costs in use, as a Tolerance.
As flowTolerance(), for the reduced costs.
-
inline KBestExtremeFlows & method( Method m )
Sets the way the flows are generated.
With RANKING, the default, a run() gives the k best vertices in order, as long as the limits on the bases allow it [see basisLimit() and vertexBasisLimit()]. With CYCLES it enumerates no basis: from the optimal vertex and potentials optimal for it, the cycles of the residual graph whose arcs have a reduced cost of zero, saturated and made vertices, are the other optimal vertices, from which the same is done again; then, from each optimal vertex and for each arc at one of its bounds, the cycle of least reduced cost through the arc, saturated and made a vertex, the cost not growing, gives a vertex of larger cost; those of the cycles of least reduced cost are kept, and given in the order of their costs. Only the arcs at a bound are tried, since the free arcs of a vertex make no cycle, and in the order of their reduced costs, which bound from below those of their cycles, until one reaches that of the last cycle kept; one Dijkstra’s algorithm is made from the head of each arc tried. The flows are distinct vertices in the order of their costs, the optimal ones first, but those of larger cost are only some of the vertices one cycle away from an optimal one [see exact()]; each optimal vertex costs at most \(O( m^2\log n )\) time, one search of \(O( m\log n )\) for each arc at a bound, and \(O(km + pn)\) memory for the p trees of the shortest paths made.
-
inline int run( int k , Cost gap = -1 )
Finds the k best extreme flows.
- Parameters:
k – The largest number of flows to find.
gap – The largest excess of the cost of a flow over the optimal one; a negative one, the default, sets no limit.
- Returns:
The number of the flows found, which is less than
kif the problem has fewer vertices within the gap, and zero if it has no optimal flow (it is infeasible or unbounded).
-
inline KBestExtremeFlows & basisLimit( int limit )
Sets the largest number of bases a run() expands.
A degenerate vertex has many bases, and the ranking expands all of those it meets, each taking \(O(n+m)\) memory and \(O(n(n+m))\) time; when the limit is reached the run stops, the flows it gives are still distinct vertices in the order of their costs, but they may not be the k best ones [see exact()]. By default, 1000.
-
inline KBestExtremeFlows & vertexBasisLimit( int limit )
Sets the largest number of bases of one vertex a run() expands.
At a degenerate vertex the pivots of zero amount lead to its other bases, and a vertex of a problem as a shortest path, a path whose other basic arcs carry no flow, has as many bases as there are trees containing it; the next vertex is adjacent to a basis of one of those given, but expanding them all may take the whole basisLimit(). With a positive limit, a basis counting only if one of its pivots leads to another vertex, the bases of a vertex beyond it are not expanded and the degenerate pivots of its last one are not taken: the flows given are distinct vertices in the order of their costs, the first one optimal, adjacent to the bases expanded, but they may not be the k best ones [see exact()]. By default, no limit.
-
inline bool exact() const
Whether the last run() is exact.
Always false with CYCLES [see method()]; with RANKING, false if the last run() stopped at the limit of the bases [see basisLimit()] or left out a basis or a pivot for the limit of the bases of a vertex [see vertexBasisLimit()], so that the flows it gives may not be the k best ones.
-
inline Value flow( int i , const Arc & a ) const
The flow on an arc in the i-th flow, the first being 0.
-
template< typename FlowMap >
inline void flowMap( int i , FlowMap & map ) const Copies the i-th flow, the first being 0, into a map.
-
inline KBestExtremeFlows & potentialMethod( PotentialMethod m )
Sets the way the optimal potentials are generated.
With PATHS, the default, runPotentials() gives the vertices of the trees of the shortest paths, from and to each node, of the reduced costs of the residual graph of the optimal flow. With PIVOTS it gives the vertices of the polyhedron of the optimal potentials reached from that of the optimal vertex by the pivots of the dual simplex, breadth first: in a tree of arcs of zero reduced cost, an arc whose opposite residual arc is closed (an arc at a bound, i.e., a degenerate one of the primal) leaves, the side of its tail is raised until an arc into it reaches a zero reduced cost and enters, and the potentials change if the step is not zero; each vertex costs \(O(nm)\) time.
-
inline int runPotentials( int k )
Finds k distinct optimal potentials.
The potentials (dual solutions) optimal for the problem, i.e., those under which the reduced cost of every residual arc of an optimal flow is nonnegative: from potentials \(\pi\) optimal for the optimal vertex [see run()], \(\pi + d_s\) and \(\pi - d'_s\) for each node \(s\) in turn, where \(d_s\) are the distances from \(s\) and \(d'_s\) those to \(s\) in the residual graph of the flow on the reduced costs (one Dijkstra’s algorithm each), the nodes that are not reached taking the largest distance. Each is optimal, and it is the vertex of the dual polyhedron given by the tree of the shortest paths, of zero reduced costs, when that tree reaches every node; potentials that differ by a constant are the same.
With PIVOTS [see potentialMethod()] they are instead the vertices reached by the pivots of the dual simplex.
- Parameters:
k – The largest number of potentials to find.
- Returns:
The number of the potentials found, zero if the problem has no optimal flow.
-
inline int potentialNum() const
The number of the potentials found by the last runPotentials().