COIN-OR::LEMON - Graph Library

Changeset 1318:ce1533650f7d in lemon


Ignore:
Timestamp:
07/07/14 15:40:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1319:11de70cf8550, 1322:1552352f9798
Parents:
1315:07cd9a2d20e0 (diff), 1317:b40c2bbb8da5 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #474

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r1298 r1318  
    937937        _node_id[n] = i;
    938938      }
    939       if (_arc_mixing) {
     939      if (_arc_mixing && _node_num > 1) {
    940940        // Store the arcs in a mixed order
    941941        const int skip = std::max(_arc_num / _node_num, 3);
  • lemon/network_simplex.h

    r1317 r1318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    4343  /// for finding a \ref min_cost_flow "minimum cost flow"
    44   /// \ref amo93networkflows, \ref dantzig63linearprog,
    45   /// \ref kellyoneill91netsimplex.
     44  /// \cite amo93networkflows, \cite dantzig63linearprog,
     45  /// \cite kellyoneill91netsimplex.
    4646  /// This algorithm is a highly efficient specialized version of the
    4747  /// linear programming simplex method directly for the minimum cost
    4848  /// flow problem.
    4949  ///
    50   /// In general, %NetworkSimplex is the fastest implementation available
    51   /// in LEMON for this problem.
    52   /// Moreover, it supports both directions of the supply/demand inequality
    53   /// constraints. For more information, see \ref SupplyType.
     50  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     51  /// implementations available in LEMON for solving this problem.
     52  /// (For more information, see \ref min_cost_flow_algs "the module page".)
     53  /// Furthermore, this class supports both directions of the supply/demand
     54  /// inequality constraints. For more information, see \ref SupplyType.
    5455  ///
    5556  /// Most of the parameters of the problem (except for the digraph)
     
    6465  /// algorithm. By default, it is the same as \c V.
    6566  ///
    66   /// \warning Both number types must be signed and all input data must
     67  /// \warning Both \c V and \c C must be signed number types.
     68  /// \warning All input data (capacities, supply values, and costs) must
    6769  /// be integer.
    6870  ///
     
    122124    /// the \ref run() function.
    123125    ///
    124     /// \ref NetworkSimplex provides five different pivot rule
    125     /// implementations that significantly affect the running time
     126    /// \ref NetworkSimplex provides five different implementations for
     127    /// the pivot strategy that significantly affects the running time
    126128    /// of the algorithm.
    127     /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128     /// proved to be the most efficient and the most robust on various
    129     /// test inputs.
    130     /// However, another pivot rule can be selected using the \ref run()
    131     /// function with the proper parameter.
     129    /// According to experimental tests conducted on various problem
     130    /// instances, \ref BLOCK_SEARCH "Block Search" and
     131    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
     132    /// to be the most efficient.
     133    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
     134    /// seemed to be slightly more robust, it is used by default.
     135    /// However, another pivot rule can easily be selected using the
     136    /// \ref run() function with the proper parameter.
    132137    enum PivotRule {
    133138
     
    155160      /// The \e Altering \e Candidate \e List pivot rule.
    156161      /// It is a modified version of the Candidate List method.
    157       /// It keeps only the several best eligible arcs from the former
     162      /// It keeps only a few of the best eligible arcs from the former
    158163      /// candidate list and extends this list in every iteration.
    159164      ALTERING_LIST
     
    168173    typedef std::vector<Cost> CostVector;
    169174    typedef std::vector<signed char> CharVector;
    170     // Note: vector<signed char> is used instead of vector<ArcState> and 
     175    // Note: vector<signed char> is used instead of vector<ArcState> and
    171176    // vector<ArcDirection> for efficiency reasons
    172177
     
    194199
    195200    // Parameters of the problem
    196     bool _have_lower;
     201    bool _has_lower;
    197202    SupplyType _stype;
    198203    Value _sum_supply;
     
    538543        SortFunc(const CostVector &map) : _map(map) {}
    539544        bool operator()(int left, int right) {
    540           return _map[left] > _map[right];
     545          return _map[left] < _map[right];
    541546        }
    542547      };
     
    556561        const double BLOCK_SIZE_FACTOR = 1.0;
    557562        const int MIN_BLOCK_SIZE = 10;
    558         const double HEAD_LENGTH_FACTOR = 0.1;
     563        const double HEAD_LENGTH_FACTOR = 0.01;
    559564        const int MIN_HEAD_LENGTH = 3;
    560565
     
    600605        }
    601606        for (e = 0; e != _next_arc; ++e) {
    602           _cand_cost[e] = _state[e] *
    603             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    604           if (_cand_cost[e] < 0) {
     607          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     608          if (c < 0) {
     609            _cand_cost[e] = c;
    605610            _candidates[_curr_length++] = e;
    606611          }
     
    615620      search_end:
    616621
    617         // Make heap of the candidate list (approximating a partial sort)
    618         make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    619                    _sort_func );
    620 
    621         // Pop the first element of the heap
     622        // Perform partial sort operation on the candidate list
     623        int new_length = std::min(_head_length + 1, _curr_length);
     624        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
     625                          _candidates.begin() + _curr_length, _sort_func);
     626
     627        // Select the entering arc and remove it from the list
    622628        _in_arc = _candidates[0];
    623629        _next_arc = e;
    624         pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    625                   _sort_func );
    626         _curr_length = std::min(_head_length, _curr_length - 1);
     630        _candidates[0] = _candidates[new_length - 1];
     631        _curr_length = new_length - 1;
    627632        return true;
    628633      }
     
    678683    template <typename LowerMap>
    679684    NetworkSimplex& lowerMap(const LowerMap& map) {
    680       _have_lower = true;
     685      _has_lower = true;
    681686      for (ArcIt a(_graph); a != INVALID; ++a) {
    682687        _lower[_arc_id[a]] = map[a];
     
    735740    ///
    736741    /// \return <tt>(*this)</tt>
     742    ///
     743    /// \sa supplyType()
    737744    template<typename SupplyMap>
    738745    NetworkSimplex& supplyMap(const SupplyMap& map) {
     
    751758    ///
    752759    /// Using this function has the same effect as using \ref supplyMap()
    753     /// with such a map in which \c k is assigned to \c s, \c -k is
     760    /// with a map in which \c k is assigned to \c s, \c -k is
    754761    /// assigned to \c t and all other nodes have zero supply value.
    755762    ///
     
    873880        _cost[i] = 1;
    874881      }
    875       _have_lower = false;
     882      _has_lower = false;
    876883      _stype = GEQ;
    877884      return *this;
     
    967974    ///
    968975    /// This function returns the total cost of the found flow.
    969     /// Its complexity is O(e).
     976    /// Its complexity is O(m).
    970977    ///
    971978    /// \note The return type of the function can be specified as a
     
    10041011    }
    10051012
    1006     /// \brief Return the flow map (the primal solution).
     1013    /// \brief Copy the flow values (the primal solution) into the
     1014    /// given map.
    10071015    ///
    10081016    /// This function copies the flow value on each arc into the given
     
    10281036    }
    10291037
    1030     /// \brief Return the potential map (the dual solution).
     1038    /// \brief Copy the potential values (the dual solution) into the
     1039    /// given map.
    10311040    ///
    10321041    /// This function copies the potential (dual value) of each node
     
    10591068             (_stype == LEQ && _sum_supply >= 0)) ) return false;
    10601069
     1070      // Check lower and upper bounds
     1071      LEMON_DEBUG(checkBoundMaps(),
     1072          "Upper bounds must be greater or equal to the lower bounds");
     1073
    10611074      // Remove non-zero lower bounds
    1062       if (_have_lower) {
     1075      if (_has_lower) {
    10631076        for (int i = 0; i != _arc_num; ++i) {
    10641077          Value c = _lower[i];
     
    12231236    }
    12241237
     1238    // Check if the upper bound is greater than or equal to the lower bound
     1239    // on each arc.
     1240    bool checkBoundMaps() {
     1241      for (int j = 0; j != _arc_num; ++j) {
     1242        if (_upper[j] < _lower[j]) return false;
     1243      }
     1244      return true;
     1245    }
     1246
    12251247    // Find the join node
    12261248    void findJoinNode() {
     
    14951517          }
    14961518        } else {
    1497           // Find the min. cost incomming arc for each demand node
     1519          // Find the min. cost incoming arc for each demand node
    14981520          for (int i = 0; i != int(demand_nodes.size()); ++i) {
    14991521            Node v = demand_nodes[i];
     
    15911613
    15921614      // Transform the solution and the supply map to the original form
    1593       if (_have_lower) {
     1615      if (_has_lower) {
    15941616        for (int i = 0; i != _arc_num; ++i) {
    15951617          Value c = _lower[i];
  • test/min_cost_flow_test.cc

    r1270 r1318  
    396396  checkMcf(mcf3, mcf3.run(param), neg2_gr, neg2_l, neg2_u, neg2_c, neg2_s,
    397397           mcf3.OPTIMAL, true,     -300, test_str + "-18", GEQ);
     398
     399  // Tests for empty graph
     400  Digraph gr0;
     401  MCF mcf0(gr0);
     402  mcf0.run(param);
     403  check(mcf0.totalCost() == 0, "Wrong total cost"); 
    398404}
    399405
  • test/min_cost_flow_test.cc

    r1317 r1318  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.