COIN-OR::LEMON - Graph Library

Changeset 810:3b53491bf643 in lemon-1.2


Ignore:
Timestamp:
11/12/09 23:34:35 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Rebase:
31306464373530663736663634663865303635326136663934636335303533383063623764626530
Message:

More options for run() in scaling MCF algorithms (#180)

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r807 r810  
    174174
    175175    Value _delta;
    176     int _phase_num;
     176    int _factor;
    177177    IntVector _pred;
    178178
     
    514514    /// have to be set again. See \ref reset() for examples.
    515515    /// However the underlying digraph must not be modified after this
    516     /// class have been constructed, since it copies the digraph.
    517     ///
    518     /// \param scaling Enable or disable capacity scaling.
    519     /// If the maximum upper bound and/or the amount of total supply
    520     /// is rather small, the algorithm could be slightly faster without
    521     /// scaling.
     516    /// class have been constructed, since it copies and extends the graph.
     517    ///
     518    /// \param factor The capacity scaling factor. It must be larger than
     519    /// one to use scaling. If it is less or equal to one, then scaling
     520    /// will be disabled.
    522521    ///
    523522    /// \return \c INFEASIBLE if no feasible flow exists,
     
    532531    ///
    533532    /// \see ProblemType
    534     ProblemType run(bool scaling = true) {
    535       ProblemType pt = init(scaling);
     533    ProblemType run(int factor = 4) {
     534      _factor = factor;
     535      ProblemType pt = init();
    536536      if (pt != OPTIMAL) return pt;
    537537      return start();
     
    547547    /// used, all the parameters given before are kept for the next
    548548    /// \ref run() call.
    549     /// However the underlying digraph must not be modified after this
     549    /// However, the underlying digraph must not be modified after this
    550550    /// class have been constructed, since it copies and extends the graph.
    551551    ///
     
    678678
    679679    // Initialize the algorithm
    680     ProblemType init(bool scaling) {
     680    ProblemType init() {
    681681      if (_node_num == 0) return INFEASIBLE;
    682682
     
    759759
    760760      // Initialize delta value
    761       if (scaling) {
     761      if (_factor > 1) {
    762762        // With scaling
    763763        Value max_sup = 0, max_dem = 0;
     
    771771        }
    772772        max_sup = std::min(std::min(max_sup, max_dem), max_cap);
    773         _phase_num = 0;
    774         for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
    775           ++_phase_num;
     773        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
    776774      } else {
    777775        // Without scaling
     
    812810      // Perform capacity scaling phases
    813811      int s, t;
    814       int phase_cnt = 0;
    815       int factor = 4;
    816812      ResidualDijkstra _dijkstra(*this);
    817813      while (true) {
     
    888884
    889885        if (_delta == 1) break;
    890         if (++phase_cnt == _phase_num / 4) factor = 2;
    891         _delta = _delta <= factor ? 1 : _delta / factor;
     886        _delta = _delta <= _factor ? 1 : _delta / _factor;
    892887      }
    893888
  • lemon/cost_scaling.h

    r809 r810  
    111111  /// \warning This algorithm does not support negative costs for such
    112112  /// arcs that have infinite upper bound.
     113  ///
     114  /// \note %CostScaling provides three different internal methods,
     115  /// from which the most efficient one is used by default.
     116  /// For more information, see \ref Method.
    113117#ifdef DOXYGEN
    114118  template <typename GR, typename V, typename C, typename TR>
     
    160164    };
    161165
     166    /// \brief Constants for selecting the internal method.
     167    ///
     168    /// Enum type containing constants for selecting the internal method
     169    /// for the \ref run() function.
     170    ///
     171    /// \ref CostScaling provides three internal methods that differ mainly
     172    /// in their base operations, which are used in conjunction with the
     173    /// relabel operation.
     174    /// By default, the so called \ref PARTIAL_AUGMENT
     175    /// "Partial Augment-Relabel" method is used, which proved to be
     176    /// the most efficient and the most robust on various test inputs.
     177    /// However, the other methods can be selected using the \ref run()
     178    /// function with the proper parameter.
     179    enum Method {
     180      /// Local push operations are used, i.e. flow is moved only on one
     181      /// admissible arc at once.
     182      PUSH,
     183      /// Augment operations are used, i.e. flow is moved on admissible
     184      /// paths from a node with excess to a node with deficit.
     185      AUGMENT,
     186      /// Partial augment operations are used, i.e. flow is moved on
     187      /// admissible paths started from a node with excess, but the
     188      /// lengths of these paths are limited. This method can be viewed
     189      /// as a combined version of the previous two operations.
     190      PARTIAL_AUGMENT
     191    };
     192
    162193  private:
    163194
     
    506537    /// \ref reset() is called, thus only the modified parameters
    507538    /// have to be set again. See \ref reset() for examples.
    508     /// However the underlying digraph must not be modified after this
    509     /// class have been constructed, since it copies the digraph.
    510     ///
    511     /// \param partial_augment By default the algorithm performs
    512     /// partial augment and relabel operations in the cost scaling
    513     /// phases. Set this parameter to \c false for using local push and
    514     /// relabel operations instead.
     539    /// However, the underlying digraph must not be modified after this
     540    /// class have been constructed, since it copies and extends the graph.
     541    ///
     542    /// \param method The internal method that will be used in the
     543    /// algorithm. For more information, see \ref Method.
     544    /// \param factor The cost scaling factor. It must be larger than one.
    515545    ///
    516546    /// \return \c INFEASIBLE if no feasible flow exists,
     
    524554    /// these cases.
    525555    ///
    526     /// \see ProblemType
    527     ProblemType run(bool partial_augment = true) {
     556    /// \see ProblemType, Method
     557    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
     558      _alpha = factor;
    528559      ProblemType pt = init();
    529560      if (pt != OPTIMAL) return pt;
    530       start(partial_augment);
     561      start(method);
    531562      return OPTIMAL;
    532563    }
     
    681712    ProblemType init() {
    682713      if (_res_node_num == 0) return INFEASIBLE;
    683 
    684       // Scaling factor
    685       _alpha = 8;
    686714
    687715      // Check the sum of supply values
     
    818846
    819847    // Execute the algorithm and transform the results
    820     void start(bool partial_augment) {
     848    void start(Method method) {
     849      // Maximum path length for partial augment
     850      const int MAX_PATH_LENGTH = 4;
     851     
    821852      // Execute the algorithm
    822       if (partial_augment) {
    823         startPartialAugment();
    824       } else {
    825         startPushRelabel();
     853      switch (method) {
     854        case PUSH:
     855          startPush();
     856          break;
     857        case AUGMENT:
     858          startAugment();
     859          break;
     860        case PARTIAL_AUGMENT:
     861          startAugment(MAX_PATH_LENGTH);
     862          break;
    826863      }
    827864
     
    852889    }
    853890
    854     /// Execute the algorithm performing partial augmentation and
    855     /// relabel operations
    856     void startPartialAugment() {
     891    /// Execute the algorithm performing augment and relabel operations
     892    void startAugment(int max_length = std::numeric_limits<int>::max()) {
    857893      // Paramters for heuristics
    858894      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
    859895      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
    860       // Maximum augment path length
    861       const int MAX_PATH_LENGTH = 4;
    862896
    863897      // Perform cost scaling phases
     
    926960          int tip = start;
    927961          while (_excess[tip] >= 0 &&
    928                  int(path_nodes.size()) <= MAX_PATH_LENGTH) {
     962                 int(path_nodes.size()) <= max_length) {
    929963            int u;
    930964            LargeCost min_red_cost, rc;
     
    9851019
    9861020    /// Execute the algorithm performing push and relabel operations
    987     void startPushRelabel() {
     1021    void startPush() {
    9881022      // Paramters for heuristics
    9891023      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
Note: See TracChangeset for help on using the changeset viewer.