Changeset 30
 Timestamp:
 Aug 28, 2006 10:37:15 AM (13 years ago)
 Location:
 trunk/Bonmin/experimental/Bcp
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Bonmin/experimental/Bcp/BM.cpp
r28 r30 52 52 BCP_parameter(BCP_CharPar, PrintBranchingInfo))); 53 53 keys.push_back(make_pair(BCP_string("CombinedDistanceAndPriority"), 54 BCP_parameter(BCP_CharPar, CombinedDistanceAndPriority))); 55 keys.push_back(make_pair(BCP_string("LowPriorityImportant"), 56 BCP_parameter(BCP_CharPar, LowPriorityImportant))); 54 BCP_parameter(BCP_CharPar, 55 CombinedDistanceAndPriority))); 56 keys.push_back(make_pair(BCP_string("SosWithLowPriorityMoreImportant"), 57 BCP_parameter(BCP_CharPar, 58 SosWithLowPriorityMoreImportant))); 59 keys.push_back(make_pair(BCP_string("VarWithLowPriorityMoreImportant"), 60 BCP_parameter(BCP_CharPar, 61 VarWithLowPriorityMoreImportant))); 57 62 keys.push_back(make_pair(BCP_string("NumNlpFailureMax"), 58 63 BCP_parameter(BCP_IntPar, NumNlpFailureMax))); … … 69 74 set_entry(PrintBranchingInfo, true); 70 75 set_entry(CombinedDistanceAndPriority, true); 71 set_entry(LowPriorityImportant, true); 76 set_entry(SosWithLowPriorityMoreImportant, true); 77 set_entry(SosWithLowPriorityMoreImportant, true); 78 set_entry(VarWithLowPriorityMoreImportant, true); 72 79 set_entry(NumNlpFailureMax, 5); 73 80 set_entry(NL_filename, ""); … … 285 292 BM_lp::BM_lp() : 286 293 BCP_lp_user(), 294 sos(), 287 295 babSolver_(3), 288 296 nlp(), 289 sos(),290 297 feasChecker_(NULL), 291 298 in_strong(0) … … 302 309 delete[] primal_solution_; 303 310 delete[] branching_priority_; 311 for (int i = sos.size()  1; i >= 0; i) { 312 delete sos[i]; 313 } 304 314 } 305 315 … … 330 340 BCP_vec<double>& cut_new_bd) 331 341 { 342 int i; 332 343 // First copy the bounds into nlp. That way all the branching decisions 333 344 // will be transferred over. 345 for (i = sos.size()  1; i >= 0; i) { 346 sos[i]>first = 0; 347 sos[i]>last = sos[i]>length; 348 } 334 349 OsiSolverInterface * osi = getLpProblemPointer()>lp_solver; 335 const int numCols = nlp.getNumCols();350 const int numCols = osi>getNumCols(); 336 351 const double* clb = osi>getColLower(); 337 352 const double* cub = osi>getColUpper(); 338 for (i nt i= 0; i < numCols; ++i) {353 for (i = 0; i < numCols; ++i) { 339 354 const BCP_var_core* v = 340 355 dynamic_cast<const BCP_var_core*>(vars[i]); … … 349 364 const int ind = bv>sos_index; 350 365 const int split = bv>split; 351 const int len = sos.lengths[ind]; 352 const char type = sos.types[ind]; 353 const int *indices = sos.indices[ind]; 366 const char type = sos[ind]>type; 367 const int *indices = sos[ind]>indices; 354 368 if (bv>ub() == 0.0) { 355 for (int j = split + type; j < len; ++j) { 369 const int last = sos[ind]>last; 370 for (int j = split + type; j < last; ++j) { 356 371 nlp.setColLower(indices[j], 0.0); 357 372 nlp.setColUpper(indices[j], 0.0); 358 373 } 374 sos[ind]>last = split + type; 359 375 } else { 360 for (int j = 0; j < split; ++j) { 376 const int first = sos[ind]>first; 377 for (int j = first; j < split; ++j) { 361 378 nlp.setColLower(indices[j], 0.0); 362 379 nlp.setColUpper(indices[j], 0.0); 363 380 } 381 sos[ind]>first = split; 364 382 } 365 383 continue; … … 404 422 nlp.initialSolve(); 405 423 if (nlp.isProvenOptimal()) { 424 const int numCols = nlp.getNumCols(); 406 425 lower_bound_ = nlp.getObjValue(); 407 CoinDisjointCopyN(nlp.getColSolution(), vars.size(), 408 primal_solution_); 426 CoinDisjointCopyN(nlp.getColSolution(), numCols, primal_solution_); 409 427 numNlpFailed_ = 0; 410 428 Ipopt::SmartPtr<Ipopt::OptionsList> options = nlp.retrieve_options(); … … 412 430 options>GetNumericValue("integer_tolerance",intTol,"bonmin."); 413 431 414 const int numCols = nlp.getNumCols();415 432 int i; 416 433 for (i = 0; i < numCols; ++i) { … … 440 457 lower_bound_ = 1e200; 441 458 numNlpFailed_ = 0; 459 printf("\ 460 BM_lp: At node %i : will fathom because of infeasibility\n", 461 current_index()); 442 462 } 443 463 else if (nlp.isAbandoned()) { … … 465 485 nlp.retrieve_options()>GetNumericValue("integer_tolerance", 466 486 integerTolerance,"bonmin."); 467 nlp.retrieve_options()>GetNumericValue("cutoff_incr", 487 /* FIXME: cutoff_decr was called cutoff_incr??? */ 488 nlp.retrieve_options()>GetNumericValue("cutoff_decr", 468 489 cutOffIncrement,"bonmin."); 469 490 OsiSolverInterface * osi = getLpProblemPointer()>lp_solver; … … 607 628 double cutoffIncr; 608 629 options>GetNumericValue("integer_tolerance", intTol, "bonmin."); 609 options>GetNumericValue("cutoff_ incr", cutoffIncr, "bonmin.");630 options>GetNumericValue("cutoff_decr", cutoffIncr, "bonmin."); 610 631 611 632 if (lower_bound_ >= upper_bound() + cutoffIncr) { … … 619 640 } 620 641 621 if (par.entry(BM_par::BranchOnSos) && sos. num> 0) {642 if (par.entry(BM_par::BranchOnSos) && sos.size() > 0) { 622 643 double bestval = 2.0; 623 644 int bestsos = 1; 624 645 int bestsplit = 1; 625 646 int bestprio = 0; 626 for (int i = 0; i < sos.num; ++i) { 627 const int ind = sos.priority_order[i]; 628 const int prio = sos.priorities[ind]; 647 for (size_t ind = 0; ind < sos.size(); ++ind) { 648 const BmSosInfo& sosi = *sos[ind]; 649 const int prio = sosi.priority; 650 const int type = sosi.type; 651 if ((type == 0 && par.entry(BM_par::BranchOnSos) == 2)  652 (type == 1 && par.entry(BM_par::BranchOnSos) == 1)) 653 continue; 629 654 if (bestsos >= 0 && prio != bestprio) 630 655 break; 631 const int len = sos.lengths[ind]; 632 const int *indices = sos.indices[ind]; 656 const int first = sosi.first; 657 const int last = sosi.last; 658 const int *indices = sosi.indices; 633 659 // First count how many nonzeros are there 634 660 int cnt = 0; 635 for (int j = 0; j < len; ++j) {661 for (int j = first; j < last; ++j) { 636 662 const double prim_i = primal_solution_[indices[j]]; 637 663 if (prim_i > intTol && prim_i < 1intTol) { … … 641 667 // For type1 there can be at most 1, for type2 at most 2 nonzeros 642 668 // Find the next sos if this is satisfied. 643 const int type = sos.types[ind];644 669 if (cnt <= 1+type) 645 670 continue; … … 649 674 double val = 0.0; 650 675 double primal = 0.0; 651 for (half = 0; half < len; ++half) {676 for (half = first; half < last; ++half) { 652 677 val = primal_solution_[indices[half]]; 653 678 primal += val; … … 664 689 665 690 /* The branches will be as follows: 666 type1 : [ 0,half) and [half,len)667 type2 : [ 0,half) and (half,len)668 So if half== 0then it must be incremented,669 and also for type 2 if half==l en1 then it must be decremented.691 type1 : [first,half) and [half,last) 692 type2 : [first,half) and (half,last) 693 So if half==first then it must be incremented, 694 and also for type 2 if half==last1 then it must be decremented. 670 695 */ 671 if (half == 0)696 if (half == first) 672 697 ++half; 673 if (type == 1 && half == l en1)698 if (type == 1 && half == last1) 674 699 half; 675 700 … … 700 725 NULL,NULL,NULL,NULL)); 701 726 if (par.entry(BM_par::PrintBranchingInfo)) { 702 printf("BM_lp: branching on SOS #%i (type %i) split at: %i\n", 703 bestsos, sos.types[bestsos]+1, bestsplit); 727 printf("\ 728 BM_lp: At node %i branching on SOS%i set %i split at: %i with val: %f\n", 729 current_index(), sos[bestsos]>type+1, 730 bestsos, bestsplit, bestval); 704 731 } 705 732 return BCP_DoBranch;; … … 773 800 //############################################################################# 774 801 775 BM_lp::BmSosInfo::~BmSosInfo() 776 { 777 if (num > 0) { 778 for (int i = 0; i < num; ++i) { 779 delete[] indices[i]; 780 delete[] weights[i]; 781 } 782 delete[] indices; 783 delete[] weights; 784 delete[] types; 785 delete[] lengths; 786 delete[] priority_order; 787 } 788 } 789 802 BM_lp::BmSosInfo::BmSosInfo(const TMINLP::SosInfo * sosinfo, int i) 803 { 804 priority = sosinfo>priorities ? sosinfo>priorities[i] : 0; 805 length = sosinfo>starts[i+1]  sosinfo>starts[i]; 806 type = sosinfo>types[i] == 1 ? 0 : 1; 807 indices = new int[length]; 808 weights = new double[length]; 809 first = 0; 810 last = length; 811 CoinDisjointCopyN(sosinfo>indices+sosinfo>starts[i], length, indices); 812 CoinDisjointCopyN(sosinfo>weights+sosinfo>starts[i], length, weights); 813 CoinSort_2(weights, weights+length, indices); 814 } 815 790 816 /**/ 791 817 792 void BM_lp:: BmSosInfo::setFrom(const TMINLP::SosInfo * sos)793 { 794 if (!sos  sos>num == 0)818 void BM_lp::setSosFrom(const TMINLP::SosInfo * sosinfo) 819 { 820 if (!sosinfo  sosinfo>num == 0) 795 821 return; 796 822 797 823 //we have some sos constraints 798 num = sos>num; 799 priority_order = new int[num]; 800 CoinIotaN(priority_order, num, 0); 801 priorities = new int[num]; 802 if (sos>priorities) { 803 CoinDisjointCopyN(sos>priorities, num, priorities); 824 sos.reserve(sosinfo>num); 825 for (int i = 0; i < sosinfo>num; ++i) { 826 sos.push_back(new BmSosInfo(sosinfo, i)); 827 } 828 829 if (sosinfo>priorities) { 830 int * priorities = new int[sosinfo>num]; 831 CoinDisjointCopyN(sosinfo>priorities, sosinfo>num, priorities); 804 832 /* FIXME: we may need to go down in order! */ 805 CoinSort_2(priorities, priorities+num, priority_order); 806 } else { 807 CoinFillN(priorities, num, 0); 808 } 809 810 lengths = new int[num]; 811 types = new int[num]; 812 indices = new int*[num]; 813 weights = new double*[num]; 814 815 for (int i = 0; i < num; ++i) { 816 lengths[i] = sos>starts[i+1]  sos>starts[i]; 817 types[i] = sos>types[i] == 1 ? 0 : 1;; 818 indices[i] = new int[lengths[i]]; 819 weights[i] = new double[lengths[i]]; 820 CoinDisjointCopyN(sos>indices+sos>starts[i], lengths[i], indices[i]); 821 CoinDisjointCopyN(sos>weights+sos>starts[i], lengths[i], weights[i]); 822 CoinSort_2(weights[i], weights[i]+lengths[i], indices[i]); 833 if (par.entry(BM_par::SosWithLowPriorityMoreImportant)) { 834 CoinSort_2(priorities, priorities+sosinfo>num, &sos[0], 835 std::less<int>()); 836 } else { 837 CoinSort_2(priorities, priorities+sosinfo>num, &sos[0], 838 std::greater<int>()); 839 } 840 delete[] priorities; 823 841 } 824 842 } … … 826 844 /**/ 827 845 846 #if 0 828 847 void BM_lp::BmSosInfo::shuffle() 829 848 { … … 841 860 } 842 861 } 862 #endif 843 863 844 864 //############################################################################# 
trunk/Bonmin/experimental/Bcp/BM.hpp
r28 r30 49 49 PureBranchAndBound, 50 50 PrintBranchingInfo, 51 LowPriorityImportant, 51 SosWithLowPriorityMoreImportant, 52 VarWithLowPriorityMoreImportant, 52 53 end_of_chr_params 53 54 }; … … 156 157 { 157 158 struct BmSosInfo { 158 int num; 159 int *priority_order; 160 int *lengths; 161 int *types; // 0: type 1  1: type 2 162 int *priorities; 163 int **indices; 164 double **weights; 165 BmSosInfo() : num(0) {} 166 ~BmSosInfo(); 167 void setFrom(const TMINLP::SosInfo * sos); 168 void shuffle(); 169 }; 159 int length; 160 int type; // 0: type 1  1: type 2 161 int priority; 162 int *indices; 163 double *weights; 164 int first; 165 int last; 166 BmSosInfo(const TMINLP::SosInfo * sosinfo, int i); 167 ~BmSosInfo() { 168 delete[] indices; 169 delete[] weights; 170 } 171 }; 172 std::vector<BmSosInfo*> sos; 173 void setSosFrom(const TMINLP::SosInfo * sosinfo); 170 174 171 175 BCP_string ipopt_file_content; … … 175 179 OsiBabSolver babSolver_; 176 180 BonminAmplInterface nlp; 177 BmSosInfo sos;178 181 179 182 double lower_bound_; 
trunk/Bonmin/experimental/Bcp/BM_pack.cpp
r1 r30 78 78 double bm_cutoffIncr; // could be negative 79 79 options>GetNumericValue("integer_tolerance",bm_intTol,"bonmin."); 80 options>GetNumericValue("cutoff_ incr",bm_cutoffIncr,"bonmin.");80 options>GetNumericValue("cutoff_decr",bm_cutoffIncr,"bonmin."); 81 81 82 82 BCP_lp_prob* bcp_lp = getLpProblemPointer(); … … 121 121 /* SOS constraints */ 122 122 if (par.entry(BM_par::BranchOnSos)) { 123 s os.setFrom(nlp.model()>sosConstraints());123 setSosFrom(nlp.model()>sosConstraints()); 124 124 } 125 125 … … 134 134 if (prio == NULL) { 135 135 // No. Just sett all of them uniformly to 1.0 136 for (i = 0; i < numCols; ++i) 137 { 138 branching_priority_[i] = 1.0; 139 } 140 } 141 else { 136 for (i = 0; i < numCols; ++i) { 137 branching_priority_[i] = 1.0; 138 } 139 } else { 142 140 /* Yes! the lower the number the earlier we want to branch on it. 143 141 Let's see how many different numbers there are */ 144 142 std::set<int> numbers; 145 for (i = 0; i < numCols; ++i) 146 { 147 numbers.insert(prio[i]); 148 } 143 for (i = 0; i < numCols; ++i) { 144 numbers.insert(prio[i]); 145 } 149 146 if (numbers.size() > 15) { 150 /* Sigh... too many... We just have to trust the user's knowledge */ 147 /* Sigh... too many... We just have to trust the user's 148 knowledge */ 151 149 if (par.entry(BM_par::CombinedDistanceAndPriority) == true) { 152 150 printf("WARNING!\n"); … … 166 164 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14}; 167 165 const double* powers = 168 par.entry(BM_par::LowPriorityImportant) ? powerup : powerdo; 169 for (i = 0; i < numCols; ++i) 170 { 171 const int pos = coinDistance(numbers.begin(), numbers.find(prio[i])); 172 assert (pos >= 0 && pos < 15); 173 branching_priority_[i] = powers[pos]; 166 par.entry(BM_par::VarWithLowPriorityMoreImportant) ? powerup : powerdo; 167 for (i = 0; i < numCols; ++i) { 168 const int pos = coinDistance(numbers.begin(), numbers.find(prio[i])); 169 assert (pos >= 0 && pos < 15); 170 branching_priority_[i] = powers[pos]; 171 } 172 } else { 173 if (par.entry(BM_par::VarWithLowPriorityMoreImportant)) { 174 const double maxprio = *numbers.rbegin(); 175 for (i = 0; i < numCols; ++i) { 176 branching_priority_[i] = maxprio  prio[i]; 174 177 } 175 } 176 else { 177 if (par.entry(BM_par::LowPriorityImportant)) { 178 const double maxprio = *numbers.rbegin(); 179 for (i = 0; i < numCols; ++i) 180 { 181 branching_priority_[i] = maxprio  prio[i]; 182 } 183 } 184 else { 185 for (i = 0; i < numCols; ++i) 186 { 187 branching_priority_[i] = prio[i]; 188 } 178 } else { 179 for (i = 0; i < numCols; ++i) { 180 branching_priority_[i] = prio[i]; 181 } 189 182 } 190 183 }
Note: See TracChangeset
for help on using the changeset viewer.