|
| | 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.
|
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
-
| 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. |
- 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< typename GR , typename V = int , typename C = V >
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.
template< typename GR , typename V = int , typename C = V >
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.
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
-
| k | The largest number of potentials to find. |
- Returns
- The number of the potentials found, zero if the problem has no optimal flow.