doc/groups.dox
changeset 739 30d5f950aa5f
parent 658 d9cf3b5858ae
child 664 c01a98ce01fd
equal deleted inserted replaced
29:f9fc7a5f4a45 30:44bea10dbfb9
   333 but it is strongly related to maximum flow.
   333 but it is strongly related to maximum flow.
   334 For more information, see \ref Circulation.
   334 For more information, see \ref Circulation.
   335 */
   335 */
   336 
   336 
   337 /**
   337 /**
   338 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   338 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
   339 @ingroup algs
   339 @ingroup algs
   340 
   340 
   341 \brief Algorithms for finding minimum cost flows and circulations.
   341 \brief Algorithms for finding minimum cost flows and circulations.
   342 
   342 
   343 This group contains the algorithms for finding minimum cost flows and
   343 This group contains the algorithms for finding minimum cost flows and
   344 circulations.
   344 circulations. For more information about this problem and its dual
   345 
   345 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
   346 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   346 
   347 minimum total cost from a set of supply nodes to a set of demand nodes
   347 LEMON contains several algorithms for this problem.
   348 in a network with capacity constraints (lower and upper bounds)
       
   349 and arc costs.
       
   350 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
       
   351 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
       
   352 upper bounds for the flow values on the arcs, for which
       
   353 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
       
   354 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
       
   355 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
       
   356 signed supply values of the nodes.
       
   357 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
       
   358 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
       
   359 \f$-sup(u)\f$ demand.
       
   360 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
       
   361 of the following optimization problem.
       
   362 
       
   363 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
       
   364 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
       
   365     sup(u) \quad \forall u\in V \f]
       
   366 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
       
   367 
       
   368 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
       
   369 zero or negative in order to have a feasible solution (since the sum
       
   370 of the expressions on the left-hand side of the inequalities is zero).
       
   371 It means that the total demand must be greater or equal to the total
       
   372 supply and all the supplies have to be carried out from the supply nodes,
       
   373 but there could be demands that are not satisfied.
       
   374 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
       
   375 constraints have to be satisfied with equality, i.e. all demands
       
   376 have to be satisfied and all supplies have to be used.
       
   377 
       
   378 If you need the opposite inequalities in the supply/demand constraints
       
   379 (i.e. the total demand is less than the total supply and all the demands
       
   380 have to be satisfied while there could be supplies that are not used),
       
   381 then you could easily transform the problem to the above form by reversing
       
   382 the direction of the arcs and taking the negative of the supply values
       
   383 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
       
   384 However \ref NetworkSimplex algorithm also supports this form directly
       
   385 for the sake of convenience.
       
   386 
       
   387 A feasible solution for this problem can be found using \ref Circulation.
       
   388 
       
   389 Note that the above formulation is actually more general than the usual
       
   390 definition of the minimum cost flow problem, in which strict equalities
       
   391 are required in the supply/demand contraints, i.e.
       
   392 
       
   393 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
       
   394     sup(u) \quad \forall u\in V. \f]
       
   395 
       
   396 However if the sum of the supply values is zero, then these two problems
       
   397 are equivalent. So if you need the equality form, you have to ensure this
       
   398 additional contraint for the algorithms.
       
   399 
       
   400 The dual solution of the minimum cost flow problem is represented by node 
       
   401 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
       
   402 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
       
   403 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
       
   404 node potentials the following \e complementary \e slackness optimality
       
   405 conditions hold.
       
   406 
       
   407  - For all \f$uv\in A\f$ arcs:
       
   408    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
       
   409    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
       
   410    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
       
   411  - For all \f$u\in V\f$ nodes:
       
   412    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
       
   413      then \f$\pi(u)=0\f$.
       
   414  
       
   415 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
       
   416 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
       
   417 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
       
   418 
       
   419 All algorithms provide dual solution (node potentials) as well,
       
   420 if an optimal flow is found.
       
   421 
       
   422 LEMON contains several algorithms for solving minimum cost flow problems.
       
   423  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   348  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   424    pivot strategies.
   349    pivot strategies.
   425  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
   350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
   426    cost scaling.
   351    cost scaling.
   427  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
   352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
   428    capacity scaling.
   353    capacity scaling.
   429  - \ref CancelAndTighten The Cancel and Tighten algorithm.
   354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
   430  - \ref CycleCanceling Cycle-Canceling algorithms.
   355  - \ref CycleCanceling Cycle-Canceling algorithms.
   431 
       
   432 Most of these implementations support the general inequality form of the
       
   433 minimum cost flow problem, but CancelAndTighten and CycleCanceling
       
   434 only support the equality form due to the primal method they use.
       
   435 
   356 
   436 In general NetworkSimplex is the most efficient implementation,
   357 In general NetworkSimplex is the most efficient implementation,
   437 but in special cases other algorithms could be faster.
   358 but in special cases other algorithms could be faster.
   438 For example, if the total supply and/or capacities are rather small,
   359 For example, if the total supply and/or capacities are rather small,
   439 CapacityScaling is usually the fastest algorithm (without effective scaling).
   360 CapacityScaling is usually the fastest algorithm (without effective scaling).