00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "BonminConfig.h"
00011 #include "OsiClpSolverInterface.hpp"
00012
00013 #include "BonBonminSetup.hpp"
00014 #include "BonCurvBranchingSolver.hpp"
00015 #include "BonChooseVariable.hpp"
00016 #include "BonRandomChoice.hpp"
00017 #include "BonDiver.hpp"
00018 #include "BonQpBranchingSolver.hpp"
00019 #include "BonLpBranchingSolver.hpp"
00020
00021
00022 #include "BonDummyHeuristic.hpp"
00023 #include "BonOACutGenerator2.hpp"
00024 #include "BonOaFeasChecker.hpp"
00025 #include "BonOaNlpOptim.hpp"
00026 #include "BonEcpCuts.hpp"
00027
00028 #include "BonCbcNode.hpp"
00029 #ifdef COIN_HAS_FILTERSQP
00030 # include "BonFilterSolver.hpp"
00031 #endif
00032
00033
00034 #include "CglGomory.hpp"
00035 #include "CglProbing.hpp"
00036 #include "CglKnapsackCover.hpp"
00037 #include "CglOddHole.hpp"
00038 #include "CglClique.hpp"
00039 #include "CglFlowCover.hpp"
00040 #include "CglMixedIntegerRounding2.hpp"
00041 #include "CglTwomir.hpp"
00042 #include "CglPreProcess.hpp"
00043 #include "CglLandP.hpp"
00044 #include "CglRedSplit.hpp"
00045
00046 namespace Bonmin
00047 {
00048 BonminSetup::BonminSetup():BabSetupBase(),algo_(Dummy)
00049 {}
00050
00051 BonminSetup::BonminSetup(const BonminSetup &other):BabSetupBase(other),
00052 algo_(other.algo_)
00053 {}
00054
00055 BonminSetup::BonminSetup(const BonminSetup &other,
00056 OsiTMINLPInterface &nlp):
00057 BabSetupBase(other, nlp),
00058 algo_(other.algo_)
00059 {
00060 if(algo_ != B_BB){
00061 assert(continuousSolver_ == NULL);
00062 continuousSolver_ = new OsiClpSolverInterface;
00063 int lpLogLevel;
00064 options_->GetIntegerValue("lp_log_level",lpLogLevel,"bonmin.");
00065 lpMessageHandler_ = nonlinearSolver_->messageHandler()->clone();
00066 continuousSolver_->passInMessageHandler(lpMessageHandler_);
00067 continuousSolver_->messageHandler()->setLogLevel(lpLogLevel);
00068 nonlinearSolver_->extractLinearRelaxation(*continuousSolver_);
00069
00070 OsiBabSolver * extraStuff = new OsiBabSolver(3);
00071 continuousSolver_->setAuxiliaryInfo(extraStuff);
00072 delete extraStuff;
00073 }
00074 }
00075 void BonminSetup::registerAllOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00076 {
00077 BabSetupBase::registerAllOptions(roptions);
00078
00079
00080 OACutGenerator2::registerOptions(roptions);
00081 EcpCuts::registerOptions(roptions);
00082 OaNlpOptim::registerOptions(roptions);
00083
00084
00085 BonCbcFullNodeInfo::registerOptions(roptions);
00086
00087
00088 registerMilpCutGenerators(roptions);
00089
00090
00091 roptions->SetRegisteringCategory("Algorithm choice", RegisteredOptions::BonminCategory);
00092 roptions->AddStringOption5("algorithm",
00093 "Choice of the algorithm.",
00094 "B-BB",
00095 "B-BB","simple branch-and-bound algorithm,",
00096 "B-OA","OA Decomposition algorithm,",
00097 "B-QG","Quesada and Grossmann branch-and-cut algorithm,",
00098 "B-Hyb","hybrid outer approximation based branch-and-cut,",
00099 "B-Ecp","ecp cuts based branch-and-cut a la FilMINT.",
00100 "This will preset some of the options of bonmin depending on the algorithm choice."
00101 );
00102 roptions->setOptionExtraInfo("algorithm",31);
00103 }
00104
00106 void
00107 BonminSetup::registerOptions()
00108 {
00109 registerAllOptions(roptions_);
00110 }
00111
00113 void
00114 BonminSetup::initialize(Ipopt::SmartPtr<TMINLP> tminlp, bool createContinuousSolver )
00115 {
00116
00117 use(tminlp);
00118 BabSetupBase::gatherParametersValues(options_);
00119 algo_ = getAlgorithm();
00120 if (algo_ == B_BB)
00121 initializeBBB();
00122 else
00123 initializeBHyb(createContinuousSolver);
00124 }
00125
00127 void
00128 BonminSetup::initialize(const OsiTMINLPInterface &nlpSi, bool createContinuousSolver )
00129 {
00130 use(nlpSi);
00131 BabSetupBase::gatherParametersValues(options_);
00132 Algorithm algo = getAlgorithm();
00133 if (algo == B_BB)
00134 initializeBBB();
00135 else
00136 initializeBHyb(createContinuousSolver);
00137 }
00138
00140 void
00141 BonminSetup::registerMilpCutGenerators(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00142 {
00143 roptions->SetRegisteringCategory("MILP cutting planes in hybrid", RegisteredOptions::BonminCategory);
00144
00145 roptions->AddLowerBoundedIntegerOption("Gomory_cuts",
00146 "Frequency k (in terms of nodes) for generating Gomory cuts in branch-and-cut.",
00147 -100,-5,
00148 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00149 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00150 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00151 roptions->setOptionExtraInfo("Gomory_cuts",5);
00152 #if 0
00153 roptions->AddBoundedIntegerOption("probing_cuts",
00154 "Frequency (in terms of nodes) for generating probing cuts in branch-and-cut",
00155 0,0,0,
00156 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00157 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00158 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00159 roptions->setOptionExtraInfo("probing_cuts",5);
00160 #endif
00161 roptions->AddLowerBoundedIntegerOption("cover_cuts",
00162 "Frequency (in terms of nodes) for generating cover cuts in branch-and-cut",
00163 -100,-5,
00164 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00165 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00166 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00167 roptions->setOptionExtraInfo("cover_cuts",5);
00168
00169 roptions->AddLowerBoundedIntegerOption("mir_cuts",
00170 "Frequency (in terms of nodes) for generating MIR cuts in branch-and-cut",
00171 -100,-5,
00172 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00173 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00174 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00175 roptions->setOptionExtraInfo("mir_cuts",5);
00176 roptions->AddLowerBoundedIntegerOption("2mir_cuts",
00177 "Frequency (in terms of nodes) for generating 2-MIR cuts in branch-and-cut",
00178 -100,0,
00179 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00180 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00181 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00182 roptions->setOptionExtraInfo("2mir_cuts",5);
00183 roptions->AddLowerBoundedIntegerOption("flow_covers_cuts",
00184 "Frequency (in terms of nodes) for generating flow cover cuts in branch-and-cut",
00185 -100,-5,
00186 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00187 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00188 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00189 roptions->setOptionExtraInfo("flow_covers_cuts",5);
00190 roptions->AddLowerBoundedIntegerOption("lift_and_project_cuts",
00191 "Frequency (in terms of nodes) for generating lift-and-project cuts in branch-and-cut",
00192 -100,0,
00193 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00194 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00195 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00196 roptions->setOptionExtraInfo("lift_and_project_cuts",5);
00197 roptions->AddLowerBoundedIntegerOption("reduce_and_split_cuts",
00198 "Frequency (in terms of nodes) for generating reduce-and-split cuts in branch-and-cut",
00199 -100,0,
00200 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00201 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00202 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00203 roptions->setOptionExtraInfo("reduce_and_split_cuts",5);
00204 roptions->AddLowerBoundedIntegerOption("clique_cuts",
00205 "Frequency (in terms of nodes) for generating clique cuts in branch-and-cut",
00206 -100,-5,
00207 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00208 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00209 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00210 roptions->setOptionExtraInfo("clique_cuts",5);
00211 }
00213 void
00214 BonminSetup::addMilpCutGenerators()
00215 {
00216 int freq;
00217 options_->GetIntegerValue("Gomory_cuts", freq,"bonmin.");
00218 if (freq) {
00219 CuttingMethod cg;
00220 cg.frequency = freq;
00221 CglGomory * gom = new CglGomory;
00222 cg.cgl = gom;
00223 gom->setLimitAtRoot(512);
00224 gom->setLimit(50);
00225 cg.id = "Mixed Integer Gomory";
00226 cutGenerators_.push_back(cg);
00227 }
00228 #if 0
00229 options_->GetIntegerValue("probing_cuts",freq,"bonmin.");
00230 if (freq) {
00231 CuttingMethod cg;
00232 cg.frequency = freq;
00233 CglProbing * probe = new CglProbing;
00234 cg.cgl = probe;
00235 probe->setUsingObjective(1);
00236 probe->setMaxPass(3);
00237 probe->setMaxPassRoot(3);
00238
00239 probe->setMaxProbe(10);
00240 probe->setMaxProbeRoot(50);
00241
00242 probe->setMaxLook(10);
00243 probe->setMaxLookRoot(50);
00244 probe->setMaxLookRoot(10);
00245
00246 probe->setMaxElements(200);
00247 probe->setRowCuts(3);
00248 cg.id = "Probing";
00249 cutGenerators_.push_back(cg);
00250 }
00251 #endif
00252 options_->GetIntegerValue("mir_cuts",freq,"bonmin.");
00253 if (freq) {
00254 CuttingMethod cg;
00255 cg.frequency = freq;
00256 CglMixedIntegerRounding2 * mir = new CglMixedIntegerRounding2;
00257 cg.cgl = mir;
00258 cg.id = "Mixed Integer Rounding";
00259 cutGenerators_.push_back(cg);
00260
00261
00262 }
00263 options_->GetIntegerValue("2mir_cuts",freq,"bonmin.");
00264 if (freq) {
00265 CuttingMethod cg;
00266 cg.frequency = freq;
00267 CglTwomir * mir2 = new CglTwomir;
00268 cg.cgl = mir2;
00269 cg.id = "2-MIR";
00270 cutGenerators_.push_back(cg);
00271 }
00272 options_->GetIntegerValue("cover_cuts",freq,"bonmin.");
00273 if (freq) {
00274 CuttingMethod cg;
00275 cg.frequency = freq;
00276 CglKnapsackCover * cover = new CglKnapsackCover;
00277 cg.cgl = cover;
00278 cg.id = "Cover";
00279 cutGenerators_.push_back(cg);
00280 }
00281
00282 options_->GetIntegerValue("clique_cuts",freq,"bonmin.");
00283 if (freq) {
00284 CuttingMethod cg;
00285 cg.frequency = freq;
00286 CglClique * clique = new CglClique;
00287 clique->setStarCliqueReport(false);
00288 clique->setRowCliqueReport(false);
00289 clique->setMinViolation(0.1);
00290
00291 cg.cgl = clique;
00292 cg.id = "Clique";
00293 cutGenerators_.push_back(cg);
00294 }
00295 options_->GetIntegerValue("flow_covers_cuts",freq,"bonmin.");
00296 if (freq) {
00297 CuttingMethod cg;
00298 cg.frequency = freq;
00299 CglFlowCover * flow = new CglFlowCover;
00300 cg.cgl = flow;
00301 cg.id = "Flow Covers";
00302 cutGenerators_.push_back(cg);
00303 }
00304 options_->GetIntegerValue("lift_and_project_cuts",freq,"bonmin.");
00305 if (freq) {
00306 CuttingMethod cg;
00307 cg.frequency = freq;
00308 CglLandP * landp = new CglLandP;
00309 cg.cgl = landp;
00310 cg.id = "Lift-and-Project";
00311 cutGenerators_.push_back(cg);
00312 }
00313 options_->GetIntegerValue("reduce_and_split_cuts",freq,"bonmin.");
00314 if (freq) {
00315 CuttingMethod cg;
00316 cg.frequency = freq;
00317 CglRedSplit * rands = new CglRedSplit;
00318 cg.cgl = rands;
00319 cg.id = "Reduce-and-Split";
00320 cutGenerators_.push_back(cg);
00321 }
00322 }
00323
00324
00325 void
00326 BonminSetup::initializeBBB()
00327 {
00328 continuousSolver_ = nonlinearSolver_;
00329 nonlinearSolver_->ignoreFailures();
00330 OsiBabSolver extraStuff(2);
00331 continuousSolver_->setAuxiliaryInfo(&extraStuff);
00332
00333 intParam_[BabSetupBase::SpecialOption] = 16;
00334 #if 1
00335 if (!options_->GetIntegerValue("number_before_trust",intParam_[BabSetupBase::MinReliability],"bonmin.")) {
00336 intParam_[BabSetupBase::MinReliability] = 1;
00337 options_->SetIntegerValue("bonmin.number_before_trust",intParam_[BabSetupBase::MinReliability], true, true);
00338 }
00339 if (!options_->GetIntegerValue("number_strong_branch",intParam_[BabSetupBase::NumberStrong],"bonmin.")) {
00340 intParam_[BabSetupBase::NumberStrong] = 1000;
00341 options_->SetIntegerValue("bonmin.number_strong_branch",intParam_[BabSetupBase::NumberStrong], true, true);
00342 }
00343 int varSelection;
00344 bool val = options_->GetEnumValue("variable_selection",varSelection,"bonmin.");
00345
00346 if (varSelection == MOST_FRACTIONAL) {
00347 intParam_[NumberStrong] = 0;
00348 intParam_[MinReliability] = 0;
00349 options_->SetIntegerValue("bonmin.number_strong_branch",intParam_[BabSetupBase::NumberStrong],true, true);
00350 }
00351 if (!val || varSelection == STRONG_BRANCHING || varSelection == RELIABILITY_BRANCHING ) {
00352 options_->SetStringValue("bonmin.variable_selection", "nlp-strong-branching", true, true);
00353 varSelection = NLP_STRONG_BRANCHING;
00354 }
00355 #endif
00356
00357 switch (varSelection) {
00358 case CURVATURE_ESTIMATOR:
00359 case QP_STRONG_BRANCHING:
00360 case LP_STRONG_BRANCHING:
00361 case NLP_STRONG_BRANCHING: {
00362 continuousSolver_->findIntegersAndSOS(false);
00363 setPriorities();
00364 addSos();
00365 SmartPtr<StrongBranchingSolver> strong_solver = NULL;
00366 BonChooseVariable * chooseVariable = new BonChooseVariable(*this, nonlinearSolver_);
00367 chooseVariable->passInMessageHandler(nonlinearSolver_->messageHandler());
00368 switch (varSelection) {
00369 case CURVATURE_ESTIMATOR:
00370 strong_solver = new CurvBranchingSolver(nonlinearSolver_);
00371 chooseVariable->setTrustStrongForSolution(false);
00372 chooseVariable->setTrustStrongForBound(false);
00373
00374 chooseVariable->setOnlyPseudoWhenTrusted(false);
00375 break;
00376 case QP_STRONG_BRANCHING:
00377 chooseVariable->setTrustStrongForSolution(false);
00378 strong_solver = new QpBranchingSolver(nonlinearSolver_);
00379
00380
00381 chooseVariable->setTrustStrongForBound(false);
00382
00383 chooseVariable->setOnlyPseudoWhenTrusted(false);
00384 break;
00385 case LP_STRONG_BRANCHING:
00386 chooseVariable->setTrustStrongForSolution(false);
00387 strong_solver = new LpBranchingSolver(nonlinearSolver_);
00388
00389 chooseVariable->setOnlyPseudoWhenTrusted(false);
00390 break;
00391 case NLP_STRONG_BRANCHING:
00392 chooseVariable->setTrustStrongForSolution(false);
00393 chooseVariable->setTrustStrongForBound(true);
00394 chooseVariable->setOnlyPseudoWhenTrusted(false);
00395 break;
00396 }
00397 nonlinearSolver_->SetStrongBrachingSolver(strong_solver);
00398 branchingMethod_ = chooseVariable;
00399 }
00400 break;
00401 case OSI_SIMPLE:
00402 continuousSolver_->findIntegersAndSOS(false);
00403 setPriorities();
00404 addSos();
00405 branchingMethod_ = new OsiChooseVariable(nonlinearSolver_);
00406
00407 break;
00408 case OSI_STRONG:
00409 continuousSolver_->findIntegersAndSOS(false);
00410 setPriorities();
00411 addSos();
00412 branchingMethod_ = new OsiChooseStrong(nonlinearSolver_);
00413 break;
00414 case RANDOM:
00415 continuousSolver_->findIntegersAndSOS(false);
00416 setPriorities();
00417 addSos();
00418 branchingMethod_ = new BonRandomChoice(nonlinearSolver_);
00419 break;
00420
00421
00422 }
00423 if (branchingMethod_ != NULL) {
00424 branchingMethod_->setNumberStrong(intParam_[NumberStrong]);
00425 }
00426 }
00427
00428 void
00429 BonminSetup::initializeBHyb(bool createContinuousSolver )
00430 {
00431 if (createContinuousSolver) {
00432
00433 continuousSolver_ = new OsiClpSolverInterface;
00434 int lpLogLevel;
00435 options_->GetIntegerValue("lp_log_level",lpLogLevel,"bonmin.");
00436 lpMessageHandler_ = nonlinearSolver_->messageHandler()->clone();
00437 continuousSolver_->passInMessageHandler(lpMessageHandler_);
00438 continuousSolver_->messageHandler()->setLogLevel(lpLogLevel);
00439 nonlinearSolver_->extractLinearRelaxation(*continuousSolver_);
00440
00441 OsiBabSolver * extraStuff = new OsiBabSolver(3);
00442 continuousSolver_->setAuxiliaryInfo(extraStuff);
00443 delete extraStuff;
00444 }
00445 Algorithm algo = getAlgorithm();
00446 if (algo == B_OA) {
00447 options_->SetNumericValue("bonmin.oa_dec_time_limit",COIN_DBL_MAX, true, true);
00448 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00449 intParam_[BabLogLevel] = 0;
00450 }
00451 else if (algo==B_QG) {
00452 options_->SetNumericValue("bonmin.oa_dec_time_limit",0, true, true);
00453 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00454 }
00455 else if (algo==B_Ecp) {
00456 options_->SetNumericValue("bonmin.oa_dec_time_limit",0, true, true);
00457 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00458 options_->SetIntegerValue("bonmin.filmint_ecp_cuts", 1, true, true);
00459 options_->SetIntegerValue("bonmin.number_cut_passes", 1, true, true);
00460 }
00461
00462 #ifdef GREAT_STUFF_FOR_ANDREAS
00463 printf("ToDo: Clean me up in Bab::branchAndBound\n");
00464 OsiCuts cuts;
00465 nonlinearSolver_->getOuterApproximation(cuts, true, NULL, true);
00466 continuousSolver_->applyCuts(cuts);
00467 #endif
00468
00469
00470 int varSelection;
00471 options_->GetEnumValue("variable_selection",varSelection,"bonmin.");
00472 if (varSelection > RELIABILITY_BRANCHING) {
00473 std::cout<<"Variable selection stragey not available with oa branch-and-cut."<<std::endl;
00474 }
00475
00476 int ival;
00477 options_->GetIntegerValue("nlp_solve_frequency",ival,"bonmin.");
00478 if (ival != 0) {
00479 CuttingMethod cg;
00480 cg.frequency = ival;
00481 OaNlpOptim * nlpsol = new OaNlpOptim(*this);
00482 nlpsol->passInMessageHandler(nonlinearSolver_->messageHandler());
00483 cg.cgl = nlpsol;
00484 cg.id="NLP solution based oa cuts";
00485 cutGenerators_.push_back(cg);
00486 }
00487
00488 options_->GetIntegerValue("filmint_ecp_cuts",ival, "bonmin.");
00489 if (ival != 0) {
00490 CuttingMethod cg;
00491 cg.frequency = ival;
00492 EcpCuts * ecp = new EcpCuts(*this);
00493 ecp->passInMessageHandler(nonlinearSolver_->messageHandler());
00494 cg.cgl = ecp;
00495 cg.id = "Ecp cuts";
00496 cutGenerators_.push_back(cg);
00497 }
00498
00499 if (algo == B_Hyb || algo == B_Ecp)
00500 addMilpCutGenerators();
00501
00502 double oaTime;
00503 options_->GetNumericValue("oa_dec_time_limit",oaTime,"bonmin.");
00504 if (oaTime > 0.) {
00505 CuttingMethod cg;
00506 cg.frequency = -99;
00507 OACutGenerator2 * oa = new OACutGenerator2(*this);
00508 oa->passInMessageHandler(nonlinearSolver_->messageHandler());
00509 cg.cgl = oa;
00510 cg.id = "Outer Approximation decomposition.";
00511 cutGenerators_.push_back(cg);
00512
00513 }
00514
00515 {
00516 CuttingMethod cg;
00517 cg.frequency = 1;
00518 OaFeasibilityChecker * oa = new OaFeasibilityChecker(*this);
00519 oa->passInMessageHandler(nonlinearSolver_->messageHandler());
00520 cg.cgl = oa;
00521 cg.id = "Outer Approximation feasibility check.";
00522 cg.atSolution = true;
00523 cg.normal = false;
00524 cutGenerators_.push_back(cg);
00525 }
00526
00527 DummyHeuristic * oaHeu = new DummyHeuristic;
00528 oaHeu->setNlp(nonlinearSolver_);
00529 HeuristicMethod h;
00530 h.heuristic = oaHeu;
00531 h.id = "nonlinear program";
00532 heuristics_.push_back(h);
00533 }
00534
00535 Algorithm BonminSetup::getAlgorithm()
00536 {
00537 if (algo_ != Dummy)
00538 return algo_;
00539 if (IsValid(options_)) {
00540 int ival;
00541 options_->GetEnumValue("algorithm", ival,"bonmin.");
00542 return Algorithm(ival);
00543 }
00544 else return Algorithm(3);
00545 }
00546
00547 }
00548