# Changeset 640:6c408d864fa1 in lemon-1.2 for doc/groups.dox

Ignore:
Timestamp:
04/29/09 03:15:24 (11 years ago)
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.
• 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:
1 edited

### Legend:

Unmodified
 r611 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. 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 - if \f\$lower(uv)