doc/groups.dox
changeset 616 f2d6d3446adf
parent 590 b61354458b59
parent 609 e6927fe719e6
child 640 6c408d864fa1
equal deleted inserted replaced
23:dc20bf2fbc70 25:6449316627fe
   315 This group contains the algorithms for finding maximum flows and
   315 This group contains the algorithms for finding maximum flows and
   316 feasible circulations.
   316 feasible circulations.
   317 
   317 
   318 The \e maximum \e flow \e problem is to find a flow of maximum value between
   318 The \e maximum \e flow \e problem is to find a flow of maximum value between
   319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
   319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
   320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
   320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
   321 \f$s, t \in V\f$ source and target nodes.
   321 \f$s, t \in V\f$ source and target nodes.
   322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
   322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
   323 following optimization problem.
   323 following optimization problem.
   324 
   324 
   325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
   325 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
   326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
   326 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
   327     \qquad \forall v\in V\setminus\{s,t\} \f]
   327     \quad \forall u\in V\setminus\{s,t\} \f]
   328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
   328 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
   329 
   329 
   330 LEMON contains several algorithms for solving maximum flow problems:
   330 LEMON contains several algorithms for solving maximum flow problems:
   331 - \ref EdmondsKarp Edmonds-Karp algorithm.
   331 - \ref EdmondsKarp Edmonds-Karp algorithm.
   332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
   332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
   333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
   333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
   348 This group contains the algorithms for finding minimum cost flows and
   348 This group contains the algorithms for finding minimum cost flows and
   349 circulations.
   349 circulations.
   350 
   350 
   351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   352 minimum total cost from a set of supply nodes to a set of demand nodes
   352 minimum total cost from a set of supply nodes to a set of demand nodes
   353 in a network with capacity constraints and arc costs.
   353 in a network with capacity constraints (lower and upper bounds)
       
   354 and arc costs.
   354 Formally, let \f$G=(V,A)\f$ be a digraph,
   355 Formally, let \f$G=(V,A)\f$ be a digraph,
   355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
   356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
   356 upper bounds for the flow values on the arcs,
   357 upper bounds for the flow values on the arcs, for which
       
   358 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
   357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
   359 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
   358 on the arcs, and
   360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
   359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
   361 signed supply values of the nodes.
   360 of the nodes.
   362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
   363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   362 the following optimization problem.
   364 \f$-sup(u)\f$ demand.
   363 
   365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
   364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
   366 of the following optimization problem.
   365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
   367 
   366     supply(v) \qquad \forall v\in V \f]
   368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
   367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
   369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
   368 
   370     sup(u) \quad \forall u\in V \f]
   369 LEMON contains several algorithms for solving minimum cost flow problems:
   371 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
   370  - \ref CycleCanceling Cycle-canceling algorithms.
   372 
   371  - \ref CapacityScaling Successive shortest path algorithm with optional
   373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
       
   374 zero or negative in order to have a feasible solution (since the sum
       
   375 of the expressions on the left-hand side of the inequalities is zero).
       
   376 It means that the total demand must be greater or equal to the total
       
   377 supply and all the supplies have to be carried out from the supply nodes,
       
   378 but there could be demands that are not satisfied.
       
   379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
       
   380 constraints have to be satisfied with equality, i.e. all demands
       
   381 have to be satisfied and all supplies have to be used.
       
   382 
       
   383 If you need the opposite inequalities in the supply/demand constraints
       
   384 (i.e. the total demand is less than the total supply and all the demands
       
   385 have to be satisfied while there could be supplies that are not used),
       
   386 then you could easily transform the problem to the above form by reversing
       
   387 the direction of the arcs and taking the negative of the supply values
       
   388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
       
   389 However \ref NetworkSimplex algorithm also supports this form directly
       
   390 for the sake of convenience.
       
   391 
       
   392 A feasible solution for this problem can be found using \ref Circulation.
       
   393 
       
   394 Note that the above formulation is actually more general than the usual
       
   395 definition of the minimum cost flow problem, in which strict equalities
       
   396 are required in the supply/demand contraints, i.e.
       
   397 
       
   398 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
       
   399     sup(u) \quad \forall u\in V. \f]
       
   400 
       
   401 However if the sum of the supply values is zero, then these two problems
       
   402 are equivalent. So if you need the equality form, you have to ensure this
       
   403 additional contraint for the algorithms.
       
   404 
       
   405 The dual solution of the minimum cost flow problem is represented by node 
       
   406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
       
   407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
       
   408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
       
   409 node potentials the following \e complementary \e slackness optimality
       
   410 conditions hold.
       
   411 
       
   412  - For all \f$uv\in A\f$ arcs:
       
   413    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
       
   414    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
       
   415    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
       
   416  - For all \f$u\in V\f$:
       
   417    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
       
   418      then \f$\pi(u)=0\f$.
       
   419  
       
   420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
       
   421 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
       
   422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
       
   423 
       
   424 All algorithms provide dual solution (node potentials) as well
       
   425 if an optimal flow is found.
       
   426 
       
   427 LEMON contains several algorithms for solving minimum cost flow problems.
       
   428  - \ref NetworkSimplex Primal Network Simplex algorithm with various
       
   429    pivot strategies.
       
   430  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
       
   431    cost scaling.
       
   432  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
   372    capacity scaling.
   433    capacity scaling.
   373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
   434  - \ref CancelAndTighten The Cancel and Tighten algorithm.
   374    cost scaling.
   435  - \ref CycleCanceling Cycle-Canceling algorithms.
   375  - \ref NetworkSimplex Primal network simplex algorithm with various
   436 
   376    pivot strategies.
   437 Most of these implementations support the general inequality form of the
       
   438 minimum cost flow problem, but CancelAndTighten and CycleCanceling
       
   439 only support the equality form due to the primal method they use.
       
   440 
       
   441 In general NetworkSimplex is the most efficient implementation,
       
   442 but in special cases other algorithms could be faster.
       
   443 For example, if the total supply and/or capacities are rather small,
       
   444 CapacityScaling is usually the fastest algorithm (without effective scaling).
   377 */
   445 */
   378 
   446 
   379 /**
   447 /**
   380 @defgroup min_cut Minimum Cut Algorithms
   448 @defgroup min_cut Minimum Cut Algorithms
   381 @ingroup algs
   449 @ingroup algs