More options for run() in scaling MCF algorithms (#180)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:34:35 +0100
changeset 8763b53491bf643
parent 875 22bb98ca0101
child 877 fe80a8145653
More options for run() in scaling MCF algorithms (#180)

- Three methods can be selected and the scaling factor can be
given for CostScaling.
- The scaling factor can be given for CapacityScaling.
lemon/capacity_scaling.h
lemon/cost_scaling.h
     1.1 --- a/lemon/capacity_scaling.h	Thu Nov 12 23:30:45 2009 +0100
     1.2 +++ b/lemon/capacity_scaling.h	Thu Nov 12 23:34:35 2009 +0100
     1.3 @@ -173,7 +173,7 @@
     1.4      IntVector _deficit_nodes;
     1.5  
     1.6      Value _delta;
     1.7 -    int _phase_num;
     1.8 +    int _factor;
     1.9      IntVector _pred;
    1.10  
    1.11    public:
    1.12 @@ -513,12 +513,11 @@
    1.13      /// \ref reset() is called, thus only the modified parameters
    1.14      /// have to be set again. See \ref reset() for examples.
    1.15      /// However the underlying digraph must not be modified after this
    1.16 -    /// class have been constructed, since it copies the digraph.
    1.17 +    /// class have been constructed, since it copies and extends the graph.
    1.18      ///
    1.19 -    /// \param scaling Enable or disable capacity scaling.
    1.20 -    /// If the maximum upper bound and/or the amount of total supply
    1.21 -    /// is rather small, the algorithm could be slightly faster without
    1.22 -    /// scaling.
    1.23 +    /// \param factor The capacity scaling factor. It must be larger than
    1.24 +    /// one to use scaling. If it is less or equal to one, then scaling
    1.25 +    /// will be disabled.
    1.26      ///
    1.27      /// \return \c INFEASIBLE if no feasible flow exists,
    1.28      /// \n \c OPTIMAL if the problem has optimal solution
    1.29 @@ -531,8 +530,9 @@
    1.30      /// these cases.
    1.31      ///
    1.32      /// \see ProblemType
    1.33 -    ProblemType run(bool scaling = true) {
    1.34 -      ProblemType pt = init(scaling);
    1.35 +    ProblemType run(int factor = 4) {
    1.36 +      _factor = factor;
    1.37 +      ProblemType pt = init();
    1.38        if (pt != OPTIMAL) return pt;
    1.39        return start();
    1.40      }
    1.41 @@ -546,7 +546,7 @@
    1.42      /// It is useful for multiple run() calls. If this function is not
    1.43      /// used, all the parameters given before are kept for the next
    1.44      /// \ref run() call.
    1.45 -    /// However the underlying digraph must not be modified after this
    1.46 +    /// However, the underlying digraph must not be modified after this
    1.47      /// class have been constructed, since it copies and extends the graph.
    1.48      ///
    1.49      /// For example,
    1.50 @@ -677,7 +677,7 @@
    1.51    private:
    1.52  
    1.53      // Initialize the algorithm
    1.54 -    ProblemType init(bool scaling) {
    1.55 +    ProblemType init() {
    1.56        if (_node_num == 0) return INFEASIBLE;
    1.57  
    1.58        // Check the sum of supply values
    1.59 @@ -758,7 +758,7 @@
    1.60        }
    1.61  
    1.62        // Initialize delta value
    1.63 -      if (scaling) {
    1.64 +      if (_factor > 1) {
    1.65          // With scaling
    1.66          Value max_sup = 0, max_dem = 0;
    1.67          for (int i = 0; i != _node_num; ++i) {
    1.68 @@ -770,9 +770,7 @@
    1.69            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
    1.70          }
    1.71          max_sup = std::min(std::min(max_sup, max_dem), max_cap);
    1.72 -        _phase_num = 0;
    1.73 -        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
    1.74 -          ++_phase_num;
    1.75 +        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
    1.76        } else {
    1.77          // Without scaling
    1.78          _delta = 1;
    1.79 @@ -811,8 +809,6 @@
    1.80      ProblemType startWithScaling() {
    1.81        // Perform capacity scaling phases
    1.82        int s, t;
    1.83 -      int phase_cnt = 0;
    1.84 -      int factor = 4;
    1.85        ResidualDijkstra _dijkstra(*this);
    1.86        while (true) {
    1.87          // Saturate all arcs not satisfying the optimality condition
    1.88 @@ -887,8 +883,7 @@
    1.89          }
    1.90  
    1.91          if (_delta == 1) break;
    1.92 -        if (++phase_cnt == _phase_num / 4) factor = 2;
    1.93 -        _delta = _delta <= factor ? 1 : _delta / factor;
    1.94 +        _delta = _delta <= _factor ? 1 : _delta / _factor;
    1.95        }
    1.96  
    1.97        return OPTIMAL;
     2.1 --- a/lemon/cost_scaling.h	Thu Nov 12 23:30:45 2009 +0100
     2.2 +++ b/lemon/cost_scaling.h	Thu Nov 12 23:34:35 2009 +0100
     2.3 @@ -110,6 +110,10 @@
     2.4    /// be integer.
     2.5    /// \warning This algorithm does not support negative costs for such
     2.6    /// arcs that have infinite upper bound.
     2.7 +  ///
     2.8 +  /// \note %CostScaling provides three different internal methods,
     2.9 +  /// from which the most efficient one is used by default.
    2.10 +  /// For more information, see \ref Method.
    2.11  #ifdef DOXYGEN
    2.12    template <typename GR, typename V, typename C, typename TR>
    2.13  #else
    2.14 @@ -159,6 +163,33 @@
    2.15        UNBOUNDED
    2.16      };
    2.17  
    2.18 +    /// \brief Constants for selecting the internal method.
    2.19 +    ///
    2.20 +    /// Enum type containing constants for selecting the internal method
    2.21 +    /// for the \ref run() function.
    2.22 +    ///
    2.23 +    /// \ref CostScaling provides three internal methods that differ mainly
    2.24 +    /// in their base operations, which are used in conjunction with the
    2.25 +    /// relabel operation.
    2.26 +    /// By default, the so called \ref PARTIAL_AUGMENT
    2.27 +    /// "Partial Augment-Relabel" method is used, which proved to be
    2.28 +    /// the most efficient and the most robust on various test inputs.
    2.29 +    /// However, the other methods can be selected using the \ref run()
    2.30 +    /// function with the proper parameter.
    2.31 +    enum Method {
    2.32 +      /// Local push operations are used, i.e. flow is moved only on one
    2.33 +      /// admissible arc at once.
    2.34 +      PUSH,
    2.35 +      /// Augment operations are used, i.e. flow is moved on admissible
    2.36 +      /// paths from a node with excess to a node with deficit.
    2.37 +      AUGMENT,
    2.38 +      /// Partial augment operations are used, i.e. flow is moved on 
    2.39 +      /// admissible paths started from a node with excess, but the
    2.40 +      /// lengths of these paths are limited. This method can be viewed
    2.41 +      /// as a combined version of the previous two operations.
    2.42 +      PARTIAL_AUGMENT
    2.43 +    };
    2.44 +
    2.45    private:
    2.46  
    2.47      TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    2.48 @@ -505,13 +536,12 @@
    2.49      /// that have been given are kept for the next call, unless
    2.50      /// \ref reset() is called, thus only the modified parameters
    2.51      /// have to be set again. See \ref reset() for examples.
    2.52 -    /// However the underlying digraph must not be modified after this
    2.53 -    /// class have been constructed, since it copies the digraph.
    2.54 +    /// However, the underlying digraph must not be modified after this
    2.55 +    /// class have been constructed, since it copies and extends the graph.
    2.56      ///
    2.57 -    /// \param partial_augment By default the algorithm performs
    2.58 -    /// partial augment and relabel operations in the cost scaling
    2.59 -    /// phases. Set this parameter to \c false for using local push and
    2.60 -    /// relabel operations instead.
    2.61 +    /// \param method The internal method that will be used in the
    2.62 +    /// algorithm. For more information, see \ref Method.
    2.63 +    /// \param factor The cost scaling factor. It must be larger than one.
    2.64      ///
    2.65      /// \return \c INFEASIBLE if no feasible flow exists,
    2.66      /// \n \c OPTIMAL if the problem has optimal solution
    2.67 @@ -523,11 +553,12 @@
    2.68      /// bounded over the feasible flows, but this algroithm cannot handle
    2.69      /// these cases.
    2.70      ///
    2.71 -    /// \see ProblemType
    2.72 -    ProblemType run(bool partial_augment = true) {
    2.73 +    /// \see ProblemType, Method
    2.74 +    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
    2.75 +      _alpha = factor;
    2.76        ProblemType pt = init();
    2.77        if (pt != OPTIMAL) return pt;
    2.78 -      start(partial_augment);
    2.79 +      start(method);
    2.80        return OPTIMAL;
    2.81      }
    2.82  
    2.83 @@ -681,9 +712,6 @@
    2.84      ProblemType init() {
    2.85        if (_res_node_num == 0) return INFEASIBLE;
    2.86  
    2.87 -      // Scaling factor
    2.88 -      _alpha = 8;
    2.89 -
    2.90        // Check the sum of supply values
    2.91        _sum_supply = 0;
    2.92        for (int i = 0; i != _root; ++i) {
    2.93 @@ -817,12 +845,21 @@
    2.94      }
    2.95  
    2.96      // Execute the algorithm and transform the results
    2.97 -    void start(bool partial_augment) {
    2.98 +    void start(Method method) {
    2.99 +      // Maximum path length for partial augment
   2.100 +      const int MAX_PATH_LENGTH = 4;
   2.101 +      
   2.102        // Execute the algorithm
   2.103 -      if (partial_augment) {
   2.104 -        startPartialAugment();
   2.105 -      } else {
   2.106 -        startPushRelabel();
   2.107 +      switch (method) {
   2.108 +        case PUSH:
   2.109 +          startPush();
   2.110 +          break;
   2.111 +        case AUGMENT:
   2.112 +          startAugment();
   2.113 +          break;
   2.114 +        case PARTIAL_AUGMENT:
   2.115 +          startAugment(MAX_PATH_LENGTH);
   2.116 +          break;
   2.117        }
   2.118  
   2.119        // Compute node potentials for the original costs
   2.120 @@ -851,14 +888,11 @@
   2.121        }
   2.122      }
   2.123  
   2.124 -    /// Execute the algorithm performing partial augmentation and
   2.125 -    /// relabel operations
   2.126 -    void startPartialAugment() {
   2.127 +    /// Execute the algorithm performing augment and relabel operations
   2.128 +    void startAugment(int max_length = std::numeric_limits<int>::max()) {
   2.129        // Paramters for heuristics
   2.130        const int BF_HEURISTIC_EPSILON_BOUND = 1000;
   2.131        const int BF_HEURISTIC_BOUND_FACTOR  = 3;
   2.132 -      // Maximum augment path length
   2.133 -      const int MAX_PATH_LENGTH = 4;
   2.134  
   2.135        // Perform cost scaling phases
   2.136        IntVector pred_arc(_res_node_num);
   2.137 @@ -925,7 +959,7 @@
   2.138            // Find an augmenting path from the start node
   2.139            int tip = start;
   2.140            while (_excess[tip] >= 0 &&
   2.141 -                 int(path_nodes.size()) <= MAX_PATH_LENGTH) {
   2.142 +                 int(path_nodes.size()) <= max_length) {
   2.143              int u;
   2.144              LargeCost min_red_cost, rc;
   2.145              int last_out = _sum_supply < 0 ?
   2.146 @@ -984,7 +1018,7 @@
   2.147      }
   2.148  
   2.149      /// Execute the algorithm performing push and relabel operations
   2.150 -    void startPushRelabel() {
   2.151 +    void startPush() {
   2.152        // Paramters for heuristics
   2.153        const int BF_HEURISTIC_EPSILON_BOUND = 1000;
   2.154        const int BF_HEURISTIC_BOUND_FACTOR  = 3;