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 roptions->AddLowerBoundedIntegerOption("probing_cuts",
00153 "Frequency (in terms of nodes) for generating probing cuts in branch-and-cut",
00154 -100,-5,
00155 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00156 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00157 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00158 roptions->setOptionExtraInfo("probing_cuts",5);
00159
00160 roptions->AddLowerBoundedIntegerOption("cover_cuts",
00161 "Frequency (in terms of nodes) for generating cover cuts in branch-and-cut",
00162 -100,-5,
00163 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00164 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00165 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00166 roptions->setOptionExtraInfo("cover_cuts",5);
00167
00168 roptions->AddLowerBoundedIntegerOption("mir_cuts",
00169 "Frequency (in terms of nodes) for generating MIR cuts in branch-and-cut",
00170 -100,-5,
00171 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00172 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00173 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00174 roptions->setOptionExtraInfo("mir_cuts",5);
00175 roptions->AddLowerBoundedIntegerOption("2mir_cuts",
00176 "Frequency (in terms of nodes) for generating 2-MIR cuts in branch-and-cut",
00177 -100,0,
00178 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00179 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00180 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00181 roptions->setOptionExtraInfo("2mir_cuts",5);
00182 roptions->AddLowerBoundedIntegerOption("flow_covers_cuts",
00183 "Frequency (in terms of nodes) for generating flow cover cuts in branch-and-cut",
00184 -100,-5,
00185 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00186 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00187 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00188 roptions->setOptionExtraInfo("flow_covers_cuts",5);
00189 roptions->AddLowerBoundedIntegerOption("lift_and_project_cuts",
00190 "Frequency (in terms of nodes) for generating lift-and-project cuts in branch-and-cut",
00191 -100,0,
00192 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00193 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00194 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00195 roptions->setOptionExtraInfo("lift_and_project_cuts",5);
00196 roptions->AddLowerBoundedIntegerOption("reduce_and_split_cuts",
00197 "Frequency (in terms of nodes) for generating reduce-and-split cuts in branch-and-cut",
00198 -100,0,
00199 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00200 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00201 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00202 roptions->setOptionExtraInfo("reduce_and_split_cuts",5);
00203 roptions->AddLowerBoundedIntegerOption("clique_cuts",
00204 "Frequency (in terms of nodes) for generating clique cuts in branch-and-cut",
00205 -100,-5,
00206 "If k > 0, cuts are generated every k nodes, if -99 < k < 0 cuts are generated every -k nodes but "
00207 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00208 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00209 roptions->setOptionExtraInfo("clique_cuts",5);
00210 }
00212 void
00213 BonminSetup::addMilpCutGenerators()
00214 {
00215 int freq;
00216 options_->GetIntegerValue("Gomory_cuts", freq,"bonmin.");
00217 if (freq) {
00218 CuttingMethod cg;
00219 cg.frequency = freq;
00220 CglGomory * gom = new CglGomory;
00221 cg.cgl = gom;
00222 gom->setLimitAtRoot(512);
00223 gom->setLimit(50);
00224 cg.id = "Mixed Integer Gomory";
00225 cutGenerators_.push_back(cg);
00226 }
00227 options_->GetIntegerValue("probing_cuts",freq,"bonmin.");
00228 if (freq) {
00229 CuttingMethod cg;
00230 cg.frequency = freq;
00231 CglProbing * probe = new CglProbing;
00232 cg.cgl = probe;
00233 probe->setUsingObjective(1);
00234 probe->setMaxPass(3);
00235 probe->setMaxPassRoot(3);
00236
00237 probe->setMaxProbe(10);
00238 probe->setMaxProbeRoot(50);
00239
00240 probe->setMaxLook(10);
00241 probe->setMaxLookRoot(50);
00242 probe->setMaxLookRoot(10);
00243
00244 probe->setMaxElements(200);
00245 probe->setRowCuts(3);
00246 cg.id = "Probing";
00247 cutGenerators_.push_back(cg);
00248 }
00249 options_->GetIntegerValue("mir_cuts",freq,"bonmin.");
00250 if (freq) {
00251 CuttingMethod cg;
00252 cg.frequency = freq;
00253 CglMixedIntegerRounding2 * mir = new CglMixedIntegerRounding2;
00254 cg.cgl = mir;
00255 cg.id = "Mixed Integer Rounding";
00256 cutGenerators_.push_back(cg);
00257
00258
00259 }
00260 options_->GetIntegerValue("2mir_cuts",freq,"bonmin.");
00261 if (freq) {
00262 CuttingMethod cg;
00263 cg.frequency = freq;
00264 CglTwomir * mir2 = new CglTwomir;
00265 cg.cgl = mir2;
00266 cg.id = "2-MIR";
00267 cutGenerators_.push_back(cg);
00268 }
00269 options_->GetIntegerValue("cover_cuts",freq,"bonmin.");
00270 if (freq) {
00271 CuttingMethod cg;
00272 cg.frequency = freq;
00273 CglKnapsackCover * cover = new CglKnapsackCover;
00274 cg.cgl = cover;
00275 cg.id = "Cover";
00276 cutGenerators_.push_back(cg);
00277 }
00278
00279 options_->GetIntegerValue("clique_cuts",freq,"bonmin.");
00280 if (freq) {
00281 CuttingMethod cg;
00282 cg.frequency = freq;
00283 CglClique * clique = new CglClique;
00284 clique->setStarCliqueReport(false);
00285 clique->setRowCliqueReport(false);
00286 clique->setMinViolation(0.1);
00287
00288 cg.cgl = clique;
00289 cg.id = "Clique";
00290 cutGenerators_.push_back(cg);
00291 }
00292 options_->GetIntegerValue("flow_covers_cuts",freq,"bonmin.");
00293 if (freq) {
00294 CuttingMethod cg;
00295 cg.frequency = freq;
00296 CglFlowCover * flow = new CglFlowCover;
00297 cg.cgl = flow;
00298 cg.id = "Flow Covers";
00299 cutGenerators_.push_back(cg);
00300 }
00301 options_->GetIntegerValue("lift_and_project_cuts",freq,"bonmin.");
00302 if (freq) {
00303 CuttingMethod cg;
00304 cg.frequency = freq;
00305 CglLandP * landp = new CglLandP;
00306 cg.cgl = landp;
00307 cg.id = "Lift-and-Project";
00308 cutGenerators_.push_back(cg);
00309 }
00310 options_->GetIntegerValue("reduce_and_split_cuts",freq,"bonmin.");
00311 if (freq) {
00312 CuttingMethod cg;
00313 cg.frequency = freq;
00314 CglRedSplit * rands = new CglRedSplit;
00315 cg.cgl = rands;
00316 cg.id = "Reduce-and-Split";
00317 cutGenerators_.push_back(cg);
00318 }
00319 }
00320
00321
00322 void
00323 BonminSetup::initializeBBB()
00324 {
00325 continuousSolver_ = nonlinearSolver_;
00326 nonlinearSolver_->ignoreFailures();
00327 OsiBabSolver extraStuff(2);
00328 continuousSolver_->setAuxiliaryInfo(&extraStuff);
00329
00330 intParam_[BabSetupBase::SpecialOption] = 16;
00331 if (!options_->GetIntegerValue("number_before_trust",intParam_[BabSetupBase::MinReliability],"bonmin.")) {
00332 intParam_[BabSetupBase::MinReliability] = 1;
00333 options_->SetIntegerValue("bonmin.number_before_trust",intParam_[BabSetupBase::MinReliability], true, true);
00334 }
00335 if (!options_->GetIntegerValue("number_strong_branch",intParam_[BabSetupBase::NumberStrong],"bonmin.")) {
00336 intParam_[BabSetupBase::NumberStrong] = 1000;
00337 options_->SetIntegerValue("bonmin.number_strong_branch",intParam_[BabSetupBase::NumberStrong], true, true);
00338 }
00339 int varSelection;
00340 bool val = options_->GetEnumValue("variable_selection",varSelection,"bonmin.");
00341 if (!val || varSelection == STRONG_BRANCHING || varSelection == RELIABILITY_BRANCHING ) {
00342 options_->SetStringValue("bonmin.variable_selection", "nlp-strong-branching", true, true);
00343 varSelection = NLP_STRONG_BRANCHING;
00344 }
00345
00346 switch (varSelection) {
00347 case CURVATURE_ESTIMATOR:
00348 case QP_STRONG_BRANCHING:
00349 case LP_STRONG_BRANCHING:
00350 case NLP_STRONG_BRANCHING: {
00351 continuousSolver_->findIntegersAndSOS(false);
00352 setPriorities();
00353 addSos();
00354 SmartPtr<StrongBranchingSolver> strong_solver = NULL;
00355 BonChooseVariable * chooseVariable = new BonChooseVariable(*this, nonlinearSolver_);
00356 chooseVariable->passInMessageHandler(nonlinearSolver_->messageHandler());
00357 switch (varSelection) {
00358 case CURVATURE_ESTIMATOR:
00359 strong_solver = new CurvBranchingSolver(nonlinearSolver_);
00360 chooseVariable->setTrustStrongForSolution(false);
00361 chooseVariable->setTrustStrongForBound(false);
00362
00363 chooseVariable->setOnlyPseudoWhenTrusted(false);
00364 break;
00365 case QP_STRONG_BRANCHING:
00366 chooseVariable->setTrustStrongForSolution(false);
00367 strong_solver = new QpBranchingSolver(nonlinearSolver_);
00368
00369
00370 chooseVariable->setTrustStrongForBound(false);
00371
00372 chooseVariable->setOnlyPseudoWhenTrusted(false);
00373 break;
00374 case LP_STRONG_BRANCHING:
00375 chooseVariable->setTrustStrongForSolution(false);
00376 strong_solver = new LpBranchingSolver(nonlinearSolver_);
00377
00378 chooseVariable->setOnlyPseudoWhenTrusted(false);
00379 break;
00380 case NLP_STRONG_BRANCHING:
00381 chooseVariable->setTrustStrongForSolution(false);
00382 chooseVariable->setTrustStrongForBound(true);
00383 chooseVariable->setOnlyPseudoWhenTrusted(false);
00384 break;
00385 }
00386 nonlinearSolver_->SetStrongBrachingSolver(strong_solver);
00387 branchingMethod_ = chooseVariable;
00388 }
00389 break;
00390 case OSI_SIMPLE:
00391 continuousSolver_->findIntegersAndSOS(false);
00392 setPriorities();
00393 addSos();
00394 branchingMethod_ = new OsiChooseVariable(nonlinearSolver_);
00395
00396 break;
00397 case OSI_STRONG:
00398 continuousSolver_->findIntegersAndSOS(false);
00399 setPriorities();
00400 addSos();
00401 branchingMethod_ = new OsiChooseStrong(nonlinearSolver_);
00402 break;
00403 case RANDOM:
00404 continuousSolver_->findIntegersAndSOS(false);
00405 setPriorities();
00406 addSos();
00407 branchingMethod_ = new BonRandomChoice(nonlinearSolver_);
00408 break;
00409
00410
00411 }
00412 if (branchingMethod_ != NULL) {
00413 branchingMethod_->setNumberStrong(intParam_[NumberStrong]);
00414 }
00415 }
00416
00417 void
00418 BonminSetup::initializeBHyb(bool createContinuousSolver )
00419 {
00420 if (createContinuousSolver) {
00421
00422 continuousSolver_ = new OsiClpSolverInterface;
00423 int lpLogLevel;
00424 options_->GetIntegerValue("lp_log_level",lpLogLevel,"bonmin.");
00425 lpMessageHandler_ = nonlinearSolver_->messageHandler()->clone();
00426 continuousSolver_->passInMessageHandler(lpMessageHandler_);
00427 continuousSolver_->messageHandler()->setLogLevel(lpLogLevel);
00428 nonlinearSolver_->extractLinearRelaxation(*continuousSolver_);
00429
00430 OsiBabSolver * extraStuff = new OsiBabSolver(3);
00431 continuousSolver_->setAuxiliaryInfo(extraStuff);
00432 delete extraStuff;
00433 }
00434 Algorithm algo = getAlgorithm();
00435 if (algo == B_OA) {
00436 options_->SetNumericValue("bonmin.oa_dec_time_limit",COIN_DBL_MAX, true, true);
00437 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00438 intParam_[BabLogLevel] = 0;
00439 }
00440 else if (algo==B_QG) {
00441 options_->SetNumericValue("bonmin.oa_dec_time_limit",0, true, true);
00442 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00443 }
00444 else if (algo==B_Ecp) {
00445 options_->SetNumericValue("bonmin.oa_dec_time_limit",0, true, true);
00446 options_->SetIntegerValue("bonmin.nlp_solve_frequency", 0, true, true);
00447 options_->SetIntegerValue("bonmin.filmint_ecp_cuts", 1, true, true);
00448 options_->SetIntegerValue("bonmin.number_cut_passes", 1, true, true);
00449 }
00450
00451 #ifdef GREAT_STUFF_FOR_ANDREAS
00452 printf("ToDo: Clean me up in Bab::branchAndBound\n");
00453 OsiCuts cuts;
00454 nonlinearSolver_->getOuterApproximation(cuts, true, NULL, true);
00455 continuousSolver_->applyCuts(cuts);
00456 #endif
00457
00458
00459 int varSelection;
00460 options_->GetEnumValue("variable_selection",varSelection,"bonmin.");
00461 if (varSelection > RELIABILITY_BRANCHING) {
00462 std::cout<<"Variable selection stragey not available with oa branch-and-cut."<<std::endl;
00463 }
00464
00465 int ival;
00466 options_->GetIntegerValue("nlp_solve_frequency",ival,"bonmin.");
00467 if (ival != 0) {
00468 CuttingMethod cg;
00469 cg.frequency = ival;
00470 OaNlpOptim * nlpsol = new OaNlpOptim(*this);
00471 nlpsol->passInMessageHandler(nonlinearSolver_->messageHandler());
00472 cg.cgl = nlpsol;
00473 cg.id="NLP solution based oa cuts";
00474 cutGenerators_.push_back(cg);
00475 }
00476
00477 options_->GetIntegerValue("filmint_ecp_cuts",ival, "bonmin.");
00478 if (ival != 0) {
00479 CuttingMethod cg;
00480 cg.frequency = ival;
00481 EcpCuts * ecp = new EcpCuts(*this);
00482 ecp->passInMessageHandler(nonlinearSolver_->messageHandler());
00483 cg.cgl = ecp;
00484 cg.id = "Ecp cuts";
00485 cutGenerators_.push_back(cg);
00486 }
00487
00488 if (algo == B_Hyb || algo == B_Ecp)
00489 addMilpCutGenerators();
00490
00491 double oaTime;
00492 options_->GetNumericValue("oa_dec_time_limit",oaTime,"bonmin.");
00493 if (oaTime > 0.) {
00494 CuttingMethod cg;
00495 cg.frequency = -99;
00496 OACutGenerator2 * oa = new OACutGenerator2(*this);
00497 oa->passInMessageHandler(nonlinearSolver_->messageHandler());
00498 cg.cgl = oa;
00499 cg.id = "Outer Approximation decomposition.";
00500 cutGenerators_.push_back(cg);
00501
00502 }
00503
00504 {
00505 CuttingMethod cg;
00506 cg.frequency = 1;
00507 OaFeasibilityChecker * oa = new OaFeasibilityChecker(*this);
00508 oa->passInMessageHandler(nonlinearSolver_->messageHandler());
00509 cg.cgl = oa;
00510 cg.id = "Outer Approximation feasibility check.";
00511 cg.atSolution = true;
00512 cg.normal = false;
00513 cutGenerators_.push_back(cg);
00514 }
00515
00516 DummyHeuristic * oaHeu = new DummyHeuristic;
00517 oaHeu->setNlp(nonlinearSolver_);
00518 HeuristicMethod h;
00519 h.heuristic = oaHeu;
00520 h.id = "nonlinear program";
00521 heuristics_.push_back(h);
00522 }
00523
00524 Algorithm BonminSetup::getAlgorithm()
00525 {
00526 if (algo_ != Dummy)
00527 return algo_;
00528 if (IsValid(options_)) {
00529 int ival;
00530 options_->GetEnumValue("algorithm", ival,"bonmin.");
00531 return Algorithm(ival);
00532 }
00533 else return Algorithm(3);
00534 }
00535
00536 }
00537