abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
KBestExtremeFlows< GR , V , C > Class Template Reference

The K best extreme flows of a minimum cost flow problem. More...

#include <lemon/k_best_extreme_flows.h>

Public Types

enum  Method { RANKING , CYCLES }
 The ways the flows are generated [see method()]. More...
enum  PotentialMethod { PATHS , PIVOTS }
 The ways the optimal potentials are generated [see potentialMethod()]. More...
typedef GR Digraph
 The type of the digraph.
typedef V Value
 The type of the flow amounts, of the bounds and of the supplies.
typedef C Cost
 The type of the costs.

Public Member Functions

 KBestExtremeFlows (const GR &graph)
 Constructor.
template< typename LowerMap >
KBestExtremeFlows & lowerMap (const LowerMap &map)
 Sets the lower bounds of the arcs.
template< typename UpperMap >
KBestExtremeFlows & upperMap (const UpperMap &map)
 Sets the upper bounds of the arcs.
template< typename CostMap >
KBestExtremeFlows & costMap (const CostMap &map)
 Sets the costs of the arcs.
template< typename SupplyMap >
KBestExtremeFlows & supplyMap (const SupplyMap &map)
 Sets the supplies of the nodes (negative for the demands).
template< typename FlowMap >
KBestExtremeFlows & initFlow (const FlowMap &map)
 Gives the optimal flow to start from.
KBestExtremeFlows & tolerances (Value flow, Cost cost)
 Sets the tolerances on the flows and on the reduced costs.
Tolerance< Value > flowTolerance () const
 The tolerance on the flows in use, as a Tolerance.
Tolerance< Cost > costTolerance () const
 The tolerance on the reduced costs in use, as a Tolerance.
KBestExtremeFlows & method (Method m)
 Sets the way the flows are generated.
int run (int k, Cost gap=-1)
 Finds the k best extreme flows.
KBestExtremeFlows & basisLimit (int limit)
 Sets the largest number of bases a run() expands.
KBestExtremeFlows & vertexBasisLimit (int limit)
 Sets the largest number of bases of one vertex a run() expands.
bool exact () const
 Whether the last run() is exact.
int flowNum () const
 The number of the flows found by the last run().
Cost totalCost (int i) const
 The total cost of the i-th flow, the first being 0.
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 >
void flowMap (int i, FlowMap &map) const
 Copies the i-th flow, the first being 0, into a map.
KBestExtremeFlows & potentialMethod (PotentialMethod m)
 Sets the way the optimal potentials are generated.
int runPotentials (int k)
 Finds k distinct optimal potentials.
int potentialNum () const
 The number of the potentials found by the last runPotentials().
Cost potential (int i, const Node &u) const
 The potential of a node in the i-th potentials, the first being 0.

Detailed Description

template< typename GR , typename V = int , typename C = V >
class lemon::KBestExtremeFlows< GR , V , C >

This class finds the K vertices of least cost of the polyhedron of the flows of a minimum cost flow problem with the GEQ supply 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.

Template Parameters
GRThe digraph type the algorithm runs on.
VThe number type of the flow amounts, of the bounds and of the supplies; by default, int.
CThe number type of the costs; by default, the same as V.
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().

Member Enumeration Documentation

◆ Method

template< typename GR , typename V = int , typename C = V >
enum Method
Enumerator
RANKING 

The ranking of Murty: the k best vertices, in order.

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.

◆ PotentialMethod

template< typename GR , typename V = int , typename C = V >
enum PotentialMethod
Enumerator
PATHS 

The trees of the shortest paths from and to each node.

PIVOTS 

The pivots of the dual simplex from the optimal vertex.

Constructor & Destructor Documentation

◆ KBestExtremeFlows()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows ( const GR & graph)
inlineexplicit

The bounds are 0 and infinite, the costs 1 and the supplies 0 until they are given.

Member Function Documentation

◆ upperMap()

template< typename GR , typename V = int , typename C = V >
template< typename UpperMap >
KBestExtremeFlows & upperMap ( const UpperMap & map)
inline

An upper bound that is infinite or the largest value of Value means no bound.

◆ initFlow()

template< typename GR , typename V = int , typename C = V >
template< typename FlowMap >
KBestExtremeFlows & initFlow ( const FlowMap & map)
inline

The flow must be optimal for the data given, not necessarily a vertex; then no algorithm of minimum cost flow is run.

◆ tolerances()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows & tolerances ( Value flow,
Cost cost )
inline

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 )

◆ flowTolerance()

template< typename GR , typename V = int , typename C = V >
Tolerance< Value > flowTolerance ( ) const
inline

The one set by tolerances(), if any, and otherwise the one of the data, whose epsilon is zero for an exact type.

◆ costTolerance()

template< typename GR , typename V = int , typename C = V >
Tolerance< Cost > costTolerance ( ) const
inline

As flowTolerance(), for the reduced costs.

◆ method()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows & method ( Method m)
inline

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.

◆ run()

template< typename GR , typename V = int , typename C = V >
int run ( int k,
Cost gap = -1 )
inline
Parameters
kThe largest number of flows to find.
gapThe 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 k if the problem has fewer vertices within the gap, and zero if it has no optimal flow (it is infeasible or unbounded).

◆ basisLimit()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows & basisLimit ( int limit)
inline

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.

◆ vertexBasisLimit()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows & vertexBasisLimit ( int limit)
inline

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.

◆ exact()

template< typename GR , typename V = int , typename C = V >
bool exact ( ) const
inline

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.

◆ potentialMethod()

template< typename GR , typename V = int , typename C = V >
KBestExtremeFlows & potentialMethod ( PotentialMethod m)
inline

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.

◆ runPotentials()

template< typename GR , typename V = int , typename C = V >
int runPotentials ( int k)
inline

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
kThe largest number of potentials to find.
Returns
The number of the potentials found, zero if the problem has no optimal flow.