COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
11/15/12 07:17:48 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Ensure strongly polynomial running time for CycleCanceling? (#436)
The number of iterations performed by Howard's algorithm is limited.
If the limit is reached, a strongly polynomial implementation,
HartmannOrlinMmc? is executed to find a minimum mean cycle.
This iteration limit is typically not reached, thus the combined
method is practically equivalent to Howard's algorithm, while it
also ensures the strongly polynomial time bound.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r1165 r1179  
    3636#include <lemon/bellman_ford.h>
    3737#include <lemon/howard_mmc.h>
     38#include <lemon/hartmann_orlin_mmc.h>
    3839
    3940namespace lemon {
     
    928929    // Execute the "Minimum Mean Cycle Canceling" method
    929930    void startMinMeanCycleCanceling() {
    930       typedef SimplePath<StaticDigraph> SPath;
     931      typedef Path<StaticDigraph> SPath;
    931932      typedef typename SPath::ArcIt SPathArcIt;
    932933      typedef typename HowardMmc<StaticDigraph, CostArcMap>
    933         ::template SetPath<SPath>::Create MMC;
     934        ::template SetPath<SPath>::Create HwMmc;
     935      typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap>
     936        ::template SetPath<SPath>::Create HoMmc;
     937
     938      const double HW_ITER_LIMIT_FACTOR = 1.0;
     939      const int HW_ITER_LIMIT_MIN_VALUE = 5;
     940
     941      const int hw_iter_limit =
     942          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
     943                   HW_ITER_LIMIT_MIN_VALUE);
    934944
    935945      SPath cycle;
    936       MMC mmc(_sgr, _cost_map);
    937       mmc.cycle(cycle);
     946      HwMmc hw_mmc(_sgr, _cost_map);
     947      hw_mmc.cycle(cycle);
    938948      buildResidualNetwork();
    939       while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
    940         // Find the cycle
    941         mmc.findCycle();
    942 
     949      while (true) {
     950       
     951        typename HwMmc::TerminationCause hw_tc =
     952            hw_mmc.findCycleMean(hw_iter_limit);
     953        if (hw_tc == HwMmc::ITERATION_LIMIT) {
     954          // Howard's algorithm reached the iteration limit, start a
     955          // strongly polynomial algorithm instead
     956          HoMmc ho_mmc(_sgr, _cost_map);
     957          ho_mmc.cycle(cycle);
     958          // Find a minimum mean cycle (Hartmann-Orlin algorithm)
     959          if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break;
     960          ho_mmc.findCycle();
     961        } else {
     962          // Find a minimum mean cycle (Howard algorithm)
     963          if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break;
     964          hw_mmc.findCycle();
     965        }
     966       
    943967        // Compute delta value
    944968        Value delta = INF;
     
    965989      const double LIMIT_FACTOR = 1.0;
    966990      const int MIN_LIMIT = 5;
     991      const double HW_ITER_LIMIT_FACTOR = 1.0;
     992      const int HW_ITER_LIMIT_MIN_VALUE = 5;
     993
     994      const int hw_iter_limit =
     995          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
     996                   HW_ITER_LIMIT_MIN_VALUE);
    967997
    968998      // Contruct auxiliary data vectors
     
    11381168          }
    11391169        } else {
    1140           typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
     1170          typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc;
     1171          typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc;
    11411172          typedef typename BellmanFord<StaticDigraph, CostArcMap>
    11421173            ::template SetDistMap<CostNodeMap>::Create BF;
    11431174
    11441175          // Set epsilon to the minimum cycle mean
     1176          Cost cycle_cost = 0;
     1177          int cycle_size = 1;
    11451178          buildResidualNetwork();
    1146           MMC mmc(_sgr, _cost_map);
    1147           mmc.findCycleMean();
    1148           epsilon = -mmc.cycleMean();
    1149           Cost cycle_cost = mmc.cycleCost();
    1150           int cycle_size = mmc.cycleSize();
     1179          HwMmc hw_mmc(_sgr, _cost_map);
     1180          if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) {
     1181            // Howard's algorithm reached the iteration limit, start a
     1182            // strongly polynomial algorithm instead
     1183            HoMmc ho_mmc(_sgr, _cost_map);
     1184            ho_mmc.findCycleMean();
     1185            epsilon = -ho_mmc.cycleMean();
     1186            cycle_cost = ho_mmc.cycleCost();
     1187            cycle_size = ho_mmc.cycleSize();
     1188          } else {
     1189            // Set epsilon
     1190            epsilon = -hw_mmc.cycleMean();
     1191            cycle_cost = hw_mmc.cycleCost();
     1192            cycle_size = hw_mmc.cycleSize();
     1193          }
    11511194
    11521195          // Compute feasible potentials for the current epsilon
Note: See TracChangeset for help on using the changeset viewer.