RhodeCode

	m4/lx_check_coin.m4 \

	cmake/FindCPLEX.cmake \

	cmake/FindCOIN.cmake \

  HINTS ${COIN_ROOT_DIR}/include

)

FIND_LIBRARY(COIN_CBC_LIBRARY

  NAMES Cbc libCbc

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY

  NAMES CbcSolver libCbcSolver

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CGL_LIBRARY

  NAMES Cgl libCgl

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_CLP_LIBRARY

  NAMES Clp libClp

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY

  NAMES CoinUtils libCoinUtils

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_LIBRARY

  NAMES Osi libOsi

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_CBC_LIBRARY

  NAMES OsiCbc libOsiCbc

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_CLP_LIBRARY

  NAMES OsiClp libOsiClp

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_OSI_VOL_LIBRARY

  NAMES OsiVol libOsiVol

  HINTS ${COIN_ROOT_DIR}/lib

)

FIND_LIBRARY(COIN_VOL_LIBRARY

  NAMES Vol libVol

  HINTS ${COIN_ROOT_DIR}/lib

)

SET(CPLEX_ROOT_DIR "" CACHE PATH "CPLEX root directory")

  PATHS "C:/ILOG/CPLEX91/include"

  PATHS "/opt/ilog/cplex91/include"

  HINTS ${CPLEX_ROOT_DIR}/include

)

  cplex91

  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda"

  PATHS "/opt/ilog/cplex91/bin"

  HINTS ${CPLEX_ROOT_DIR}/bin

)

  PATHS "C:/ILOG/CPLEX91/bin/x86_win32"

)

  IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")

    SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")

  ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")

SET(GLPK_ROOT_DIR "" CACHE PATH "GLPK root directory")

  PATHS ${GLPK_REGKEY}/include

  HINTS ${GLPK_ROOT_DIR}/include

)

FIND_LIBRARY(GLPK_LIBRARY

  glpk

  PATHS ${GLPK_REGKEY}/lib

  HINTS ${GLPK_ROOT_DIR}/lib

)

IF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)

  FILE(READ ${GLPK_INCLUDE_DIR}/glpk.h GLPK_GLPK_H)

  STRING(REGEX MATCH "define[ ]+GLP_MAJOR_VERSION[ ]+[0-9]+" GLPK_MAJOR_VERSION_LINE "${GLPK_GLPK_H}")

  STRING(REGEX REPLACE "define[ ]+GLP_MAJOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MAJOR "${GLPK_MAJOR_VERSION_LINE}")

  STRING(REGEX MATCH "define[ ]+GLP_MINOR_VERSION[ ]+[0-9]+" GLPK_MINOR_VERSION_LINE "${GLPK_GLPK_H}")

  STRING(REGEX REPLACE "define[ ]+GLP_MINOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MINOR "${GLPK_MINOR_VERSION_LINE}")

  SET(GLPK_VERSION_STRING "${GLPK_VERSION_MAJOR}.${GLPK_VERSION_MINOR}")

  IF(GLPK_FIND_VERSION)

    IF(GLPK_FIND_VERSION_COUNT GREATER 2)

      MESSAGE(SEND_ERROR "unexpected version string")

    ENDIF(GLPK_FIND_VERSION_COUNT GREATER 2)

    MATH(EXPR GLPK_REQUESTED_VERSION "${GLPK_FIND_VERSION_MAJOR}*100 + ${GLPK_FIND_VERSION_MINOR}")

    MATH(EXPR GLPK_FOUND_VERSION "${GLPK_VERSION_MAJOR}*100 + ${GLPK_VERSION_MINOR}")

    IF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)

      SET(GLPK_PROPER_VERSION_FOUND FALSE)

    ELSE(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)

      SET(GLPK_PROPER_VERSION_FOUND TRUE)

    ENDIF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)

  ELSE(GLPK_FIND_VERSION)

    SET(GLPK_PROPER_VERSION_FOUND TRUE)

  ENDIF(GLPK_FIND_VERSION)

ENDIF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)

FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_PROPER_VERSION_FOUND)

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

\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

A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution

An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem

 - For all \f$u\in V\f$ nodes:

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

All algorithms provide dual solution (node potentials) as well,

nodist_lemon_HEADERS = lemon/config.h	

	lemon/cbc.h \

    /// \brief The type of the flow and supply values.

    typedef typename SupplyMap::Value Value;

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    typedef lemon::Tolerance<Value> Tolerance;

    ///The type of the flow and supply values.

    typedef typename Traits::Value Value;

    typedef typename Digraph::template NodeMap<Value> ExcessMap;

          Value fc = -(*_excess)[_g.target(e)];

        Value exc=(*_excess)[act];

          Value fc=(*_up)[e]-(*_flow)[e];

          Value fc=(*_flow)[e]-(*_lo)[e];

    /// \brief Returns the flow value on the given arc.

    /// Returns the flow value on the given arc.

    Value flow(const Arc& arc) const {

          Value dif=-(*_supply)[n];

      Value delta=0;

      Value inf_cap = std::numeric_limits<Value>::has_infinity ?

        std::numeric_limits<Value>::infinity() :

        std::numeric_limits<Value>::max();

#include <lemon/config.h>

  /// Moreover it supports both directions of the supply/demand inequality

  /// constraints. For more information see \ref SupplyType.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  /// \tparam V The value type used for flow amounts, capacity bounds

  /// algorithm. By default it is the same as \c V.

  template <typename GR, typename V = int, typename C = V>

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    /// \brief Problem type constants for the \c run() function.

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The objective function of the problem is unbounded, i.e.

      /// there is a directed cycle having negative total cost and

      /// infinite upper bound.

      UNBOUNDED

    };

    /// \brief Constants for selecting the type of the supply constraints.

    ///

    /// Enum type containing constants for selecting the supply type,

    /// i.e. the direction of the inequalities in the supply/demand

    /// constraints of the \ref min_cost_flow "minimum cost flow problem".

    ///

    /// The default supply type is \c GEQ, since this form is supported

    /// by other minimum cost flow algorithms and the \ref Circulation

    /// algorithm, as well.

    /// The \c LEQ problem type can be selected using the \ref supplyType()

    /// Note that the equality form is a special case of both supply types.

    enum SupplyType {

      /// This option means that there are <em>"greater or equal"</em>

      /// supply/demand constraints in the definition, i.e. the exact

      /// formulation of the problem is the following.

      /**

          \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]

      */

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

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

      /// negative) and all the supplies have to be carried out from 

      /// the supply nodes, but there could be demands that are not 

      /// satisfied.

      GEQ,

      /// It is just an alias for the \c GEQ option.

      CARRY_SUPPLIES = GEQ,

      /// This option means that there are <em>"less or equal"</em>

      /// supply/demand constraints in the definition, i.e. the exact

      /// formulation of the problem is the following.

      /**

          \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.

      LEQ,

      /// It is just an alias for the \c LEQ option.

      SATISFY_DEMANDS = LEQ

    };

    /// \brief Constants for selecting the pivot rule.

    ///

    /// Enum type containing constants for selecting the pivot rule for

    /// the \ref run() function.

    ///

    typedef std::vector<Value> ValueVector;

    bool _have_lower;

    SupplyType _stype;

    Value _sum_supply;

    IntArcMap _arc_id;

    ValueVector _lower;

    ValueVector _upper;

    ValueVector _cap;

    ValueVector _supply;

    ValueVector _flow;

    Value delta;

  public:

    /// \brief Constant for infinite upper bounds (capacities).

    ///

    /// Constant for infinite upper bounds (capacities).

    /// It is \c std::numeric_limits<Value>::infinity() if available,

    /// \c std::numeric_limits<Value>::max() otherwise.

    const Value INF;

      _graph(graph), _node_id(graph), _arc_id(graph),

      INF(std::numeric_limits<Value>::has_infinity ?

          std::numeric_limits<Value>::infinity() :

          std::numeric_limits<Value>::max())

      // Check the value types

      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,

        "The flow type of NetworkSimplex must be signed");

      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,

        "The cost type of NetworkSimplex must be signed");

      // Resize vectors

      _node_num = countNodes(_graph);

      _arc_num = countArcs(_graph);

      int all_node_num = _node_num + 1;

      int all_arc_num = _arc_num + _node_num;

      _source.resize(all_arc_num);

      _target.resize(all_arc_num);

      _lower.resize(all_arc_num);

      _upper.resize(all_arc_num);

      _cap.resize(all_arc_num);

      _cost.resize(all_arc_num);

      _supply.resize(all_node_num);

      _flow.resize(all_arc_num);

      _pi.resize(all_node_num);

      _parent.resize(all_node_num);

      _pred.resize(all_node_num);

      _forward.resize(all_node_num);

      _thread.resize(all_node_num);

      _rev_thread.resize(all_node_num);

      _succ_num.resize(all_node_num);

      _last_succ.resize(all_node_num);

      _state.resize(all_arc_num);

      // Copy the graph (store the arcs in a mixed order)

      int i = 0;

      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {

        _node_id[n] = i;

      }

      int k = std::max(int(std::sqrt(double(_arc_num))), 10);

      i = 0;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        _arc_id[a] = i;

        _source[i] = _node_id[_graph.source(a)];

        _target[i] = _node_id[_graph.target(a)];

        if ((i += k) >= _arc_num) i = (i % k) + 1;

      }

      // Initialize maps

      for (int i = 0; i != _node_num; ++i) {

        _supply[i] = 0;

      }

      for (int i = 0; i != _arc_num; ++i) {

        _lower[i] = 0;

        _upper[i] = INF;

        _cost[i] = 1;

      }

      _have_lower = false;

      _stype = GEQ;

    /// If it is not used before calling \ref run(), the lower bounds

    /// will be set to zero on all arcs.

    /// Its \c Value type must be convertible to the \c Value type

    template <typename LowerMap>

    NetworkSimplex& lowerMap(const LowerMap& map) {

      _have_lower = true;

        _lower[_arc_id[a]] = map[a];

    /// If it is not used before calling \ref run(), the upper bounds

    /// will be set to \ref INF on all arcs (i.e. the flow value will be

    /// unbounded from above on each arc).

    /// Its \c Value type must be convertible to the \c Value type

    template<typename UpperMap>

    NetworkSimplex& upperMap(const UpperMap& map) {

        _upper[_arc_id[a]] = map[a];

    template<typename CostMap>

    NetworkSimplex& costMap(const CostMap& map) {

        _cost[_arc_id[a]] = map[a];

    /// Its \c Value type must be convertible to the \c Value type

    template<typename SupplyMap>

    NetworkSimplex& supplyMap(const SupplyMap& map) {

        _supply[_node_id[n]] = map[n];

    /// Using this function has the same effect as using \ref supplyMap()

    /// with such a map in which \c k is assigned to \c s, \c -k is

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {

      for (int i = 0; i != _node_num; ++i) {

        _supply[i] = 0;

      }

      _supply[_node_id[s]] =  k;

      _supply[_node_id[t]] = -k;

    /// \brief Set the type of the supply constraints.

    /// This function sets the type of the supply/demand constraints.

    /// If it is not used before calling \ref run(), the \ref GEQ supply

    /// For more information see \ref SupplyType.

    NetworkSimplex& supplyType(SupplyType supply_type) {

      _stype = supply_type;

    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 

    /// \ref supplyType().

    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

    /// However the underlying digraph must not be modified after this

    /// class have been constructed, since it copies and extends the graph.

    /// \return \c INFEASIBLE if no feasible flow exists,

    /// \n \c OPTIMAL if the problem has optimal solution

    /// (i.e. it is feasible and bounded), and the algorithm has found

    /// optimal flow and node potentials (primal and dual solutions),

    /// \n \c UNBOUNDED if the objective function of the problem is

    /// unbounded, i.e. there is a directed cycle having negative total

    /// cost and infinite upper bound.

    ///

    /// \see ProblemType, PivotRule

    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {

      if (!init()) return INFEASIBLE;

      return start(pivot_rule);

    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().

    /// However the underlying digraph must not be modified after this

    /// class have been constructed, since it copies and extends the graph.

    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

    ///   ns.upperMap(capacity).costMap(cost)

      for (int i = 0; i != _node_num; ++i) {

        _supply[i] = 0;

      }

      for (int i = 0; i != _arc_num; ++i) {

        _lower[i] = 0;

        _upper[i] = INF;

        _cost[i] = 1;

      }

      _have_lower = false;

      _stype = GEQ;

    /// Its complexity is O(e).

    template <typename Number>

    Number totalCost() const {

      Number c = 0;

      for (ArcIt a(_graph); a != INVALID; ++a) {

        int i = _arc_id[a];

        c += Number(_flow[i]) * Number(_cost[i]);

    Value flow(const Arc& a) const {

      return _flow[_arc_id[a]];

    /// \brief Return the flow map (the primal solution).

    /// This function copies the flow value on each arc into the given

    /// map. The \c Value type of the algorithm must be convertible to

    /// the \c Value type of the map.

    template <typename FlowMap>

    void flowMap(FlowMap &map) const {

      for (ArcIt a(_graph); a != INVALID; ++a) {

        map.set(a, _flow[_arc_id[a]]);

      }

      return _pi[_node_id[n]];

    /// \brief Return the potential map (the dual solution).

    /// This function copies the potential (dual value) of each node

    /// into the given map.

    /// The \c Cost type of the algorithm must be convertible to the

    /// \c Value type of the map.

    template <typename PotentialMap>

    void potentialMap(PotentialMap &map) const {

      for (NodeIt n(_graph); n != INVALID; ++n) {

        map.set(n, _pi[_node_id[n]]);

      }

      if (_node_num == 0) return false;

      // Check the sum of supply values

      _sum_supply = 0;

      for (int i = 0; i != _node_num; ++i) {

        _sum_supply += _supply[i];

      if ( !((_stype == GEQ && _sum_supply <= 0) ||

             (_stype == LEQ && _sum_supply >= 0)) ) return false;

      // Remove non-zero lower bounds

      if (_have_lower) {

        for (int i = 0; i != _arc_num; ++i) {

          Value c = _lower[i];

          if (c >= 0) {

            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;

          } else {

            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;

          }

          _supply[_source[i]] -= c;

          _supply[_target[i]] += c;

        }

      } else {

        for (int i = 0; i != _arc_num; ++i) {

          _cap[i] = _upper[i];

        }