RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/**

\page min_cost_flow Minimum Cost Flow Problem

\section mcf_def Definition (GEQ form)

The \e minimum \e cost \e flow \e problem is to find a feasible flow of

minimum total cost from a set of supply nodes to a set of demand nodes

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: A\rightarrow\mathbf{R}\f$,

\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and

upper bounds for the flow values on the arcs, for which

\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,

\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow

on the arcs and \f$sup: V\rightarrow\mathbf{R}\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{R}\f$ solution

of the following optimization problem.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

zero or negative in order to have a feasible solution (since the sum

of the expressions on the left-hand side of the inequalities is zero).

It means that the total demand must be greater or equal to the total

supply and all the supplies have to be carried out from the supply nodes,

but there could be demands that are not satisfied.

If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

constraints have to be satisfied with equality, i.e. all demands

have to be satisfied and all supplies have to be used.

\section mcf_algs Algorithms

LEMON contains several algorithms for solving this problem, for more

information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".

A feasible solution for this problem can be found using \ref Circulation.

\section mcf_dual Dual Solution

The dual solution of the minimum cost flow problem is represented by

node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.

An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal

if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials

the following \e complementary \e slackness optimality conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - 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$ nodes:

   - \f$\pi(u)<=0\f$;

   - 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 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,

if an optimal flow is found.

\section mcf_eq Equality Form

The above \ref mcf_def "definition" is actually more general than the

usual formulation of the minimum cost flow problem, in which strict

equalities are required in the supply/demand contraints.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

However if the sum of the supply values is zero, then these two problems

are equivalent.

The \ref min_cost_flow_algs "algorithms" in LEMON support the general

form, so if you need the equality form, you have to ensure this additional

contraint manually.

\section mcf_leq Opposite Inequalites (LEQ Form)

Another possible definition of the minimum cost flow problem is

when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,

instead of the <em>"greater or equal"</em> (GEQ) constraints.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

It means that the total demand must be less or equal to the 

total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or

positive) and all the demands have to be satisfied, but there

could be supplies that are not carried out from the supply

nodes.

The equality form is also a special case of this form, of course.

You could easily transform this case to the \ref mcf_def "GEQ form"

of the problem by reversing the direction of the arcs and taking the

negative of the supply values (e.g. using \ref ReverseDigraph and

\ref NegMap adaptors).

However \ref NetworkSimplex algorithm also supports this form directly

for the sake of convenience.

Note that the optimality conditions for this supply constraint type are

slightly differ from the conditions that are discussed for the GEQ form,

namely the potentials have to be non-negative instead of non-positive.

An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem

is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$

node potentials the following conditions hold.

 - For all \f$uv\in A\f$ arcs:

   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;

   - 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$ nodes:

   - \f$\pi(u)>=0\f$;

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

*/

}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <lemon/connectivity.h>

#include <lemon/list_graph.h>

#include <lemon/adaptors.h>

#include "test_tools.h"

using namespace lemon;

int main()

{

  typedef ListDigraph Digraph;

  typedef Undirector<Digraph> Graph;

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

    check(stronglyConnected(d), "The empty digraph is strongly connected");

    check(countStronglyConnectedComponents(d) == 0,

          "The empty digraph has 0 strongly connected component");

    check(connected(g), "The empty graph is connected");

    check(countConnectedComponents(g) == 0,

          "The empty graph has 0 connected component");

    check(biNodeConnected(g), "The empty graph is bi-node-connected");

    check(countBiNodeConnectedComponents(g) == 0,

          "The empty graph has 0 bi-node-connected component");

    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");

    check(countBiEdgeConnectedComponents(g) == 0,

          "The empty graph has 0 bi-edge-connected component");

    check(dag(d), "The empty digraph is DAG.");

    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");

    check(loopFree(d), "The empty digraph is loop-free.");

    check(parallelFree(d), "The empty digraph is parallel-free.");

    check(simpleGraph(d), "The empty digraph is simple.");

    check(acyclic(g), "The empty graph is acyclic.");

    check(tree(g), "The empty graph is tree.");

    check(bipartite(g), "The empty graph is bipartite.");

    check(loopFree(g), "The empty graph is loop-free.");

    check(parallelFree(g), "The empty graph is parallel-free.");

    check(simpleGraph(g), "The empty graph is simple.");

  }

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

    Digraph::Node n = d.addNode();

    check(stronglyConnected(d), "This digraph is strongly connected");

    check(countStronglyConnectedComponents(d) == 1,

          "This digraph has 1 strongly connected component");

    check(connected(g), "This graph is connected");

    check(countConnectedComponents(g) == 1,

          "This graph has 1 connected component");

    check(biNodeConnected(g), "This graph is bi-node-connected");

    check(countBiNodeConnectedComponents(g) == 0,

          "This graph has 0 bi-node-connected component");

    check(biEdgeConnected(g), "This graph is bi-edge-connected");

    check(countBiEdgeConnectedComponents(g) == 1,

          "This graph has 1 bi-edge-connected component");

    check(dag(d), "This digraph is DAG.");

    check(checkedTopologicalSort(d, order), "This digraph is DAG.");

    check(loopFree(d), "This digraph is loop-free.");

    check(parallelFree(d), "This digraph is parallel-free.");

    check(simpleGraph(d), "This digraph is simple.");

    check(acyclic(g), "This graph is acyclic.");

    check(tree(g), "This graph is tree.");

    check(bipartite(g), "This graph is bipartite.");

    check(loopFree(g), "This graph is loop-free.");

    check(parallelFree(g), "This graph is parallel-free.");

    check(simpleGraph(g), "This graph is simple.");

  }

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

    Digraph::Node n1 = d.addNode();

    Digraph::Node n2 = d.addNode();

    Digraph::Node n3 = d.addNode();

    Digraph::Node n4 = d.addNode();

    Digraph::Node n5 = d.addNode();

    Digraph::Node n6 = d.addNode();

    d.addArc(n1, n3);

    d.addArc(n3, n2);

    d.addArc(n2, n1);

    d.addArc(n4, n2);

    d.addArc(n4, n3);

    d.addArc(n5, n6);

    d.addArc(n6, n5);

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    check(!connected(g), "This graph is not connected");

    check(countConnectedComponents(g) == 2,

          "This graph has 2 connected components");

    check(!dag(d), "This digraph is not DAG.");

    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");

    check(loopFree(d), "This digraph is loop-free.");

    check(parallelFree(d), "This digraph is parallel-free.");

    check(simpleGraph(d), "This digraph is simple.");

    check(!acyclic(g), "This graph is not acyclic.");

    check(!tree(g), "This graph is not tree.");

    check(!bipartite(g), "This graph is not bipartite.");

    check(loopFree(g), "This graph is loop-free.");

    check(!parallelFree(g), "This graph is not parallel-free.");

    check(!simpleGraph(g), "This graph is not simple.");

    d.addArc(n3, n3);

    check(!loopFree(d), "This digraph is not loop-free.");

    check(!loopFree(g), "This graph is not loop-free.");

    check(!simpleGraph(d), "This digraph is not simple.");

    d.addArc(n3, n2);

    check(!parallelFree(d), "This digraph is not parallel-free.");

  }

  {

    Digraph d;

    Digraph::ArcMap<bool> cutarcs(d, false);

    Graph g(d);

    Digraph::Node n1 = d.addNode();

    Digraph::Node n2 = d.addNode();

    Digraph::Node n3 = d.addNode();

    Digraph::Node n4 = d.addNode();

    Digraph::Node n5 = d.addNode();

    Digraph::Node n6 = d.addNode();

    Digraph::Node n7 = d.addNode();

    Digraph::Node n8 = d.addNode();

    d.addArc(n1, n2);

    d.addArc(n5, n1);

    d.addArc(n2, n8);

    d.addArc(n8, n5);

    d.addArc(n6, n4);

    d.addArc(n4, n6);

    d.addArc(n2, n5);

    d.addArc(n1, n8);

    d.addArc(n6, n7);

    d.addArc(n7, n6);

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    Digraph::NodeMap<int> scomp1(d);

    check(stronglyConnectedComponents(d, scomp1) == 3,

          "This digraph has 3 strongly connected components");

    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&

          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");

    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&

          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");

    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],

          "Wrong stronglyConnectedComponents()");

    Digraph::ArcMap<bool> scut1(d, false);

    check(stronglyConnectedCutArcs(d, scut1) == 0,

          "This digraph has 0 strongly connected cut arc.");

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");

    }

    check(!connected(g), "This graph is not connected");

    check(countConnectedComponents(g) == 3,

          "This graph has 3 connected components");

    Graph::NodeMap<int> comp(g);

    check(connectedComponents(g, comp) == 3,

          "This graph has 3 connected components");

    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&

          comp[n3] != comp[n4], "Wrong connectedComponents()");

    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&

          comp[n1] == comp[n8], "Wrong connectedComponents()");

    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],

          "Wrong connectedComponents()");

    cutarcs[d.addArc(n3, n1)] = true;

    cutarcs[d.addArc(n3, n5)] = true;

    cutarcs[d.addArc(n3, n8)] = true;

    cutarcs[d.addArc(n8, n6)] = true;

    cutarcs[d.addArc(n8, n7)] = true;

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    Digraph::NodeMap<int> scomp2(d);

    check(stronglyConnectedComponents(d, scomp2) == 3,

          "This digraph has 3 strongly connected components");

    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");

    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&

          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");

    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,

          "Wrong stronglyConnectedComponents()");

    Digraph::ArcMap<bool> scut2(d, false);

    check(stronglyConnectedCutArcs(d, scut2) == 5,

          "This digraph has 5 strongly connected cut arcs.");

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");

    }

  }

  {

    // DAG example for topological sort from the book New Algorithms

    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Digraph::Node belt = d.addNode();

    Digraph::Node trousers = d.addNode();

    Digraph::Node necktie = d.addNode();

    Digraph::Node coat = d.addNode();

    Digraph::Node socks = d.addNode();

    Digraph::Node shirt = d.addNode();

    Digraph::Node shoe = d.addNode();

    Digraph::Node watch = d.addNode();

    Digraph::Node pants = d.addNode();

    d.addArc(socks, shoe);

    d.addArc(pants, shoe);

    d.addArc(pants, trousers);

    d.addArc(trousers, shoe);

    d.addArc(trousers, belt);

    d.addArc(belt, coat);

    d.addArc(shirt, belt);

    d.addArc(shirt, necktie);

    d.addArc(necktie, coat);

    check(dag(d), "This digraph is DAG.");

    topologicalSort(d, order);

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(order[d.source(a)] < order[d.target(a)],

            "Wrong topologicalSort()");

    }

  }

  {

    ListGraph g;

    ListGraph::NodeMap<bool> map(g);

    ListGraph::Node n1 = g.addNode();

    ListGraph::Node n2 = g.addNode();

    ListGraph::Node n3 = g.addNode();

    ListGraph::Node n4 = g.addNode();

    ListGraph::Node n5 = g.addNode();

    ListGraph::Node n6 = g.addNode();

    ListGraph::Node n7 = g.addNode();

    g.addEdge(n1, n3);

    g.addEdge(n1, n4);

    g.addEdge(n2, n5);

    g.addEdge(n3, n6);

    g.addEdge(n4, n6);

    g.addEdge(n4, n7);

    g.addEdge(n5, n7);

    check(bipartite(g), "This graph is bipartite");

    check(bipartitePartitions(g, map), "This graph is bipartite");

    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],

          "Wrong bipartitePartitions()");

    check(map[n3] == map[n4] && map[n3] == map[n5],

          "Wrong bipartitePartitions()");

  }

  return 0;

}

      "LEMON - Library for Efficient Modeling and Optimization in Networks")

2009-05-13 Version 1.1 released

        This is the second stable release of the 1.x series. It

        features a better coverage of the tools available in the 0.x

        series, a thoroughly reworked LP/MIP interface plus various

        improvements in the existing tools.

        * Much improved M$ Windows support

          * Various improvements in the CMAKE build system

          * Compilation warnings are fixed/suppressed

        * Support IBM xlC compiler

        * New algorithms

          * Connectivity related algorithms (#61)

          * Euler walks (#65)

          * Preflow push-relabel max. flow algorithm (#176)

          * Circulation algorithm (push-relabel based) (#175)

          * Suurballe algorithm (#47)

          * Gomory-Hu algorithm (#66)

          * Hao-Orlin algorithm (#58)

          * Edmond's maximum cardinality and weighted matching algorithms

            in general graphs (#48,#265)

          * Minimum cost arborescence/branching (#60)

          * Network Simplex min. cost flow algorithm (#234)

        * New data structures

          * Full graph structure (#57)

          * Grid graph structure (#57)

          * Hypercube graph structure (#57)

          * Graph adaptors (#67)

          * ArcSet and EdgeSet classes (#67)

          * Elevator class (#174)

        * Other new tools

          * LP/MIP interface (#44)

            * Support for GLPK, CPLEX, Soplex, COIN-OR CLP and CBC

          * Reader for the Nauty file format (#55)

          * DIMACS readers (#167)

          * Radix sort algorithms (#72)

          * RangeIdMap and CrossRefMap (#160)

        * New command line tools

          * DIMACS to LGF converter (#182)

          * lgf-gen - a graph generator (#45)

          * DIMACS solver utility (#226)

        * Other code improvements

          * Lognormal distribution added to Random (#102)

          * Better (i.e. O(1) time) item counting in SmartGraph (#3)

          * The standard maps of graphs are guaranteed to be

            reference maps (#190)

        * Miscellaneous

          * Various doc improvements

          * Improved 0.x -> 1.x converter script

        * Several bugfixes (compared to release 1.0):

          #170: Bugfix SmartDigraph::split()

          #171: Bugfix in SmartGraph::restoreSnapshot()

          #172: Extended test cases for graphs and digraphs

          #173: Bugfix in Random

                * operator()s always return a double now

                * the faulty real<Num>(Num) and real<Num>(Num,Num)

                  have been removed

          #187: Remove DijkstraWidestPathOperationTraits

          #61:  Bugfix in DfsVisit

          #193: Bugfix in GraphReader::skipSection()

          #195: Bugfix in ConEdgeIt()

          #197: Bugfix in heap unionfind

                * This bug affects Edmond's general matching algorithms

          #207: Fix 'make install' without 'make html' using CMAKE

          #208: Suppress or fix VS2008 compilation warnings

          ----: Update the LEMON icon

          ----: Enable the component-based installer

                (in installers made by CPACK)

          ----: Set the proper version for CMAKE in the tarballs

                (made by autotools)

          ----: Minor clarification in the LICENSE file

          ----: Add missing unistd.h include to time_measure.h

          #204: Compilation bug fixed in graph_to_eps.h with VS2005

          #214,#215: windows.h should never be included by lemon headers

          #230: Build systems check the availability of 'long long' type

          #229: Default implementation of Tolerance<> is used for integer types

          #211,#212: Various fixes for compiling on AIX

          ----: Improvements in CMAKE config

                - docs is installed in share/doc/

                - detects newer versions of Ghostscript

          #239: Fix missing 'inline' specifier in time_measure.h

          #274,#280: Install lemon/config.h

          #275: Prefix macro names with LEMON_ in lemon/config.h

          ----: Small script for making the release tarballs added

          ----: Minor improvement in unify-sources.sh (a76f55d7d397)

=====================================================================

LEMON - a Library for Efficient Modeling and Optimization in Networks

=====================================================================

	doc/min_cost_flow.dox \