- Generated by
1.9.7
|
The MCFClass Project
|
Linear Min Cost Flow problems solver, based on the RELAXIV code by D. More...
#include "MCFClass.h"Classes | |
| class | RelaxIV |
| The RelaxIV class derives from the abstract base class MCFClass, thus sharing its (standard) interface, and implements a Relaxation algorithm for solving (Linear) Min Cost Flow problems. More... | |
Namespaces | |
| namespace | MCFClass_di_unipi_it |
| The namespace MCFClass_di_unipi_it is defined to hold the MCFClass class and all the relative stuff. | |
Macros | |
| #define | DYNMC_MCF_RIV 3 |
| Decides if the graph topology (arcs, nodes) can be changed. | |
| #define | AUCTION 0 |
| Decides if the auction/shortest paths inizialization procedure is used. | |
| #define | RELAXIV_STATISTICS 0 |
| If RELAXIV_STATISTICS > 0, then statistic information about the behaviour of the Relaxation algorithm is computed. | |
Linear Min Cost Flow problems solver, based on the RELAXIV code by D.
Bertsekas and P. Tseng, as described in
Bertsekas, Dimitri P., and Paul Tseng. "RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems." (1994), Report LIDS-P-2276, MIT.
Conforms to the standard (MCF) interface defined in MCFClass.h.
RelaxIV is based on a primal-dual algorithm which essentially operates as follows: a pseudoflow (a flow vector which satisfies bound and non-negativity constraints but not necessarily flow conservation constraints) is kept which satisfies complementarity slackness conditions with the current vector of potentials; that is, only the flow on arcs whose reduced cost
\[ RC[ i , j ] = C[ i , j ] - Pi[ j ] + Pi[ i ] \]
is zero can be chosen to any value between 0 and the capacity, while arcs with reduced cost < 0 are saturated (fixed to their capacity) and arcs with reduced cost > 0 are empty (fixed to 0).
The algorithm attempts to convert the pseudoflow into a flow (i.e., to satisfy the flow conservation constraints) by essentially running a max-flow algorithm of the augmenting path type. If the flow is found then this is an optimal solution of the problem and the algorithm is stopped. Otherwise, a saturated cut is identified which separates the origins (nodes not yet producing enough flow) to the destinations (nodes not yet consuming enough flow); this cut is used to modify the potentials, thereby creating new arcs with zero reduced cost, which can be used to push further flow from the origins to the destinations. If no such arcs can be created the problem is declared unfeasible. Much care is devoted to stop the max-flow computation as soon as a proof that the set of potentials is not optimal, in order to reach as soon as possible a dual optimal solution, and to re-use all available information to "warm start" the max-flow computation after a change in the potentials.
1.9.7