Changeset 710:8b0df68370a4 in lemon for doc/groups.dox
 Timestamp:
 05/12/09 12:06:40 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r707 r710 336 336 337 337 /** 338 @defgroup min_cost_flow Minimum Cost Flow Algorithms338 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 339 339 @ingroup algs 340 340 … … 342 342 343 343 This group contains the algorithms for finding minimum cost flows and 344 circulations. 345 346 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 347 minimum total cost from a set of supply nodes to a set of demand nodes 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 lefthand 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. 344 circulations. For more information about this problem and its dual 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 346 347 LEMON contains several algorithms for this problem. 423 348  \ref NetworkSimplex Primal Network Simplex algorithm with various 424 349 pivot strategies. … … 429 354  \ref CancelAndTighten The Cancel and Tighten algorithm. 430 355  \ref CycleCanceling CycleCanceling algorithms. 431 432 Most of these implementations support the general inequality form of the433 minimum cost flow problem, but CancelAndTighten and CycleCanceling434 only support the equality form due to the primal method they use.435 356 436 357 In general NetworkSimplex is the most efficient implementation,
Note: See TracChangeset
for help on using the changeset viewer.