00001
00002
00003
00004
00005
00006
00007
00008
00009 #include "CoinHelperFunctions.hpp"
00010 #include "BCP_lp_node.hpp"
00011 #include "BCP_lp.hpp"
00012 #include "BCP_lp_functions.hpp"
00013 #include "BM.hpp"
00014 #include "BonChooseVariable.hpp"
00015 #include "BonCurvBranchingSolver.hpp"
00016 #include "BonQpBranchingSolver.hpp"
00017 #include "BonLpBranchingSolver.hpp"
00018 #include "BonOsiTMINLPInterface.hpp"
00019 #include "BonIpoptWarmStart.hpp"
00020
00021 #ifndef BM_DEBUG_PRINT
00022 #define BM_DEBUG_PRINT 0
00023 #endif
00024
00025 static bool ifprint = true;
00026 static bool ifprint2 = false;
00027
00028
00029
00030 BCP_branching_decision
00031 BM_lp::select_branching_candidates(const BCP_lp_result& lpres,
00032 const BCP_vec<BCP_var*>& vars,
00033 const BCP_vec<BCP_cut*>& cuts,
00034 const BCP_lp_var_pool& local_var_pool,
00035 const BCP_lp_cut_pool& local_cut_pool,
00036 BCP_vec<BCP_lp_branching_object*>& cands,
00037 bool force_branch)
00038 {
00039
00040 bm_stats.incNumberNodeSolves();
00041
00042 Bonmin::OsiTMINLPInterface* nlp =
00043 dynamic_cast<Bonmin::OsiTMINLPInterface*>(getLpProblemPointer()->lp_solver);
00044
00045
00046 if (nlp) {
00047 if (lpres.termcode() & BCP_Abandoned) {
00048 if (nlp->isIterationLimitReached()) {
00049 print(ifprint, "\
00050 BM_lp: At node %i : WARNING: nlp reached iter limit. Will force branching\n",
00051 current_index());
00052 } else {
00053 print(ifprint, "\
00054 BM_lp: At node %i : WARNING: nlp is abandoned. Will force branching\n",
00055 current_index());
00056 }
00057
00058 nlp->forceBranchable();
00059 numNlpFailed_++;
00060 if (numNlpFailed_ >= par.entry(BM_par::NumNlpFailureMax)) {
00061 print(ifprint, "WARNING! Too many (%i) NLP failures in a row. Abandoning node.",
00062 numNlpFailed_);
00063 return BCP_DoNotBranch_Fathomed;
00064 }
00065 } else {
00066 numNlpFailed_ = 0;
00067 }
00068 }
00069
00070 OsiBranchingInformation brInfo(nlp, false, true);
00071 brInfo.cutoff_ = upper_bound() + get_param(BCP_lp_par::Granularity);
00072 brInfo.objectiveValue_ = lpres.objval();
00073 brInfo.integerTolerance_ = integerTolerance_;
00074 brInfo.timeRemaining_ = get_param(BCP_lp_par::MaxRunTime) - CoinCpuTime();
00075 brInfo.numberSolutions_ = 0;
00076 brInfo.numberBranchingSolutions_ = 0;
00077 brInfo.depth_ = current_level();
00078
00079 BCP_branching_decision brDecision;
00080 if (bonmin_.getAlgorithm() == 0) {
00081
00082 brDecision = bbBranch(brInfo, cands);
00083 } else {
00084 brDecision = hybridBranch();
00085 }
00086
00087 return brDecision;
00088 }
00089
00090
00091
00092 BCP_branching_decision
00093 BM_lp::hybridBranch()
00094 {
00095
00096 throw BCP_fatal_error("BM_lp: FIXME: make hybrid work...");
00097 }
00098
00099
00100
00101 void
00102 BM_lp::unpack_pseudo_costs(BCP_buffer& buf)
00103 {
00104 Bonmin::BonChooseVariable* choose =
00105 dynamic_cast<Bonmin::BonChooseVariable*>(bonmin_.branchingMethod());
00106 OsiPseudoCosts& pseudoCosts = choose->pseudoCosts();
00107 int numObj = pseudoCosts.numberObjects();
00108 double* upTotalChange = pseudoCosts.upTotalChange();
00109 int* upNumber = pseudoCosts.upNumber();
00110 double* downTotalChange = pseudoCosts.downTotalChange();
00111 int* downNumber = pseudoCosts.downNumber();
00112
00113 buf.unpack(upTotalChange, numObj, false);
00114 buf.unpack(upNumber, numObj, false);
00115 buf.unpack(downTotalChange, numObj, false);
00116 buf.unpack(downNumber, numObj, false);
00117 }
00118
00119
00120
00121
00122 void
00123 BM_lp::send_pseudo_cost_update(OsiBranchingInformation& branchInfo)
00124 {
00125 bm_buf.clear();
00126 int itmp;
00127 double objchange;
00128 itmp = BM_PseudoCostUpdate;
00129 bm_buf.pack(itmp);
00130 for (int i = 0; i < objNum_; ++i) {
00131 const BM_SB_result& sbres = sbResult_[i];
00132 if ((sbres.branchEval & 1) != 0 && sbres.status[0] != BCP_Abandoned) {
00133 bm_buf.pack(sbres.objInd);
00134 itmp = 0;
00135 bm_buf.pack(itmp);
00136 if (sbres.status[0] == BCP_ProvenOptimal) {
00137 objchange = sbres.objval[0] - branchInfo.objectiveValue_;
00138 } else {
00139 if (branchInfo.cutoff_ < 1e50) {
00140 objchange = 2*(branchInfo.cutoff_-branchInfo.objectiveValue_);
00141 } else {
00142 objchange = 2*fabs(branchInfo.objectiveValue_);
00143 }
00144 }
00145 bm_buf.pack(objchange/sbres.varChange[0]);
00146 }
00147 if ((sbres.branchEval & 2) != 0 && sbres.status[1] != BCP_Abandoned) {
00148 bm_buf.pack(sbres.objInd);
00149 itmp = 1;
00150 bm_buf.pack(itmp);
00151 if (sbres.status[1] == BCP_ProvenOptimal) {
00152 objchange = sbres.objval[1] - branchInfo.objectiveValue_;
00153 } else {
00154 if (branchInfo.cutoff_ < 1e50) {
00155 objchange = 2*(branchInfo.cutoff_-branchInfo.objectiveValue_);
00156 } else {
00157 objchange = 2*fabs(branchInfo.objectiveValue_);
00158 }
00159 }
00160 bm_buf.pack(objchange/sbres.varChange[1]);
00161 }
00162 }
00163 itmp = -1;
00164 bm_buf.pack(itmp);
00165 send_message(parent(), bm_buf);
00166 }
00167
00168
00169
00170 int
00171 BM_lp::sort_objects(OsiBranchingInformation& branchInfo,
00172 Bonmin::BonChooseVariable* choose, int& branchNum)
00173 {
00174 const OsiObject* const * objects = branchInfo.solver_->objects();
00175 double upMult, downMult;
00176 choose->computeMultipliers(upMult, downMult);
00177 const double MAXMIN = choose->maxminCrit(&branchInfo);
00178
00179
00180 int lastPriority = objects[objInd_[0]]->priority();
00181 int infBlockStart = 0;
00182 int feasBlockStart = 0;
00183 branchNum = 0;
00184 infNum_ = 0;
00185 feasNum_ = 0;
00186
00187 const bool isRoot = (current_index() == 0);
00188 int way;
00189
00190 const bool disregardPriorities = par.entry(BM_par::DisregardPriorities);
00191 const bool usePseudoCosts = par.entry(BM_par::UsePseudoCosts);
00192
00193 for (int i = 0; i < objNum_; ++i) {
00194 const int ind = objInd_[i];
00195 const OsiObject* object = objects[ind];
00196 double value = object->infeasibility(&branchInfo, way);
00197 if (value > 0.0) {
00198 if (value >= 1e50) {
00199 return -1;
00200 }
00201 if (! disregardPriorities) {
00202 int priorityLevel = object->priority();
00203 if (lastPriority < priorityLevel) {
00204
00205 if (infBlockStart < infNum_) {
00206 if (par.entry(BM_par::DecreasingSortInSetupList)) {
00207 CoinSort_2(infUseful_ + infBlockStart, infUseful_ + infNum_,
00208 infInd_ + infBlockStart,
00209 CoinFirstGreater_2<double,int>());
00210 } else {
00211 CoinSort_2(infUseful_ + infBlockStart, infUseful_ + infNum_,
00212 infInd_ + infBlockStart);
00213 }
00214 infBlockStart = infNum_;
00215 }
00216 lastPriority = priorityLevel;
00217 }
00218 }
00219 double dummy;
00220 infInd_[infNum_] = ind;
00221 if (usePseudoCosts) {
00222 infUseful_[infNum_] = isRoot ?
00223 value : choose->computeUsefulness(MAXMIN, upMult, downMult, value,
00224 object, ind, dummy);
00225 } else {
00226 infUseful_[infNum_] = value;
00227 }
00228
00229 ++infNum_;
00230 branchNum += 2;
00231
00232 } else {
00233 const OsiSOS* sos = dynamic_cast<const OsiSOS*>(object);
00234 if (sos) {
00235
00236 continue;
00237 }
00238 const int iCol = object->columnNumber();
00239 const double lb = branchInfo.lower_[iCol];
00240 const double ub = branchInfo.upper_[iCol];
00241 if (fabs(ub - lb) < 0.1) {
00242 continue;
00243 }
00244 value = branchInfo.solution_[iCol];
00245 ++branchNum;
00246 if (floor(value+0.5) > lb && ceil(value-0.5) < ub) {
00247
00248
00249 ++branchNum;
00250 }
00251 if (! disregardPriorities) {
00252 int priorityLevel = object->priority();
00253 if (lastPriority < priorityLevel) {
00254
00255 if (feasBlockStart < feasNum_) {
00256 if (par.entry(BM_par::DecreasingSortInSetupList)) {
00257 CoinSort_2(feasUseful_ + feasBlockStart, feasUseful_ + feasNum_,
00258 feasInd_ + feasBlockStart,
00259 CoinFirstGreater_2<double,int>());
00260 } else {
00261 CoinSort_2(feasUseful_ + feasBlockStart, feasUseful_ + feasNum_,
00262 feasInd_ + feasBlockStart);
00263 }
00264 }
00265 lastPriority = priorityLevel;
00266 }
00267 }
00268 double dummy;
00269 feasInd_[feasNum_] = ind;
00270 feasUseful_[feasNum_] = choose->computeUsefulness(MAXMIN,
00271 upMult, downMult, value,
00272 object, ind, dummy);
00273 ++feasNum_;
00274 }
00275 }
00276 if (infBlockStart < infNum_) {
00277 if (par.entry(BM_par::DecreasingSortInSetupList)) {
00278 CoinSort_2(infUseful_ + infBlockStart, infUseful_ + infNum_,
00279 infInd_ + infBlockStart,
00280 CoinFirstGreater_2<double,int>());
00281 } else {
00282 CoinSort_2(infUseful_ + infBlockStart, infUseful_ + infNum_,
00283 infInd_ + infBlockStart);
00284 }
00285 }
00286 if (feasBlockStart < feasNum_) {
00287 if (par.entry(BM_par::DecreasingSortInSetupList)) {
00288 CoinSort_2(feasUseful_ + feasBlockStart, feasUseful_ + feasNum_,
00289 feasInd_ + feasBlockStart,
00290 CoinFirstGreater_2<double,int>());
00291 } else {
00292 CoinSort_2(feasUseful_ + feasBlockStart, feasUseful_ + feasNum_,
00293 feasInd_ + feasBlockStart);
00294 }
00295 }
00296
00297 #if (BM_DEBUG_PRINT != 0)
00298 const double t = CoinWallclockTime();
00299 printf("LP %.3f: node: %i depth: %i obj: %f infNum: %i feasNum: %i soltime: %.3f\n",
00300 t-start_time(), current_index(), current_level(),
00301 branchInfo.objectiveValue_,
00302 infNum_, feasNum_, t-node_start_time);
00303 node_start_time = t;
00304 #endif
00305
00306 return infNum_;
00307 }
00308
00309
00310
00311 void
00312 BM_lp::clear_SB_results()
00313 {
00314 for (int i = 0; i < objNum_; ++i) {
00315 sbResult_[i].branchEval = 0;
00316 }
00317 bestSbResult_ = NULL;
00318 }
00319
00320
00321
00322 void
00323 BM_lp::collect_branch_data(OsiBranchingInformation& branchInfo,
00324 OsiSolverInterface* solver,
00325 const int branchNum,
00326 BM_BranchData* branchData)
00327 {
00328 int i;
00329 int b = 0;
00330 for (i = 0; i < infNum_; ++i) {
00331
00332 const int objInd = infInd_[i];
00333 const int colInd = solver->object(objInd)->columnNumber();
00334 const double val = branchInfo.solution_[colInd];
00335 branchData[b].changeType = BM_Var_DownBranch;
00336 branchData[b].objInd = objInd;
00337 branchData[b].colInd = colInd;
00338 branchData[b].solval = val;
00339 branchData[b].bd = floor(val);
00340 BM_SB_result& sbres = sbResult_[objInd];
00341 sbres.objInd = objInd;
00342 sbres.varChange[0] = val - floor(val);
00343 ++b;
00344 if (b == branchNum) {
00345 return;
00346 }
00347 branchData[b].changeType = BM_Var_UpBranch;
00348 branchData[b].objInd = objInd;
00349 branchData[b].colInd = colInd;
00350 branchData[b].solval = val;
00351 branchData[b].bd = ceil(val);
00352 sbres.varChange[1] = ceil(val) - val;
00353 ++b;
00354 if (b == branchNum) {
00355 return;
00356 }
00357 }
00358 for (i = 0; i < feasNum_; ++i) {
00359 const int objInd = feasInd_[i];
00360 const int colInd = solver->object(objInd)->columnNumber();
00361 const double val = branchInfo.solution_[colInd];
00362 const double lb = branchInfo.lower_[colInd];
00363 const double ub = branchInfo.upper_[colInd];
00364 if (floor(val+0.5) > lb) {
00365 branchData[b].changeType = BM_Var_DownBranch;
00366 branchData[b].objInd = objInd;
00367 branchData[b].colInd = colInd;
00368 branchData[b].solval = val;
00369 branchData[b].bd = floor(val - 0.5);
00370 ++b;
00371 if (b == branchNum) {
00372 return;
00373 }
00374 }
00375 if (ceil(val-0.5) < ub) {
00376 branchData[b].changeType = BM_Var_UpBranch;
00377 branchData[b].objInd = objInd;
00378 branchData[b].colInd = colInd;
00379 branchData[b].solval = val;
00380 branchData[b].bd = ceil(val + 0.5);
00381 ++b;
00382 if (b == branchNum) {
00383 return;
00384 }
00385 }
00386 }
00387 }
00388
00389
00390
00391 void
00392 BM_solve_branches(OsiSolverInterface* solver, const CoinWarmStart* cws,
00393 const int numBranch, BM_BranchData* bD)
00394 {
00395 for (int i = 0; i < numBranch; ++i) {
00396 double t = CoinWallclockTime();
00397 const int ind = bD[i].colInd;
00398 const int field = bD[i].changeType == BM_Var_UpBranch ? 1 : 0;
00399 const double old_lb = solver->getColLower()[ind];
00400 const double old_ub = solver->getColUpper()[ind];
00401 if (field == 0) {
00402 solver->setColUpper(ind, bD[i].bd);
00403 } else {
00404 solver->setColLower(ind, bD[i].bd);
00405 }
00406 if (cws) {
00407 solver->setWarmStart(cws);
00408 solver->resolve();
00409 } else {
00410 solver->initialSolve();
00411 }
00412 bD[i].status =
00413 (solver->isAbandoned() ? BCP_Abandoned : 0) |
00414 (solver->isProvenOptimal() ? BCP_ProvenOptimal : 0) |
00415 (solver->isProvenPrimalInfeasible() ? BCP_ProvenPrimalInf : 0);
00416 bD[i].objval =
00417 (bD[i].status & BCP_ProvenOptimal) != 0 ? solver->getObjValue() : 0.0;
00418 bD[i].iter = solver->getIterationCount();
00419 solver->setColBounds(ind, old_lb, old_ub);
00420 bD[i].time = CoinWallclockTime() - t;
00421 }
00422 }
00423
00424
00425
00426 void
00427 BM_register_branch_results(const int numBranch, const BM_BranchData* bD,
00428 BM_SB_result* sbResults)
00429 {
00430 for (int i = 0; i < numBranch; ++i) {
00431 const int field = bD[i].changeType == BM_Var_UpBranch ? 1 : 0;
00432 BM_SB_result& sbres = sbResults[bD[i].objInd];
00433 sbres.objInd = bD[i].objInd;
00434 sbres.branchEval |= field == 0 ? 1 : 2;
00435 sbres.status[field] = bD[i].status;
00436 sbres.objval[field] = bD[i].objval;
00437 sbres.iter[field] = bD[i].iter;
00438 sbres.varChange[field] = fabs(bD[i].solval - bD[i].bd);
00439 }
00440 }
00441
00442
00443
00444 void
00445 BM_lp::do_distributed_SB(OsiBranchingInformation& branchInfo,
00446 OsiSolverInterface* solver,
00447 const CoinWarmStart* cws,
00448 const int branchNum,
00449 const int* pids, const int pidNum)
00450 {
00451 const double * clb = solver->getColLower();
00452 const double * cub = solver->getColUpper();
00453 const int numCols = solver->getNumCols();
00454 bm_buf.clear();
00455 int tag = BM_StrongBranchRequest;
00456 bm_buf.pack(tag);
00457 bm_buf.pack(clb, numCols);
00458 bm_buf.pack(cub, numCols);
00459 bm_buf.pack(branchInfo.objectiveValue_);
00460 bm_buf.pack(branchInfo.cutoff_);
00461 bool has_ws = cws != NULL;
00462 bm_buf.pack(has_ws);
00463 if (has_ws) {
00464 BCP_lp_prob* p = getLpProblemPointer();
00465 CoinWarmStart* cws_tmp = cws->clone();
00466 BCP_warmstart* ws = cws ? BCP_lp_convert_CoinWarmStart(*p, cws_tmp) : NULL;
00467 BCP_pack_warmstart(ws, bm_buf);
00468 delete ws;
00469 }
00470
00471 const int fixed_size = bm_buf.size();
00472
00473
00474 BM_BranchData* branchData = new BM_BranchData[branchNum];
00475 collect_branch_data(branchInfo, solver, branchNum, branchData);
00476
00477
00478
00479 int branchLeft = branchNum;
00480 BM_BranchData* bD = branchData;
00481 for (int pidLeft = pidNum; pidLeft > 0; --pidLeft) {
00482 int numSend = branchLeft / pidLeft;
00483 if (numSend * pidLeft < branchLeft) {
00484 ++numSend;
00485 }
00486 bm_buf.set_size(fixed_size);
00487
00488 int location = bD - branchData;
00489 bm_buf.pack(location);
00490 bm_buf.pack(numSend);
00491 for (int s = 0; s < numSend; ++s) {
00492 bm_buf.pack(bD[s].changeType);
00493 bm_buf.pack(bD[s].objInd);
00494 bm_buf.pack(bD[s].colInd);
00495 bm_buf.pack(bD[s].solval);
00496 bm_buf.pack(bD[s].bd);
00497 }
00498 send_message(pids[pidLeft-1], bm_buf);
00499 bD += numSend;
00500 branchLeft -= numSend;
00501 }
00502 assert(branchNum/(pidNum+1) == branchLeft);
00503
00504
00505
00506
00507 BM_solve_branches(solver, cws, branchLeft, bD);
00508 bm_stats.incNumberSbSolves(branchLeft);
00509 BM_register_branch_results(branchLeft, bD, sbResult_);
00510
00511
00512 int numResults = branchLeft;
00513 while (numResults < branchNum) {
00514 bm_buf.clear();
00515 receive_message(BCP_AnyProcess, bm_buf, BCP_Msg_User);
00516 bm_buf.unpack(tag);
00517 assert(tag == BM_StrongBranchResult);
00518 int location;
00519 int numRes;
00520 bm_buf.unpack(location);
00521 bm_buf.unpack(numRes);
00522 BM_BranchData* bD = branchData + location;
00523 for (int i = 0; i < numRes; ++i) {
00524 bm_buf.unpack(bD[i].status);
00525 bm_buf.unpack(bD[i].objval);
00526 bm_buf.unpack(bD[i].iter);
00527 bm_buf.unpack(bD[i].time);
00528 }
00529 BM_register_branch_results(numRes, bD, sbResult_);
00530 numResults += numRes;
00531 }
00532 }
00533
00534
00535
00536 bool
00537 BM_lp::isBranchFathomable(int status, double obj)
00538 {
00539 return ( (status & BCP_ProvenPrimalInf) ||
00540 ((status & BCP_ProvenOptimal) && over_ub(obj)) );
00541 }
00542
00543
00544
00545 int
00546 BM_lp::process_SB_results(OsiBranchingInformation& branchInfo,
00547 OsiSolverInterface* solver,
00548 Bonmin::BonChooseVariable* choose,
00549 OsiBranchingObject*& branchObject)
00550 {
00551 int evaluated = 0;
00552 int i;
00553 #if defined(DEBUG_PRINT)
00554 const double t = CoinWallclockTime()-start_time();
00555 #endif
00556
00557 #if 0 // defined(DEBUG_PRINT)
00558 const double t = CoinWallclockTime()-start_time();
00559 for (i = 0; i < infNum_; ++i) {
00560 const BM_SB_result& sbres = sbResult_[infInd_[i]];
00561 if (sbres.branchEval == 0) {
00562 continue;
00563 }
00564 printf("LP %.3f: SB: node: %i inf col: %i stati: %i %i, obj: %f %f time: %.3f %.3f\n",
00565 t, current_index(), sbres.colInd,
00566 sbres.status[0], sbres.status[1],
00567 sbres.objval[0], sbres.objval[1], sbres.time[0], sbres.time[1]);
00568 }
00569 for (i = 0; i < feasNum_; ++i) {
00570 const BM_SB_result& sbres = sbResult_[feasInd_[i]];
00571 if (sbres.branchEval == 0) {
00572 continue;
00573 }
00574 printf("LP %.3f: SB: node: %i feas col: %i stati: %i %i, obj: %f %f time: %.3f %.3f\n",
00575 t, current_index(), sbres.colInd,
00576 sbres.status[0], sbres.status[1],
00577 sbres.objval[0], sbres.objval[1], sbres.time[0], sbres.time[1]);
00578 }
00579 #endif
00580
00581 int listLen=0;
00582 for (i = 0; i < infNum_; ++i) {
00583 const BM_SB_result& sbres = sbResult_[infInd_[i]];
00584 if (sbres.branchEval == 0) {
00585 continue;
00586 }
00587 assert(sbres.branchEval == 3);
00588 if (isBranchFathomable(sbres.status[0], sbres.objval[0]) &&
00589 isBranchFathomable(sbres.status[1], sbres.objval[1])) {
00590 #if (BM_DEBUG_PRINT != 0)
00591 const double wallclock = CoinWallclockTime();
00592 #if 0
00593 printf("LP %.3f: SBres: node: %i FATHOM inf/eval/cand: time: %.3f\n",
00594 wallclock-start_time(), current_index(),
00595 infNum_,
00596 wallclock-node_start_time);
00597 #else
00598 printf("LP %.3f: SBres: node: %i FATHOM time: %.3f\n",
00599 wallclock-start_time(), current_index(),
00600 wallclock-node_start_time);
00601 #endif
00602 #endif
00603 return -2;
00604 }
00605 ++listLen;
00606 }
00607
00608
00609
00610 int fixedStat = 0;
00611 for (i = 0; i < infNum_; ++i) {
00612 const BM_SB_result& sbres = sbResult_[infInd_[i]];
00613 if (sbres.branchEval == 0) {
00614 continue;
00615 }
00616 ++evaluated;
00617 if (isBranchFathomable(sbres.status[0], sbres.objval[0])) {
00618 const int colInd = sbres.colInd;
00619 solver->setColLower(colInd, ceil(branchInfo.solution_[colInd]));
00620 fixedStat |= 2;
00621 bm_stats.incNumberFixed();
00622 }
00623 if (isBranchFathomable(sbres.status[1], sbres.objval[1])) {
00624 const int colInd = sbres.colInd;
00625 solver->setColUpper(colInd, floor(branchInfo.solution_[colInd]));
00626 fixedStat |= 2;
00627 bm_stats.incNumberFixed();
00628 }
00629 }
00630 for (i = 0; i < feasNum_; ++i) {
00631 const BM_SB_result& sbres = sbResult_[feasInd_[i]];
00632 if (sbres.branchEval == 0) {
00633 continue;
00634 }
00635 ++evaluated;
00636 if ( (sbres.branchEval & 1) &&
00637 isBranchFathomable(sbres.status[0], sbres.objval[0]) ) {
00638
00639 const int colInd = sbres.colInd;
00640 solver->setColLower(colInd, ceil(branchInfo.solution_[colInd] - 0.5));
00641 fixedStat |= 1;
00642 bm_stats.incNumberFixed();
00643 }
00644 if ( (sbres.branchEval & 2) &&
00645 isBranchFathomable(sbres.status[1], sbres.objval[1]) ) {
00646
00647 const int colInd = sbres.colInd;
00648 solver->setColUpper(colInd, floor(branchInfo.solution_[colInd] + 0.5));
00649 fixedStat |= 1;
00650 bm_stats.incNumberFixed();
00651 }
00652 }
00653 if ((fixedStat & 2) != 0) {
00654 #if (BM_DEBUG_PRINT != 0)
00655 printf("LP %.3f: SBres: node: %i RESOLVE time: %.3f\n",
00656 t - start_time(), current_index(), t-node_start_time);
00657 node_start_time = t;
00658 #endif
00659 return -1;
00660 }
00661
00662
00663
00664
00665
00666 const bool preferHigh = par.entry(BM_par::PreferHighCombinationInBranching);
00667 int best = -1;
00668 int bestWhichWay = 1;
00669 double bestTrusted = preferHigh ? -COIN_DBL_MAX : COIN_DBL_MAX;
00670 const double MAXMIN = choose->maxminCrit(&branchInfo);
00671
00672 for (i = 0; i < infNum_; ++i) {
00673 const int objInd = infInd_[i];
00674 const BM_SB_result& sbres = sbResult_[objInd];
00675 if (sbres.branchEval == 0) {
00676
00677 continue;
00678 }
00679 if ((sbres.status[0]&BCP_Abandoned) || (sbres.status[1]&BCP_Abandoned)){
00680 continue;
00681 }
00682 double upEst = sbres.objval[1] - branchInfo.objectiveValue_;
00683 double downEst = sbres.objval[0] - branchInfo.objectiveValue_;
00684 double value =
00685 MAXMIN*CoinMin(upEst,downEst) + (1.0-MAXMIN)*CoinMax(upEst,downEst);
00686 const bool better = ( ( preferHigh && (value > bestTrusted)) ||
00687 ( !preferHigh && (value < bestTrusted)) );
00688 if (better) {
00689 bestTrusted = value;
00690 best = i;
00691 bestWhichWay = upEst > downEst ? 0 : 1;
00692
00693 const OsiObject* object = solver->object(objInd);
00694 if (object->preferredWay() >= 0 && object->infeasibility()) {
00695 bestWhichWay = object->preferredWay();
00696 }
00697 }
00698 }
00699 if (best == -1) {
00700
00701
00702
00703
00704 for (i = 0; i < infNum_; ++i) {
00705 const BM_SB_result& sbres = sbResult_[infInd_[i]];
00706 if (sbres.branchEval == 0) {
00707 best = i;
00708 break;
00709 }
00710 }
00711 if (best == -1) {
00712 for (i = 0; i < infNum_; ++i) {
00713 const BM_SB_result& sbres = sbResult_[infInd_[i]];
00714 if ((sbres.status[0] & BCP_Abandoned) == 0 ||
00715 (sbres.status[1] & BCP_Abandoned) == 0) {
00716
00717 best = i;
00718 break;
00719 }
00720 best = i;
00721 }
00722 }
00723 }
00724
00725 bm_stats.updateStrongBrachingInfo(best, listLen);
00726
00727
00728 const OsiObject * object = solver->object(infInd_[best]);
00729 branchObject = object->createBranch(solver, &branchInfo, bestWhichWay);
00730 bestSbResult_ = sbResult_ + infInd_[best];
00731 #if (BM_DEBUG_PRINT != 0)
00732 const int ind = object->columnNumber();
00733 printf("LP %.3f: SBres: node: %i depth: %i BRANCH time: %.3f evaluated: %i bvar: %i val: %f obj0: %f obj1: %f way: %i\n",
00734 t-start_time(), current_index(), current_level(), t-node_start_time,
00735 evaluated, ind, branchInfo.solution_[ind],
00736 bestSbResult_->objval[0], bestSbResult_->objval[1], bestWhichWay);
00737 node_start_time = t;
00738 #endif
00739
00740 return (fixedStat & 1) != 0 ? -1 : 0;
00741 }
00742
00743
00744
00745 int
00746 BM_lp::try_to_branch(OsiBranchingInformation& branchInfo,
00747 OsiSolverInterface* solver,
00748 Bonmin::BonChooseVariable* choose,
00749 OsiBranchingObject*& branchObject,
00750 bool allowVarFix)
00751 {
00752 int returnStatus = 0;
00753
00754 int branchNum;
00755 sort_objects(branchInfo, choose, branchNum);
00756
00757 if (infNum_ == 0) {
00758 return 0;
00759 }
00760
00761 const bool do_distributed_branching = true;
00762
00763 if (do_distributed_branching) {
00764
00765 bm_buf.clear();
00766 bm_buf.pack(branchNum-1);
00767 send_message(parent(), bm_buf, BCP_Msg_RequestProcessList);
00768 bm_buf.clear();
00769 receive_message(parent(), bm_buf, BCP_Msg_ProcessList);
00770 int* pids = NULL;
00771 int pidNum;
00772 bm_buf.unpack(pids, pidNum);
00773
00774 clear_SB_results();
00775
00776
00777 CoinWarmStart* cws = solver->getWarmStart();
00778 Bonmin::IpoptWarmStart* iws = dynamic_cast<Bonmin::IpoptWarmStart*>(cws);
00779 if (iws && iws->empty()) {
00780 delete cws;
00781 cws = NULL;
00782 }
00783
00784 const int nodeIndex = current_index();
00785 if (nodeIndex == 0) {
00786
00787
00788 branchNum = CoinMin(branchNum, par.entry(BM_par::SBNumBranchesInRoot));
00789 } else {
00790 if (nodeIndex < par.entry(BM_par::SBMaxLevel)) {
00791 branchNum = CoinMin(branchNum,
00792 CoinMax(pidNum + 1,
00793 par.entry(BM_par::SBNumBranchesInTree)));
00794 } else {
00795 branchNum = pidNum > 0 ? pidNum + 1 : 0;
00796 }
00797 }
00798
00799 if (branchNum > 0) {
00800 do_distributed_SB(branchInfo, solver, cws, branchNum, pids, pidNum);
00801 returnStatus = process_SB_results(branchInfo, solver, choose,
00802 branchObject);
00803 send_pseudo_cost_update(branchInfo);
00804 } else {
00805
00806
00807 returnStatus = BCP_lp_user::try_to_branch(branchInfo, solver, choose,
00808 branchObject, allowVarFix);
00809 }
00810
00811 delete[] pids;
00812 delete cws;
00813
00814 } else {
00815
00816 }
00817
00818 return returnStatus;
00819 }
00820
00821
00822
00823 BCP_branching_decision
00824 BM_lp::bbBranch(OsiBranchingInformation& brInfo,
00825 BCP_vec<BCP_lp_branching_object*>& cands)
00826 {
00827 BCP_lp_prob* p = getLpProblemPointer();
00828 OsiSolverInterface* osi = p->lp_solver;
00829 Bonmin::OsiTMINLPInterface* nlp =
00830 dynamic_cast<Bonmin::OsiTMINLPInterface*>(osi);
00831 assert(nlp);
00832
00833 nlp->getDblParam(OsiPrimalTolerance, brInfo.integerTolerance_);
00834
00835 BCP_branching_decision retCode;
00836 OsiBranchingObject* brObj = NULL;
00837
00838 const int numCols = nlp->getNumCols();
00839 double* clb_old = new double[numCols];
00840 double* cub_old = new double[numCols];
00841 CoinDisjointCopyN(nlp->getColLower(), numCols, clb_old);
00842 CoinDisjointCopyN(nlp->getColUpper(), numCols, cub_old);
00843
00844 Ipopt::SmartPtr<Ipopt::OptionsList> options = bonmin_.options();
00845 int numSB = 0;
00846
00847 options->GetIntegerValue("number_strong_branch",numSB,"bonmin.");
00848 int numSBroot = 0;
00849 const bool sbRootIsSet =
00850 options->GetIntegerValue("number_strong_branch_root",numSBroot,"bonmin.");
00851
00852 if (sbRootIsSet && brInfo.depth_ == 0) {
00853 bonmin_.branchingMethod()->setNumberStrong(numSBroot);
00854 } else {
00855 bonmin_.branchingMethod()->setNumberStrong(numSB);
00856 }
00857
00858 Bonmin::BonChooseVariable* choose =
00859 dynamic_cast<Bonmin::BonChooseVariable*>(bonmin_.branchingMethod());
00860 const int brResult = BM_lp::try_to_branch(brInfo, nlp, choose, brObj, true);
00861
00862 #if 0
00863 if (choose->goodSolution()) {
00864
00865 const double* sol = choose->goodSolution();
00866 BM_solution* bmsol = new BM_solution;
00867
00868 double ptol = integerTolerance_;
00869 for (int i = 0 ; i < numCols ; i++) {
00870 if (fabs(sol[i]) > ptol)
00871 bmsol->add_entry(i, sol[i]);
00872 }
00873 bmsol->setObjective(choose->goodObjectiveValue());
00874 choose->clearGoodSolution();
00875 send_feasible_solution(bmsol);
00876 delete bmsol;
00877 }
00878 #endif
00879
00880 switch (brResult) {
00881 case -2:
00882
00883
00884 retCode = BCP_DoNotBranch_Fathomed;
00885 break;
00886 case -1:
00887
00888 if (!brObj) {
00889
00890 retCode = BCP_DoNotBranch;
00891 } else {
00892
00893
00894 retCode = BCP_DoBranch;
00895 }
00896 break;
00897 case 0:
00898 if (!brObj) {
00899
00900 throw BCP_fatal_error("BM: Couldn't branch!\n");
00901 }
00902
00903 retCode = BCP_DoBranch;
00904 break;
00905 default:
00906 throw BCP_fatal_error("\
00907 BM: BCP_lp_user::try_to_branch returned with unknown return code.\n");
00908 }
00909
00910 if (brResult < 0) {
00911
00912
00913
00914
00915
00916
00917 const double* clb = nlp->getColLower();
00918 const double* cub = nlp->getColUpper();
00919
00920 BCP_vec<BCP_var*>& vars = getLpProblemPointer()->node->vars;
00921 for (int i = 0; i < numCols; ++i) {
00922 if (clb_old[i] != clb[i] || cub_old[i] != cub[i]) {
00923 vars[i]->change_bounds(clb[i], cub[i]);
00924 nlp->setColBounds(i, clb[i], cub[i]);
00925 }
00926 }
00927 }
00928
00929 if (retCode == BCP_DoBranch) {
00930
00931 int order[2] = {0, 1};
00932
00933 OsiIntegerBranchingObject* intBrObj =
00934 dynamic_cast<OsiIntegerBranchingObject*>(brObj);
00935 if (intBrObj) {
00936 if (intBrObj->firstBranch() == 1) {
00937 order[0] = 1;
00938 order[1] = 0;
00939 }
00940 BCP_lp_integer_branching_object o(intBrObj);
00941 cands.push_back(new BCP_lp_branching_object(o, order));
00942 if (bestSbResult_) {
00943 BCP_vec<double> lb(2, 0.0);
00944 lb[0] = bestSbResult_->objval[order[0]];
00945 lb[1] = bestSbResult_->objval[order[1]];
00946 BCP_vec<int> tc(2, 0);
00947 tc[0] = bestSbResult_->status[order[0]];
00948 tc[1] = bestSbResult_->status[order[1]];
00949 cands.back()->set_presolve_result(lb, tc);
00950 }
00951 if (par.entry(BM_par::PrintBranchingInfo)) {
00952 print(ifprint2, "BM_lp: branching on variable %i value: %f\n",
00953 intBrObj->originalObject()->columnNumber(),
00954 intBrObj->value());
00955 }
00956 }
00957 OsiSOSBranchingObject* sosBrObj =
00958 dynamic_cast<OsiSOSBranchingObject*>(brObj);
00959 if (sosBrObj) {
00960 if (sosBrObj->firstBranch() == 1) {
00961 order[0] = 1;
00962 order[1] = 0;
00963 }
00964 BCP_lp_sos_branching_object o(sosBrObj);
00965 cands.push_back(new BCP_lp_branching_object(nlp, o, order));
00966 if (bestSbResult_) {
00967 BCP_vec<double> lb(2, 0.0);
00968 lb[0] = bestSbResult_->objval[order[0]];
00969 lb[1] = bestSbResult_->objval[order[1]];
00970 BCP_vec<int> tc(2, 0);
00971 tc[0] = bestSbResult_->status[order[0]];
00972 tc[1] = bestSbResult_->status[order[1]];
00973 cands.back()->set_presolve_result(lb, tc);
00974 }
00975 if (par.entry(BM_par::PrintBranchingInfo)) {
00976 print(ifprint2, "BM_lp: branching on SOS %i value: %f\n",
00977 sosBrObj->originalObject()->columnNumber(),
00978 sosBrObj->value());
00979 }
00980 }
00981 }
00982
00983 delete brObj;
00984 delete[] clb_old;
00985 delete[] cub_old;
00986
00987 return retCode;
00988 }
00989
00990
00991
00992 void
00993 BM_lp::set_user_data_for_children(BCP_presolved_lp_brobj* best,
00994 const int selected)
00995 {
00996 BM_node* data = NULL;
00997 data = new BM_node;
00998 data->numNlpFailed_ = numNlpFailed_;
00999 best->user_data()[0] = data;
01000 data = new BM_node;
01001 data->numNlpFailed_ = numNlpFailed_;
01002 best->user_data()[1] = data;
01003 }
01004
01005
01006
01007 void
01008 BM_lp::process_message(BCP_buffer& buf)
01009 {
01010 int msgtag;
01011 buf.unpack(msgtag);
01012 assert(msgtag == BM_StrongBranchRequest);
01013
01014 Bonmin::OsiTMINLPInterface* nlp = bonmin_.nonlinearSolver();
01015
01016 int numCols;
01017 double* clb;
01018 double* cub;
01019 double objvalOrig;
01020 double cutoff;
01021 buf.unpack(clb, numCols);
01022 assert(numCols == nlp->getNumCols());
01023 buf.unpack(cub, numCols);
01024 assert(numCols == nlp->getNumCols());
01025 buf.unpack(objvalOrig);
01026 buf.unpack(cutoff);
01027 bool has_ws;
01028 buf.unpack(has_ws);
01029 BCP_warmstart* ws = has_ws ? BCP_unpack_warmstart(buf) : NULL;
01030 CoinWarmStart* cws = ws ? ws->convert_to_CoinWarmStart() : NULL;
01031 int location;
01032 int numBranch;
01033 buf.unpack(location);
01034 buf.unpack(numBranch);
01035
01036 int i;
01037 BM_BranchData* branchData = new BM_BranchData[numBranch];
01038 for (i = 0; i < numBranch; ++i) {
01039 buf.unpack(branchData[i].changeType);
01040 buf.unpack(branchData[i].objInd);
01041 buf.unpack(branchData[i].colInd);
01042 buf.unpack(branchData[i].solval);
01043 buf.unpack(branchData[i].bd);
01044 }
01045
01046 nlp->setColLower(clb);
01047 nlp->setColUpper(cub);
01048 BM_solve_branches(nlp, cws, numBranch, branchData);
01049
01050 bm_buf.clear();
01051 msgtag = BM_StrongBranchResult;
01052 bm_buf.pack(msgtag);
01053 bm_buf.pack(location);
01054 bm_buf.pack(numBranch);
01055 for (i = 0; i < numBranch; ++i) {
01056 const BM_BranchData& bD = branchData[i];
01057 bm_buf.pack(bD.status);
01058 bm_buf.pack(bD.objval);
01059 bm_buf.pack(bD.iter);
01060 bm_buf.pack(bD.time);
01061 }
01062 send_message(buf.sender(), bm_buf, BCP_Msg_User);
01063
01064 bm_buf.clear();
01065 send_message(parent(), bm_buf, BCP_Msg_SBnodeFinished);
01066
01067 delete[] branchData;
01068 delete cws;
01069 delete ws;
01070 delete[] clb;
01071 delete[] cub;
01072
01073 bm_stats.incNumberSbSolves(numBranch);
01074 }