COIN-OR::LEMON - Graph Library

Changeset 1318:ce1533650f7d in lemon


Ignore:
Timestamp:
07/07/14 15:40:12 (3 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.
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.