00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "BonCouenneSetup.hpp"
00012 #include "BonInitHeuristic.hpp"
00013 #include "BonNlpHeuristic.hpp"
00014 #include "BonCouenneInterface.hpp"
00015
00016 #include "BonGuessHeuristic.hpp"
00017 #include "CbcCompareActual.hpp"
00018
00019 #include "CouenneObject.hpp"
00020 #include "CouenneComplObject.hpp"
00021 #include "CouenneVarObject.hpp"
00022 #include "CouenneVTObject.hpp"
00023 #include "CouenneChooseVariable.hpp"
00024 #include "CouenneChooseStrong.hpp"
00025 #include "CouenneSolverInterface.hpp"
00026 #include "CouenneCutGenerator.hpp"
00027 #include "CouenneDisjCuts.hpp"
00028 #include "BonCouenneInfo.hpp"
00029 #include "BonCbcNode.hpp"
00030
00031
00032 #include "CglGomory.hpp"
00033 #include "CglProbing.hpp"
00034 #include "CglKnapsackCover.hpp"
00035 #include "CglOddHole.hpp"
00036 #include "CglClique.hpp"
00037 #include "CglFlowCover.hpp"
00038 #include "CglMixedIntegerRounding2.hpp"
00039 #include "CglTwomir.hpp"
00040 #include "CglPreProcess.hpp"
00041 #include "CglLandP.hpp"
00042 #include "CglRedSplit.hpp"
00043
00044
00045 #ifdef COIN_HAS_ASL
00046 #include "asl.h"
00047 #include "getstub.h"
00048 #endif
00049
00050
00051 namespace Bonmin{
00052
00053 SmartAsl::~SmartAsl(){
00054 #ifdef COIN_HAS_ASL
00055
00056 if(asl != NULL){
00057 if (X0) {
00058 delete [] X0;
00059 X0 = NULL;
00060 }
00061 if (havex0) {
00062 delete [] havex0;
00063 havex0 = NULL;
00064 }
00065 if (pi0) {
00066 delete [] pi0;
00067 pi0 = NULL;
00068 }
00069 if (havepi0) {
00070 delete [] havepi0;
00071 havepi0 = NULL;
00072 }
00073 ASL* asl_to_free = (ASL*)asl;
00074 ASL_free(&asl_to_free);
00075 asl = NULL;
00076 }
00077 ASL_free(&asl);
00078 #endif
00079 }
00080
00081 CouenneSetup::~CouenneSetup(){
00082
00083
00084 }
00085
00086 bool CouenneSetup::InitializeCouenne (char **& argv,
00087 CouenneProblem *couenneProb,
00088 Bonmin::CouenneInterface *ci) {
00089
00090 readOptionsFile();
00091
00092
00093 std::string test_mode;
00094 options_ -> GetStringValue ("test_mode", test_mode, "couenne.");
00095 if (test_mode == "yes")
00096 WindowsErrorPopupBlocker();
00097
00101 options_->SetStringValue ("nlp_failure_behavior", "fathom", "bonmin.");
00102
00103 gatherParametersValues(options_);
00104
00105 continuousSolver_ = new CouenneSolverInterface;
00106
00107 if (!ci) {
00108
00109 ci = new CouenneInterface;
00110
00111 if (!couenneProb && argv) {
00112 #ifdef COIN_HAS_ASL
00113
00114 ci->readAmplNlFile(argv,roptions(),options(),journalist());
00115 aslfg_ = new SmartAsl;
00116 aslfg_->asl = readASLfg (argv);
00117 #else
00118 std::cerr << "Couenne was compiled without AMPL Solver Library. Cannot initialize from AMPL NL File." << std::endl;
00119 return false;
00120 #endif
00121 }
00122 }
00123
00124 nonlinearSolver_ = ci;
00125 continuousSolver_ -> passInMessageHandler(ci -> messageHandler());
00126
00130 int i;
00131
00132 options()->GetIntegerValue("boundtightening_print_level", i, "bonmin.");
00133 journalist()->GetJournal("console")-> SetPrintLevel(J_BOUNDTIGHTENING, (EJournalLevel) i);
00134
00135 options()->GetIntegerValue("branching_print_level", i, "bonmin.");
00136 journalist()->GetJournal("console")-> SetPrintLevel(J_BRANCHING, (EJournalLevel) i);
00137
00138 options()->GetIntegerValue("convexifying_print_level", i, "bonmin.");
00139 journalist()->GetJournal("console")-> SetPrintLevel(J_CONVEXIFYING, (EJournalLevel) i);
00140
00141 options()->GetIntegerValue("problem_print_level", i, "bonmin.");
00142 journalist()->GetJournal("console")-> SetPrintLevel(J_PROBLEM, (EJournalLevel) i);
00143
00144 options()->GetIntegerValue("nlpheur_print_level", i, "bonmin.");
00145 journalist()->GetJournal("console")-> SetPrintLevel(J_NLPHEURISTIC, (EJournalLevel) i);
00146
00147 options()->GetIntegerValue("disjcuts_print_level", i, "bonmin.");
00148 journalist()->GetJournal("console")-> SetPrintLevel(J_DISJCUTS, (EJournalLevel) i);
00149
00150 options()->GetIntegerValue("reformulate_print_level", i, "bonmin.");
00151 journalist()->GetJournal("console")-> SetPrintLevel(J_REFORMULATE, (EJournalLevel) i);
00152
00153
00154
00155
00156
00157
00158 CouenneCutGenerator * couenneCg =
00159 new CouenneCutGenerator (ci, this, couenneProb ? NULL : aslfg_->asl);
00160
00161 if (!couenneProb) couenneProb = couenneCg -> Problem();
00162 else {
00163 couenneCg -> setProblem (couenneProb);
00164 couenneProb -> setBase (this);
00165 }
00166
00167 assert (couenneProb);
00168
00169 couenneProb -> reformulate ();
00170
00171 Bonmin::BabInfo * extraStuff = new Bonmin::CouenneInfo(0);
00172
00173
00174 extraStuff -> setExtraCharacteristics (extraStuff -> extraCharacteristics () | 2);
00175
00176 continuousSolver_ -> setAuxiliaryInfo (extraStuff);
00177 delete extraStuff;
00178
00179 extraStuff = dynamic_cast <Bonmin::BabInfo *> (continuousSolver_ -> getAuxiliaryInfo ());
00180
00181
00182 int lpLogLevel;
00183 options()->GetIntegerValue("lp_log_level",lpLogLevel,"bonmin.");
00184 continuousSolver_->messageHandler()->setLogLevel(lpLogLevel);
00185
00187
00188 couenneCg -> Problem () -> setMaxCpuTime (getDoubleParameter (BabSetupBase::MaxTime));
00189
00190 ci -> extractLinearRelaxation (*continuousSolver_, *couenneCg);
00191
00192
00193
00194 if (!(extraStuff -> infeasibleNode ()) &&
00195 ci -> isProvenOptimal () &&
00196 ci -> haveNlpSolution ()) {
00197
00199 InitHeuristic* initHeuristic = new InitHeuristic
00200 (ci -> getObjValue (), ci -> getColSolution (), *couenneProb);
00201 HeuristicMethod h;
00202 h.id = "Init Rounding NLP";
00203 h.heuristic = initHeuristic;
00204 heuristics_.push_back(h);
00205 }
00206
00207 if (extraStuff -> infeasibleNode ()){
00208 journalist() -> Printf(J_SUMMARY, J_PROBLEM, "Initial linear relaxation constructed by Couenne is infeasible, exiting...\n");
00209 return false;
00210 }
00211
00212
00213
00214
00215
00216
00217 std::string s;
00218
00219 int
00220 nSOS = 0,
00221 nVars = couenneProb -> nVars ();
00222
00223 OsiObject ** objects = NULL;
00224
00225 options () -> GetStringValue ("enable_sos", s, "couenne.");
00226 if (s == "yes") {
00227
00228
00229 objects = new OsiObject* [couenneProb -> nCons () + nVars];
00230
00231 nSOS = couenneProb -> findSOS (nonlinearSolver (), objects);
00232
00233 nonlinearSolver () -> addObjects (nSOS, objects);
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245 if (!nSOS) {
00246 delete [] objects;
00247 objects = NULL;
00248 }
00249 }
00250
00251
00252
00253
00254
00255
00256 options () -> GetStringValue ("display_stats", s, "couenne.");
00257 displayStats_ = (s == "yes");
00258
00259 options () -> GetStringValue ("branching_object", s, "couenne.");
00260
00261 enum CouenneObject::branch_obj objType = CouenneObject::VAR_OBJ;
00262
00263 if (s == "vt_obj") objType = CouenneObject::VT_OBJ;
00264 else if (s == "var_obj") objType = CouenneObject::VAR_OBJ;
00265 else if (s == "expr_obj") objType = CouenneObject::EXPR_OBJ;
00266 else {
00267 printf ("CouenneSetup: Unknown branching object type\n");
00268 exit (-1);
00269 }
00270
00271 int
00272 nobj = nSOS;
00273
00274 if (!objects)
00275 objects = new OsiObject* [nVars];
00276
00277 int contObjPriority = 2000;
00278
00279 options () -> GetIntegerValue ("cont_var_priority", contObjPriority, "bonmin.");
00280
00281 for (int i = 0; i < nVars; i++) {
00282
00283 exprVar *var = couenneProb -> Var (i);
00284
00285
00286 if (var -> Multiplicity () <= 0)
00287 continue;
00288
00289 switch (objType) {
00290
00291 case CouenneObject::EXPR_OBJ:
00292
00293
00294 if (var -> isInteger () ||
00295 (var -> Type () == AUX) &&
00296 (var -> Image () -> Linearity () > LINEAR)) {
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307 objects [nobj] = new CouenneObject (couenneProb, var, this, journalist ());
00308
00309 objects [nobj++] -> setPriority (contObjPriority);
00310
00311 }
00312
00313 break;
00314
00315 case CouenneObject::VAR_OBJ:
00316
00317
00318 if
00319 (var -> isInteger () ||
00320 (couenneProb -> Dependence () [var -> Index ()] . size () > 0)) {
00321
00322
00323
00324 objects [nobj] = new CouenneVarObject (couenneProb, var, this, journalist ());
00325 objects [nobj++] -> setPriority (contObjPriority);
00326
00327 }
00328
00329 break;
00330
00331 default:
00332 case CouenneObject::VT_OBJ:
00333
00334
00335 if
00336 (var -> isInteger () ||
00337 (couenneProb -> Dependence () [var -> Index ()] . size () > 0)) {
00338
00339
00340
00341 objects [nobj] = new CouenneVTObject (couenneProb, var, this, journalist ());
00342 objects [nobj++] -> setPriority (contObjPriority);
00343
00344 }
00345
00346 break;
00347 }
00348 }
00349
00350
00351
00352 continuousSolver_ -> addObjects (nobj, objects);
00353
00354 for (int i = 0 ; i < nobj ; i++)
00355 delete objects [i];
00356
00357 delete [] objects;
00358
00359
00360
00361 int freq;
00362
00363 options()->GetIntegerValue("convexification_cuts",freq,"couenne.");
00364
00365 if (freq != 0) {
00366
00367 CuttingMethod cg;
00368 cg.frequency = freq;
00369 cg.cgl = couenneCg;
00370 cg.id = "Couenne convexifier cuts";
00371 cutGenerators().push_back(cg);
00372
00373
00374 dynamic_cast <CouenneSolverInterface *>
00375 (continuousSolver_) -> setCutGenPtr (couenneCg);
00376 }
00377
00378
00379
00380
00381 if (couenneCg -> Problem () -> nIntVars () > 0)
00382 addMilpCutGenerators ();
00383
00384 CouennePtr_ = couenneCg;
00385
00386
00387
00388 int doNlpHeurisitic = 0;
00389 options()->GetEnumValue("local_optimization_heuristic", doNlpHeurisitic, "couenne.");
00390 if(doNlpHeurisitic)
00391 {
00392 int numSolve;
00393 options()->GetIntegerValue("log_num_local_optimization_per_level",numSolve,"couenne.");
00394 NlpSolveHeuristic * nlpHeuristic = new NlpSolveHeuristic;
00395 nlpHeuristic->setNlp(*ci,false);
00396 nlpHeuristic->setCouenneProblem(couenneProb);
00397
00398 nlpHeuristic->setMaxNlpInf(maxNlpInf_0);
00399 nlpHeuristic->setNumberSolvePerLevel(numSolve);
00400 HeuristicMethod h;
00401 h.id = "Couenne Rounding NLP";
00402 h.heuristic = nlpHeuristic;
00403 heuristics_.push_back(h);
00404 }
00405
00406 #if 0
00407 {
00408 CbcCompareEstimate compare;
00409 model -> setNodeComparison(compare);
00410 GuessHeuristic * guessHeu = new GuessHeuristic (*model);
00411 HeuristicMethod h;
00412 h.id = "Bonmin Guessing";
00413 h.heuristic = guessHeu;
00414 heuristics_.push_back (h);
00415
00416
00417 }
00418 #endif
00419
00420
00421
00422 int varSelection;
00423 if (!options_->GetEnumValue("variable_selection",varSelection,"bonmin.")) {
00424
00425 varSelection = OSI_SIMPLE;
00426 }
00427
00428 switch (varSelection) {
00429
00430 case OSI_STRONG: {
00431 CouenneChooseStrong * chooseVariable = new CouenneChooseStrong
00432 (*this, couenneProb, journalist ());
00433 chooseVariable->setTrustStrongForSolution(false);
00434 chooseVariable->setTrustStrongForBound(false);
00435 chooseVariable->setOnlyPseudoWhenTrusted(true);
00436 branchingMethod_ = chooseVariable;
00437 break;
00438 }
00439
00440 case OSI_SIMPLE:
00441 branchingMethod_ = new CouenneChooseVariable
00442 (continuousSolver_, couenneProb, journalist ());
00443 break;
00444
00445 default:
00446 std::cerr << "Unknown variable_selection for Couenne\n" << std::endl;
00447 throw;
00448 break;
00449 }
00450
00451
00452
00453 options () -> GetIntegerValue ("minlp_disj_cuts", freq, "couenne.");
00454
00455 if (freq != 0) {
00456
00457 CouenneDisjCuts * couenneDisj =
00458 new CouenneDisjCuts (ci, this,
00459 couenneCg,
00460 branchingMethod_,
00461 varSelection == OSI_STRONG,
00462 journalist (),
00463 options ());
00464
00465 CuttingMethod cg;
00466 cg.frequency = freq;
00467 cg.cgl = couenneDisj;
00468 cg.id = "Couenne disjunctive cuts";
00469 cutGenerators (). push_back(cg);
00470 }
00471
00472 int ival;
00473 if (!options_->GetEnumValue("node_comparison",ival,"bonmin.")) {
00474
00475 nodeComparisonMethod_ = bestBound;
00476 }
00477 else {
00478 nodeComparisonMethod_ = NodeComparison(ival);
00479 }
00480
00481 if(intParam_[NumCutPasses] < 2)
00482 intParam_[NumCutPasses] = 2;
00483
00484
00485
00486 intParam_[BabSetupBase::SpecialOption] = 16 | 4;
00487
00488 return true;
00489 }
00490
00491 void CouenneSetup::registerOptions(){
00492 registerAllOptions(roptions());
00493 }
00494
00495
00496 void
00497 CouenneSetup::registerAllOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions){
00498 BabSetupBase::registerAllOptions(roptions);
00499 BonCbcFullNodeInfo::registerOptions(roptions);
00500 CouenneCutGenerator::registerOptions (roptions);
00501 CouenneDisjCuts::registerOptions (roptions);
00502
00503 roptions -> AddNumberOption
00504 ("couenne_check",
00505 "known value of a global optimum",
00506 COIN_DBL_MAX,
00507 "Default value is +infinity.");
00508
00509 roptions -> AddStringOption2 (
00510 "display_stats",
00511 "display statistics at the end of the run",
00512 "no",
00513 "yes", "",
00514 "no", "");
00515
00516 roptions -> AddStringOption2 (
00517 "test_mode",
00518 "set to true if this is Couenne unit test",
00519 "no",
00520 "yes", "",
00521 "no", "");
00522
00523 roptions->AddBoundedIntegerOption(
00524 "branching_print_level", "Output level for braching code in Couenne",
00525 -2, J_LAST_LEVEL-1, J_NONE, "");
00526
00527 roptions->AddBoundedIntegerOption(
00528 "boundtightening_print_level", "Output level for bound tightening code in Couenne",
00529 -2, J_LAST_LEVEL-1, J_NONE, "");
00530
00531 roptions->AddBoundedIntegerOption(
00532 "convexifying_print_level", "Output level for convexifying code in Couenne",
00533 -2, J_LAST_LEVEL-1, J_NONE, "");
00534
00535 roptions->AddBoundedIntegerOption(
00536 "problem_print_level", "Output level for problem manipulation code in Couenne",
00537 -2, J_LAST_LEVEL-1, J_WARNING, "");
00538
00539 roptions->AddBoundedIntegerOption(
00540 "nlpheur_print_level", "Output level for NLP heuristic in Couenne",
00541 -2, J_LAST_LEVEL-1, J_WARNING, "");
00542
00543 roptions->AddBoundedIntegerOption(
00544 "disjcuts_print_level", "Output level for disjunctive cuts in Couenne",
00545 -2, J_LAST_LEVEL-1, J_WARNING, "");
00546
00547 roptions->AddBoundedIntegerOption(
00548 "reformulate_print_level", "Output level for reformulating problems in Couenne",
00549 -2, J_LAST_LEVEL-1, J_WARNING, "");
00550
00551
00552
00553
00554
00555 struct cutOption_ {
00556
00557 const char *cgname;
00558 int defaultFreq;
00559
00560 } cutOption [] = {
00561 {(const char *) "Gomory_cuts", 0},
00562 {(const char *) "probing_cuts", 0},
00563 {(const char *) "cover_cuts", 0},
00564 {(const char *) "mir_cuts", 0},
00565 {(const char *) "2mir_cuts", 0},
00566 {(const char *) "flow_covers_cuts", 0},
00567 {(const char *) "lift_and_project_cuts", 0},
00568 {(const char *) "reduce_split_cuts", 0},
00569 {(const char *) "clique_cuts", 0},
00570 {NULL, 0}};
00571
00572 for (int i=0; cutOption [i].cgname; i++) {
00573
00574 char descr [150];
00575
00576 sprintf (descr, "Frequency k (in terms of nodes) for generating %s cuts in branch-and-cut.",
00577 cutOption [i].cgname);
00578
00579 roptions -> AddLowerBoundedIntegerOption
00580 (cutOption [i].cgname,
00581 descr,
00582 -100, cutOption [i].defaultFreq,
00583 "If k > 0, cuts are generated every k nodes, "
00584 "if -99 < k < 0 cuts are generated every -k nodes but "
00585 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
00586 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
00587
00588 roptions->setOptionExtraInfo (cutOption [i].cgname, 5);
00589 }
00590 }
00591
00592
00593
00595 void CouenneSetup::addMilpCutGenerators () {
00596
00597 enum extraInfo_ {CUTINFO_NONE, CUTINFO_MIG, CUTINFO_PROBING, CUTINFO_CLIQUE};
00598
00599 struct cutInfo {
00600
00601 const char *optname;
00602 CglCutGenerator *cglptr;
00603 const char *cglId;
00604 enum extraInfo_ extraInfo;
00605
00606 } cutList [] = {
00607 {(const char*)"Gomory_cuts",new CglGomory, (const char*)"Mixed Integer Gomory",CUTINFO_MIG},
00608 {(const char*)"probing_cuts",new CglProbing, (const char*) "Probing", CUTINFO_PROBING},
00609 {(const char*)"mir_cuts",new CglMixedIntegerRounding2, (const char*) "Mixed Integer Rounding",
00610 CUTINFO_NONE},
00611 {(const char*)"2mir_cuts", new CglTwomir, (const char*) "2-MIR", CUTINFO_NONE},
00612 {(const char*)"cover_cuts", new CglKnapsackCover, (const char*) "Cover", CUTINFO_NONE},
00613 {(const char*)"clique_cuts", new CglClique, (const char*) "Clique", CUTINFO_CLIQUE},
00614 {(const char*)"lift_and_project_cuts",new CglLandP,(const char*)"Lift and Project",CUTINFO_NONE},
00615 {(const char*)"reduce_split_cuts",new CglRedSplit,(const char*) "Reduce and Split",CUTINFO_NONE},
00616 {(const char*)"flow_covers_cuts",new CglFlowCover,(const char*) "Flow cover cuts", CUTINFO_NONE},
00617 {NULL, NULL, NULL, CUTINFO_NONE}};
00618
00619 int freq;
00620
00621 for (int i=0; cutList [i]. optname; i++) {
00622
00623 options_ -> GetIntegerValue (std::string (cutList [i]. optname), freq, "bonmin.");
00624
00625 if (!freq) {
00626 delete cutList [i].cglptr;
00627 continue;
00628 }
00629
00630 CuttingMethod cg;
00631 cg.frequency = freq;
00632 cg.cgl = cutList [i].cglptr;
00633 cg.id = std::string (cutList [i]. cglId);
00634 cutGenerators_.push_back (cg);
00635
00636
00637 switch (cutList [i].extraInfo) {
00638
00639 case CUTINFO_MIG: {
00640 CglGomory *gc = dynamic_cast <CglGomory *> (cutList [i].cglptr);
00641
00642 if (!gc) break;
00643
00644 gc -> setLimitAtRoot(512);
00645 gc -> setLimit(50);
00646 }
00647 break;
00648
00649 case CUTINFO_PROBING: {
00650 CglProbing *pc = dynamic_cast <CglProbing *> (cutList [i].cglptr);
00651
00652 if (!pc) break;
00653
00654 pc->setUsingObjective(1);
00655 pc->setMaxPass(3);
00656 pc->setMaxPassRoot(3);
00657
00658 pc->setMaxProbe(10);
00659 pc->setMaxProbeRoot(50);
00660
00661 pc->setMaxLook(10);
00662 pc->setMaxLookRoot(50);
00663 pc->setMaxLookRoot(10);
00664
00665 pc->setMaxElements(200);
00666 pc->setRowCuts(3);
00667 }
00668 break;
00669
00670 case CUTINFO_CLIQUE: {
00671 CglClique *clique = dynamic_cast <CglClique *> (cutList [i].cglptr);
00672
00673 if (!clique) break;
00674
00675 clique -> setStarCliqueReport(false);
00676 clique -> setRowCliqueReport(false);
00677 clique -> setMinViolation(0.1);
00678 }
00679 break;
00680
00681
00682 default:
00683 break;
00684 }
00685 }
00686 }
00687 }