Changeset 5589


Ignore:
Timestamp:
09/20/08 21:39:44 (6 years ago)
Author:
jwatson
Message:

Added a simple randomized rounding component to FP, which rounds - in the process of forming the x-tilde vector - any
integer variable with a fractional component on [0.33,0.67] to 0 or 1 with equal probability. Eventually will promote
the 0.33/0.67 parameters to FP command-line parameters, but only once I flush out issues with the new scheme.

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

Legend:

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

    r5588 r5589  
    2323#include <limits> 
    2424 
     25#include <math.h> 
    2526#include <assert.h> 
    2627 
     
    121122                                               "Feasibility Pump Heuristic", 
    122123                                               utilib::ParameterPositive<int>()); 
     124 
     125    FPRoundingType = 0; 
     126    ParameterSet::create_categorized_parameter("FPRoundingType",FPRoundingType, 
     127                                               "<int>","0", 
     128                                               "The type of rounding used by FP to form a new x~ target vector from the current LP solution x*. 0 indicates standard deterministic. 1 indicates randomized rounding around the interval [0.33, 0.66]", 
     129                                               "Feasibility Pump Heuristic", 
     130                                               utilib::ParameterPositive<int>()); 
     131 
    123132  } 
    124133 
     
    168177    // IMPT: have to un-do on the way out. 
    169178    lp->setCutting(); 
     179 
     180    // verify that the rounding type is set to a sane value. 
     181    if (FPRoundingType >= 2) 
     182      { 
     183        DEBUGPR(10, ucout << "***WARNING: FPRoundingType parameter has an unknown value=" << FPRoundingType << std::endl << Flush); 
     184        return 0; 
     185      } 
    170186 
    171187    DEBUGPR(100, ucout << "-----------------------------------------------" << std::endl << Flush); 
     
    418434  } 
    419435 
     436  bool feasibilityPump::deterministicRounding(unsigned int & num_rounded_up, 
     437                                              unsigned int & num_rounded_down, 
     438                                              int num_vars, 
     439                                              const double * new_solution, 
     440                                              double * x_tilde)const 
     441  { 
     442    bool any_inverted = false; 
     443    num_rounded_down = 0; 
     444    num_rounded_up = 0; 
     445    for (int j = 0; j < num_vars; ++j) 
     446      { 
     447        if (lp->isContinuous(j) == false) 
     448          { 
     449            if (bGlobal->isInteger(new_solution[j]) == false) 
     450              { 
     451                double rounded_value = rint(new_solution[j]); 
     452                if (fabs(rounded_value - x_tilde[j]) > 1e-5) // enough of a threshold, given comparison of integers. 
     453                  { 
     454                    any_inverted = true; 
     455                    x_tilde[j] = rounded_value; 
     456                     
     457                    // the following is simply for statistics. 
     458                    if (rounded_value <= new_solution[j])  
     459                      { 
     460                        ++num_rounded_down; 
     461                      } 
     462                    else 
     463                      { 
     464                        ++num_rounded_up; 
     465                      } 
     466 
     467                    // spit out the actual rounding information for debug/analysis purposes. 
     468                    if (verbosity(50) == true) 
     469                      { 
     470                        std::cout << "Rounded value=" << new_solution[j] << " to integral value=" << rounded_value << std::endl; 
     471                      } 
     472                  } 
     473              } 
     474          } 
     475      } 
     476 
     477    return any_inverted; 
     478  } 
     479 
     480  bool feasibilityPump::randomizedRounding(unsigned int & num_rounded_up, 
     481                                           unsigned int & num_rounded_down, 
     482                                           int num_vars, 
     483                                           const double * new_solution, 
     484                                           double * x_tilde)const 
     485  { 
     486    bool any_inverted = false; 
     487    num_rounded_down = 0; 
     488    num_rounded_up = 0; 
     489 
     490    RNG * rng = pebbl::gRandomRNG(); 
     491    Uniform sampler(rng, 0.0, 1.0);  
     492 
     493    for (int j = 0; j < num_vars; ++j) 
     494      { 
     495        if (lp->isContinuous(j) == false) 
     496          { 
     497            if (bGlobal->isInteger(new_solution[j]) == false) 
     498              { 
     499                // if you're <= 0.33 or >= 0.67 in the fractional component, 
     500                // perform deterministic rounding. otherweise, round with 
     501                // equal probability in one or the other direction. 
     502                double fractional_component(new_solution[j] - floor(new_solution[j])); 
     503                double rounded_value; 
     504                if (fractional_component < 0.33) 
     505                  { 
     506                    rounded_value = floor(new_solution[j]); 
     507                  } 
     508                else if (fractional_component > 0.67) 
     509                  { 
     510                    rounded_value = ceil(new_solution[j]);                   
     511                  } 
     512                else 
     513                  { 
     514                    if (sampler() <= 0.5) 
     515                      { 
     516                        rounded_value = floor(new_solution[j]); 
     517                      } 
     518                    else 
     519                      { 
     520                        rounded_value = ceil(new_solution[j]); 
     521                      } 
     522                  } 
     523 
     524                if (fabs(rounded_value - x_tilde[j]) > 1e-5) // enough of a threshold, given comparison of integers. 
     525                  { 
     526                    any_inverted = true; 
     527                    x_tilde[j] = rounded_value; 
     528                     
     529                    // the following is simply for statistics. 
     530                    if (fabs(rounded_value - floor(new_solution[j])) < 1e-5) 
     531                      { 
     532                        ++num_rounded_down; 
     533                      } 
     534                    else 
     535                      { 
     536                        ++num_rounded_up; 
     537                      } 
     538 
     539                    // spit out the actual rounding information for debug/analysis purposes. 
     540                    if (verbosity(50) == true) 
     541                      { 
     542                        std::cout << "Rounded value=" << new_solution[j] << " to integral value=" << rounded_value << std::endl; 
     543                      } 
     544                  } 
     545              } 
     546          } 
     547      } 
     548 
     549    return any_inverted; 
     550  } 
     551 
    420552  bool feasibilityPump::feasibilityPumpCore(OsiSolverInterface * fp_solver_interface, 
    421553                                            const double * initial_solution, 
     
    436568    consumed_runtime = 0.0; 
    437569 
     570    if (FPRoundingType == 0) 
     571      { 
     572        DEBUGPR(10, ucout << "Deterministic rounding enabled for feasibility pump" << std::endl << Flush); 
     573      } 
     574    else // (FPRoundingType == 1) 
     575      { 
     576        DEBUGPR(10, ucout << "Randomized rounding enabled for feasibility pump" << std::endl << Flush); 
     577      } 
     578 
    438579    // initialize the hash weights, which are used to detect cycles in the solution vector x tilde. 
    439580    std::vector<int> hash_weights(num_vars); 
     
    669810            else 
    670811              { 
    671                 // construct the next x tilde. first pass is to see if rounding of  
    672                 // any x* variables yields new values for the corresponding x~ variables.  
     812                // construct the next x tilde via any number of mechanisms, to see if rounding 
     813                // of any x* variables yields new values for the corresponding x~ variables. 
     814 
    673815                bool any_inverted(false); 
     816                unsigned int num_rounded_up(0); 
    674817                unsigned int num_rounded_down(0); 
    675                 unsigned int num_rounded_up(0); 
    676                 for (int j = 0; j < num_vars; ++j) 
    677                   { 
    678                     if (lp->isContinuous(j) == false) 
    679                       { 
    680                         if (bGlobal->isInteger(new_solution[j]) == false) 
    681                           { 
    682                             double rounded_value = rint(new_solution[j]); 
    683                             if (fabs(rounded_value - x_tilde[j]) > 1e-5) // enough of a threshold, given comparison of integers. 
    684                               { 
    685                                 any_inverted = true; 
    686                                 x_tilde[j] = rounded_value; 
    687  
    688                                 // the following is simply for statistics. 
    689                                 if (rounded_value <= new_solution[j])  
    690                                   { 
    691                                     ++num_rounded_down; 
    692                                   } 
    693                                 else 
    694                                   { 
    695                                     ++num_rounded_up; 
    696                                   } 
    697  
    698                                 // spit out the actual rounding information for debug/analysis purposes. 
    699                                 if (verbosity(50) == true) 
    700                                   { 
    701                                     std::cout << "Rounded value=" << new_solution[j] << " to integral value=" << rounded_value << std::endl; 
    702  
    703                                   } 
    704                               } 
    705                           } 
    706                       } 
     818 
     819                if (FPRoundingType == 0) 
     820                  { 
     821                    any_inverted = deterministicRounding(num_rounded_up,  
     822                                                         num_rounded_down, 
     823                                                         num_vars, 
     824                                                         new_solution, 
     825                                                         x_tilde); 
     826                  } 
     827                else // (FPRoundingType == 1) 
     828                  { 
     829                    any_inverted = randomizedRounding(num_rounded_up,  
     830                                                      num_rounded_down, 
     831                                                      num_vars, 
     832                                                      new_solution, 
     833                                                      x_tilde); 
    707834                  } 
    708835 
    709836                if (any_inverted == true) 
    710837                  { 
    711                     DEBUGPR(10, ucout << ", Deterministic flipping - " << num_rounded_down << " rounded down, " << num_rounded_up << " rounded up" << std::endl << Flush); 
     838                    DEBUGPR(10, ucout << ", Variables were inverted - " << num_rounded_down << " rounded down, " << num_rounded_up << " rounded up" << std::endl << Flush); 
    712839                  } 
    713840                else 
  • pico/trunk/src/milp/pico/feasibilityPump.h

    r5518 r5589  
    5151      bool FPRandomInitialSolution;  
    5252 
    53       // the mean number of variables to invert in each feasibility pump iteration 
     53      // the mean number of variables to invert in each feasibility pump iteration, 
     54      // assuming randomization doesn't change the xtilde vector. 
    5455      // default is 20. 
    5556      int FPMeanFlipCount;  
     
    6465      double FPImprovementAlpha;  
    6566 
     67      // what type of rounding do I do in FP to form the xtilde vector from 
     68      // the current x* vector? 0=deterministic, 1=randomized. no other 
     69      // options are currently defined. the default is 0. 
     70      int FPRoundingType; 
     71 
    6672      // do I execute at all? based on whether the current MILPNode is the root. 
    6773      bool executeFP; 
     
    7278 
    7379    protected: 
     80 
     81      // the original FP rounding scheme, which is deterministic. 
     82      bool deterministicRounding(unsigned int & num_rounded_up, 
     83                                 unsigned int & num_rounded_down, 
     84                                 int num_vars, 
     85                                 const double * new_solution, 
     86                                 double * x_tilde)const; 
     87 
     88      // modified FP rounding scheme, which randomly flips in one direction 
     89      // any integer variable with a x* value in the range [0.33,0.67]. all 
     90      // other variables are rounded deterministically. 
     91      bool randomizedRounding(unsigned int & num_rounded_up, 
     92                              unsigned int & num_rounded_down, 
     93                              int num_vars, 
     94                              const double * new_solution, 
     95                              double * x_tilde)const; 
     96 
    7497       
    7598      bool feasibilityPumpCore(OsiSolverInterface * fp_solver_interface, 
Note: See TracChangeset for help on using the changeset viewer.