Changeset 5518
 Timestamp:
 08/22/08 14:12:10 (6 years ago)
 Location:
 pico/trunk/src/milp/pico
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

pico/trunk/src/milp/pico/feasibilityPump.cpp
r5274 r5518 23 23 24 24 // comparison function used in std::sort call found below. 25 // sorts in decreasing order. 25 26 bool compareDists(const std::pair<double,int> & a, 26 27 const std::pair<double,int> & b) … … 105 106 "Feasibility Pump Heuristic"); 106 107 107 FPImprovementAlpha = 0. 15;108 FPImprovementAlpha = 0.50; 108 109 ParameterSet::create_categorized_parameter("FPImprovementAlpha",FPImprovementAlpha, 109 "<double>","0. 15",110 "<double>","0.50", 110 111 "When improving incumbents, the fraction of the absolute gap used to form the new objective cut", 111 112 "Feasibility Pump Heuristic"); 112 113 113 FP FlipCount = 20;114 ParameterSet::create_categorized_parameter("FP FlipCount",FPFlipCount,114 FPMeanFlipCount = 20; 115 ParameterSet::create_categorized_parameter("FPMeanFlipCount",FPMeanFlipCount, 115 116 "<int>","20", 116 "M aximum variables 'flipped' per feasibility pump iteration",117 "Mean number of variables 'flipped' per feasibility pump iteration, if rounded solution remains unchanged", 117 118 "Feasibility Pump Heuristic", 118 119 utilib::ParameterPositive<int>()); … … 172 173 int cumulative_iterations(0); 173 174 int allowable_iterations; 174 if (currentDepth == 1) 175 if (currentDepth == 1) // depth is 1based in PICO/PEBBL. 175 176 { 176 177 allowable_iterations = FPRootIterations; … … 180 181 allowable_iterations = FPInteriorIterations; 181 182 } 183 184 int num_vars(lp>getNumCols()); 182 185 183 186 // verify that any integer variables are in fact binary  the current 184 187 // code doesn't deal with the general integer case, as that's more 185 188 // than a bit of pain. 186 for (int i = 0; i < lp>getNumCols(); ++i)189 for (int i = 0; i < num_vars; ++i) 187 190 { 188 191 if ((lp>isContinuous(i) == false) && … … 195 198 } 196 199 } 197 198 int num_vars(lp>getNumCols());199 200 200 201 DEBUGPR(50, ucout << "Limit on number of feasibility pump meta iterations=" … … 256 257 if (lp>isContinuous(i) == true) 257 258 { 258 initial_solution[i] = 0.0; // isn't usedanyway259 initial_solution[i] = 0.0; // isn't manipulated by FP anyway 259 260 } 260 261 else … … 311 312 // better solutions are found  assuming incumbent improvement 312 313 // is enabled. 313 int num_vars(fp_solver_interface>getNumCols());314 // NOTE: does milpNode or the base heuristic already add the objective cut? 314 315 const double * obj_coeffs = fp_solver_interface>getObjCoefficients(); 315 316 CoinPackedVector objective_cut(num_vars, obj_coeffs); … … 432 433 bool incumbent_found(false); 433 434 bool time_limited(false); // upon exit, is it due to time limiation? 434 bool iteration_limited(false); // upon exi st, is it due to iteration limitation?435 bool iteration_limited(false); // upon exit, is it due to iteration limitation? 435 436 int iteration_feasible_found(std::numeric_limits<int>::min()); 436 437 438 // the following is for reporting purposes only, and won't be triggered 439 // without some real weird inputs. 437 440 if (allocated_iterations == 0) 438 441 { … … 461 464 else // for now, we assume all integers are binary 462 465 { 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. 464 467 { 465 468 fp_solver_interface>setObjCoeff(j, 1.0); … … 484 487 DEBUGPR(100, prettyPrint("X~ solution", x_tilde, num_vars, ucout)); 485 488 486 // compute the distance between the new x* and the old x~489 // compute the L1norm distance between the new x* and the old x~ 487 490 double dist(0.0); 488 491 for (int j = 0; j < num_vars; ++j) … … 497 500 498 501 // NOTE: The solution can still be integerfeasible, although the 499 // distance is > 0. weird, but true. 502 // distance is > 0. weird, but true. due to tolerances. 500 503 501 504 // see if the resulting solution is integer. … … 587 590 else 588 591 { 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. 592 594 bool any_inverted(false); 593 595 unsigned int num_rounded_down(0); 594 596 unsigned int num_rounded_up(0); 595 RNG * rng = pebbl::gRandomRNG();596 Uniform sampler(rng, 0.0, 1.0);597 597 for (int j = 0; j < num_vars; ++j) 598 598 { … … 601 601 if (bGlobal>isInteger(new_solution[j]) == false) 602 602 { 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]); 620 604 if (rounded_value != x_tilde[j]) 621 605 { … … 645 629 // flip some number of variables with the highest 646 630 // value of abs(x*  x~). 647 DEBUGPR(100, ucout << "Mean flip count=" << FP FlipCount << std::endl << Flush);631 DEBUGPR(100, ucout << "Mean flip count=" << FPMeanFlipCount << std::endl << Flush); 648 632 649 633 // compute x*  x~ for each variable and sort in descending order. … … 664 648 RNG * rng = pebbl::gRandomRNG(); 665 649 DUniform<int> sampler(rng, 666 int(floor(double(FPFlipCount)/2.0)),667 int(ceil(3.0*double(FP FlipCount)/2.0)));650 std::max(int(floor(double(FPMeanFlipCount)/2.0)),1), 651 int(ceil(3.0*double(FPMeanFlipCount)/2.0))); 668 652 669 653 int num_to_flip = sampler(); 
pico/trunk/src/milp/pico/feasibilityPump.h
r5254 r5518 27 27 private: 28 28 29 // the debug level specific to the feasibility pump.29 // the debug output level specific to the feasibility pump. 30 30 // defaults to 0. 31 31 int FPDebug; … … 40 40 41 41 // how many iterations of the feasibility pump should be executed at "interior" nodes? 42 // defaults to 50. 42 43 int FPInteriorIterations; 43 44 … … 52 53 // the mean number of variables to invert in each feasibility pump iteration 53 54 // default is 20. 54 int FP FlipCount;55 int FPMeanFlipCount; 55 56 56 57 // 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. 58 59 bool FPImproveIncumbent; 59 60 60 61 // when forming the new objective bound, by what fraction of the 61 62 // 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. 63 64 double FPImprovementAlpha; 64 65
Note: See TracChangeset
for help on using the changeset viewer.