Changeset 5518


Ignore:
Timestamp:
08/22/08 14:12:10 (6 years ago)
Author:
jwatson
Message:

Some minor structural changes and cleanup to the feasibility pump code base.

Location:
pico/trunk/src/milp/pico
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • pico/trunk/src/milp/pico/feasibilityPump.cpp

    r5274 r5518  
    2323 
    2424// comparison function used in std::sort call found below. 
     25// sorts in decreasing order. 
    2526bool compareDists(const std::pair<double,int> & a, 
    2627                  const std::pair<double,int> & b) 
     
    105106                                               "Feasibility Pump Heuristic"); 
    106107 
    107     FPImprovementAlpha = 0.15; 
     108    FPImprovementAlpha = 0.50; 
    108109    ParameterSet::create_categorized_parameter("FPImprovementAlpha",FPImprovementAlpha, 
    109                                                "<double>","0.15", 
     110                                               "<double>","0.50", 
    110111                                               "When improving incumbents, the fraction of the absolute gap used to form the new objective cut", 
    111112                                               "Feasibility Pump Heuristic"); 
    112113 
    113     FPFlipCount = 20; 
    114     ParameterSet::create_categorized_parameter("FPFlipCount",FPFlipCount, 
     114    FPMeanFlipCount = 20; 
     115    ParameterSet::create_categorized_parameter("FPMeanFlipCount",FPMeanFlipCount, 
    115116                                               "<int>","20", 
    116                                                "Maximum variables 'flipped' per feasibility pump iteration", 
     117                                               "Mean number of variables 'flipped' per feasibility pump iteration, if rounded solution remains unchanged", 
    117118                                               "Feasibility Pump Heuristic", 
    118119                                               utilib::ParameterPositive<int>()); 
     
    172173    int cumulative_iterations(0); 
    173174    int allowable_iterations; 
    174     if (currentDepth == 1) 
     175    if (currentDepth == 1) // depth is 1-based in PICO/PEBBL. 
    175176      { 
    176177        allowable_iterations = FPRootIterations; 
     
    180181        allowable_iterations = FPInteriorIterations; 
    181182      } 
     183 
     184    int num_vars(lp->getNumCols()); 
    182185 
    183186    // verify that any integer variables are in fact binary - the current 
    184187    // code doesn't deal with the general integer case, as that's more  
    185188    // than a bit of pain. 
    186     for (int i = 0; i < lp->getNumCols(); ++i) 
     189    for (int i = 0; i < num_vars; ++i) 
    187190      { 
    188191        if ((lp->isContinuous(i) == false) && 
     
    195198          } 
    196199      } 
    197  
    198     int num_vars(lp->getNumCols()); 
    199200 
    200201    DEBUGPR(50, ucout << "Limit on number of feasibility pump meta iterations="  
     
    256257                if (lp->isContinuous(i) == true) 
    257258                  { 
    258                     initial_solution[i] = 0.0; // isn't used anyway 
     259                    initial_solution[i] = 0.0; // isn't manipulated by FP anyway 
    259260                  } 
    260261                else 
     
    311312        // better solutions are found - assuming incumbent improvement 
    312313        // is enabled. 
    313         int num_vars(fp_solver_interface->getNumCols()); 
     314        // NOTE: does milpNode or the base heuristic already add the objective cut? 
    314315        const double * obj_coeffs = fp_solver_interface->getObjCoefficients(); 
    315316        CoinPackedVector objective_cut(num_vars, obj_coeffs); 
     
    432433    bool incumbent_found(false); 
    433434    bool time_limited(false); // upon exit, is it due to time limiation? 
    434     bool iteration_limited(false); // upon exist, is it due to iteration limitation? 
     435    bool iteration_limited(false); // upon exit, is it due to iteration limitation? 
    435436    int iteration_feasible_found(std::numeric_limits<int>::min()); 
    436437 
     438    // the following is for reporting purposes only, and won't be triggered 
     439    // without some real weird inputs. 
    437440    if (allocated_iterations == 0) 
    438441      { 
     
    461464            else // for now, we assume all integers are binary 
    462465              { 
    463                 if (x_tilde[j] == 0) 
     466                if (x_tilde[j] == 0) // the rounded variables should be exactly equal to 0 (which is representable), so tolerances shouldn't be an issue. 
    464467                  { 
    465468                    fp_solver_interface->setObjCoeff(j, 1.0); 
     
    484487        DEBUGPR(100, prettyPrint("X~ solution", x_tilde, num_vars, ucout)); 
    485488 
    486         // compute the distance between the new x* and the old x~ 
     489        // compute the L1-norm distance between the new x* and the old x~ 
    487490        double dist(0.0); 
    488491        for (int j = 0; j < num_vars; ++j) 
     
    497500 
    498501        // NOTE: The solution can still be integer-feasible, although the 
    499         //       distance is > 0. weird, but true. 
     502        //       distance is > 0. weird, but true. due to tolerances. 
    500503 
    501504        // see if the resulting solution is integer. 
     
    587590            else 
    588591              { 
    589                 // construct the next x tilde. first pass is to see if rounding 
    590                 // of any x* variables yields new values for the corresponding  
    591                 // x~ variables.  
     592                // construct the next x tilde. first pass is to see if rounding of  
     593                // any x* variables yields new values for the corresponding x~ variables.  
    592594                bool any_inverted(false); 
    593595                unsigned int num_rounded_down(0); 
    594596                unsigned int num_rounded_up(0); 
    595                 RNG * rng = pebbl::gRandomRNG(); 
    596                 Uniform sampler(rng, 0.0, 1.0); 
    597597                for (int j = 0; j < num_vars; ++j) 
    598598                  { 
     
    601601                        if (bGlobal->isInteger(new_solution[j]) == false) 
    602602                          { 
    603                             double rounded_value; 
    604                             //                      if ((new_solution[j] >= 0.40) && 
    605                             //                          (new_solution[j] <= 0.60)) 
    606                             //                        { 
    607                             //                          if (sampler() <= 0.5) 
    608                             //                            { 
    609                             //                              rounded_value = std::floor(new_solution[j]); 
    610                             //                            } 
    611                             //                          else 
    612                             //                            { 
    613                             //                              rounded_value = std::ceil(new_solution[j]); 
    614                             //                            } 
    615                             //                        } 
    616                             //                      else 
    617                             //                        { 
    618                                 rounded_value = rint(new_solution[j]); 
    619                                 //                            } 
     603                            double rounded_value = rint(new_solution[j]); 
    620604                            if (rounded_value != x_tilde[j]) 
    621605                              { 
     
    645629                    // flip some number of variables with the highest 
    646630                    // value of abs(x* - x~). 
    647                     DEBUGPR(100, ucout << "Mean flip count=" << FPFlipCount << std::endl << Flush); 
     631                    DEBUGPR(100, ucout << "Mean flip count=" << FPMeanFlipCount << std::endl << Flush); 
    648632 
    649633                    // compute |x* - x~| for each variable and sort in descending order. 
     
    664648                    RNG * rng = pebbl::gRandomRNG(); 
    665649                    DUniform<int> sampler(rng, 
    666                                           int(floor(double(FPFlipCount)/2.0)), 
    667                                           int(ceil(3.0*double(FPFlipCount)/2.0))); 
     650                                          std::max(int(floor(double(FPMeanFlipCount)/2.0)),1), 
     651                                          int(ceil(3.0*double(FPMeanFlipCount)/2.0))); 
    668652 
    669653                    int num_to_flip = sampler(); 
  • pico/trunk/src/milp/pico/feasibilityPump.h

    r5254 r5518  
    2727    private: 
    2828       
    29       // the debug level specific to the feasibility pump. 
     29      // the debug output level specific to the feasibility pump. 
    3030      // defaults to 0. 
    3131      int FPDebug; 
     
    4040 
    4141      // how many iterations of the feasibility pump should be executed at "interior" nodes? 
     42      // defaults to 50. 
    4243      int FPInteriorIterations;  
    4344       
     
    5253      // the mean number of variables to invert in each feasibility pump iteration 
    5354      // default is 20. 
    54       int FPFlipCount;  
     55      int FPMeanFlipCount;  
    5556 
    5657      // once a feasible incumbent is found, do I continue to expend energy 
    57       // trying to improve it? default is false. 
     58      // trying to improve it? default is true. 
    5859      bool FPImproveIncumbent; 
    5960 
    6061      // when forming the new objective bound, by what fraction of the 
    6162      // absolute gap (relative to the LP relaxation) do I set the  
    62       // new objective cut. default is set to 0.15. 
     63      // new objective cut. default is set to 0.50. 
    6364      double FPImprovementAlpha;  
    6465 
Note: See TracChangeset for help on using the changeset viewer.