Changeset 640:6c408d864fa1 in lemon-main for doc

Timestamp:

04/29/09 03:15:24 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Support negative costs and bounds in NetworkSimplex? (#270)

• The interface is reworked to support negative costs and bounds.
  • ProblemType? and problemType() are renamed to SupplyType? and supplyType(), see also #234.
  • ProblemType? type is introduced similarly to the LP interface.
  • 'bool run()' is replaced by 'ProblemType? run()' to handle unbounded problem instances, as well.
  • Add INF public member constant similarly to the LP interface.
• Remove capacityMap() and boundMaps(), see also #266.
• Update the problem definition in the MCF module.
• Remove the usage of Circulation (and adaptors) for checking feasibility. Check feasibility by examining the artifical arcs instead (after solving the problem).
• Additional check for unbounded negative cycles found during the algorithm (it is possible now, since negative costs are allowed).
• Fix in the constructor (the value types needn't be integer any more), see also #254.
• Improve and extend the doc.
• Rework the test file and add test cases for negative costs and bounds.

File:

• doc/groups.dox (modified) (3 diffs)

doc/groups.dox

@@ -353 +353 @@
 in a network with capacity constraints (lower and upper bounds)
 and arc costs.
-Formally, let \f$G=(V,A)\f$ be a digraph,
-\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
+Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
+\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
 upper bounds for the flow values on the arcs, for which
-\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
-\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
-on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
+\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
+\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
+on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
 signed supply values of the nodes.
 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 \f$-sup(u)\f$ demand.
-A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
+A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
 of the following optimization problem.
 
@@ -405 +405 @@
 The dual solution of the minimum cost flow problem is represented by node 
 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
-An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
+An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
 node potentials the following \e complementary \e slackness optimality
@@ -414 +414 @@
    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
- - For all \f$u\in V\f$:
+ - For all \f$u\in V\f$ nodes:
    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
      then \f$\pi(u)=0\f$.
  
 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
-\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
+\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 
-All algorithms provide dual solution (node potentials) as well
+All algorithms provide dual solution (node potentials) as well,
 if an optimal flow is found.