1 // (C) Copyright International Business Machines Corporation 2007 2 // All Rights Reserved. 3 // This code is published under the Eclipse Public License. 4 // 5 // Authors : 6 // Pierre Bonami, International Business Machines Corporation 7 // 8 // Date : 04/12/2007 9 10 #ifndef BabSetupBase_H 11 #define BabSetupBase_H 12 13 #include <string> 14 #include <list> 15 #include "CglCutGenerator.hpp" 16 #include "CbcHeuristic.hpp" 17 #include "OsiChooseVariable.hpp" 18 #include "BonOsiTMINLPInterface.hpp" 19 #include "IpSmartPtr.hpp" 20 #include "BonTMINLP2OsiLP.hpp" 21 22 namespace Bonmin 23 { 24 /** A class to have all elements necessary to setup a branch-and-bound.*/ 25 class BabSetupBase 26 { 27 public: 28 /** Type for cut generation method with its frequency and string identification. */ 29 struct CuttingMethod 30 { 31 int frequency; 32 std::string id; 33 CglCutGenerator * cgl; 34 bool atSolution; 35 bool normal; 36 bool always; CuttingMethodBonmin::BabSetupBase::CuttingMethod37 CuttingMethod(): 38 atSolution(false), 39 normal(true), 40 always(false) 41 {} 42 CuttingMethodBonmin::BabSetupBase::CuttingMethod43 CuttingMethod(const CuttingMethod & other): 44 frequency(other.frequency), 45 id(other.id), 46 cgl(other.cgl), 47 atSolution(other.atSolution), 48 normal(other.normal), 49 always(other.always) 50 {} 51 }; 52 /** Type for heuristic method with its string identification. */ 53 struct HeuristicMethod 54 { 55 std::string id; 56 CbcHeuristic* heuristic; HeuristicMethodBonmin::BabSetupBase::HeuristicMethod57 HeuristicMethod() 58 {} 59 HeuristicMethodBonmin::BabSetupBase::HeuristicMethod60 HeuristicMethod(const HeuristicMethod & other): 61 id(other.id), 62 heuristic(other.heuristic) 63 {} 64 }; 65 typedef std::list<CuttingMethod> CuttingMethods; 66 typedef std::list<HeuristicMethod > HeuristicMethods; 67 68 /** Strategies for comparing the nodes on the heap. */ 69 enum NodeComparison { 70 bestBound = 0 /** Best bound*/, 71 DFS /** Depth First Search*/, 72 BFS /** Best First Search */, 73 dynamic /** Dynamic strategy, see <a href="http://www.coin-or.org/Doxygen/Cbc/class_cbc_branch_dynamic_decision.html"> 74 CbcBranchActual.hpp </a> for explanations.*/, 75 bestGuess /** Best guessed integer solution is subtree below, based on pseudo costs */ 76 }; 77 78 /** Strategies for traversing the tree.*/ 79 enum TreeTraversal { 80 HeapOnly=0 /** Only using the heap, uses CbcTree.*/, 81 DiveFromBest /** dive from top node of the heap untill it gets to a leaf of the tree. Uses Bonmin::CbcDiver.*/, 82 ProbedDive /** Eplore two kids before following on dive.*/, 83 DfsDiveFromBest /** dive from top node of the heap with more elaborate strategy (see options doc). Uses Bonmin::CbcDfsDiver.*/, 84 DfsDiveDynamic /** Same as DfsDiveFromBest, but after a prescribed number of integer solution are found switch to best-bound and if too many node switches to depth-first. Uses Bonmin::CbcDfsDiver.*/ 85 }; 86 87 88 /** @name Enums for optionslist parameters */ 89 enum VarSelectStra_Enum { 90 MOST_FRACTIONAL=0, 91 STRONG_BRANCHING, 92 RELIABILITY_BRANCHING, 93 #ifdef BONMIN_CURVATURE_BRANCHING 94 CURVATURE_ESTIMATOR, 95 #endif 96 QP_STRONG_BRANCHING, 97 LP_STRONG_BRANCHING, 98 NLP_STRONG_BRANCHING, 99 OSI_SIMPLE, 100 OSI_STRONG, 101 RANDOM 102 }; 103 104 /** Parameters represented by an integer. */ 105 enum IntParameter{ 106 BabLogLevel = 0 /** Log level of main branch-and-bound*/, 107 BabLogInterval/** Display information every logIntervval nodes.*/, 108 MaxFailures /** Max number of failures in a branch.*/, 109 FailureBehavior /** Behavior of the algorithm in the case of a failure.*/, 110 MaxInfeasible /** Max number of consecutive infeasible problem in a branch 111 before fathoming.*/, 112 NumberStrong /** Number of candidates for strong branching.*/, 113 MinReliability /** Minimum reliability before trust pseudo-costs.*/, 114 MaxNodes /** Global node limit.*/, 115 MaxSolutions /** limit on number of integer feasible solution.*/, 116 MaxIterations /** Global iteration limit. */, 117 SpecialOption /** Spetial option in particular for Cbc. */, 118 DisableSos /** Consider or not SOS constraints.*/, 119 NumCutPasses/** Number of cut passes at nodes.*/, 120 NumCutPassesAtRoot/** Number of cut passes at nodes.*/, 121 RootLogLevel/** Log level for root relaxation.*/, 122 NumberIntParam /** Dummy end to size table*/ 123 }; 124 125 126 /** Parameters represented by a double.*/ 127 enum DoubleParameter{ 128 CutoffDecr = 0 /** Amount by which cutoff is incremented */, 129 Cutoff /** cutoff value */, 130 AllowableGap /** Stop if absolute gap is less than this. */, 131 AllowableFractionGap /** Stop if relative gap is less than this.*/, 132 IntTol /** Integer tolerance.*/, 133 MaxTime /** Global time limit. */, 134 NumberDoubleParam /** Dummy end to size table*/ 135 }; 136 137 /** Default constructor. */ 138 BabSetupBase(const CoinMessageHandler * handler = NULL); 139 140 /** Construct from existing tminlp. */ 141 BabSetupBase(Ipopt::SmartPtr<TMINLP> tminlp, const CoinMessageHandler * handler = NULL); 142 /** Construct from existing application.*/ 143 BabSetupBase(Ipopt::SmartPtr<TNLPSolver> app); 144 /** Construct from existing TMINLP interface.*/ 145 BabSetupBase(const OsiTMINLPInterface& nlp); 146 /** Copy but uses an other nlp.*/ 147 BabSetupBase(const BabSetupBase &setup, 148 OsiTMINLPInterface &nlp); 149 150 /** Copy but uses an other nlp.*/ 151 BabSetupBase(const BabSetupBase &setup, 152 OsiTMINLPInterface &nlp, 153 const std::string &prefix); 154 155 /** Copy constructor. */ 156 BabSetupBase(const BabSetupBase & other); 157 158 /** virtual copy constructor. */ 159 virtual BabSetupBase * clone() const = 0; 160 161 /** Make a copy with solver replace by one passed .*/ 162 virtual BabSetupBase *clone(OsiTMINLPInterface&nlp)const; 163 /** Virtual destructor. */ 164 virtual ~BabSetupBase(); 165 166 /** @name Methods to initialize algorithm with various inputs. */ 167 /** @{ */ 168 /** use existing TMINLP interface (containing the options).*/ 169 void use(const OsiTMINLPInterface& nlp); 170 /** Read options (if not done before) and create interface using tminlp.*/ 171 void use(Ipopt::SmartPtr<TMINLP> tminlp ); 172 /** use specific instanciation of a TMINLP2TNLP.*/ 173 void use(Ipopt::SmartPtr<TMINLP2TNLP> prob); 174 /** Set the non-linear solver used */ setNonlinearSolver(OsiTMINLPInterface * s)175 void setNonlinearSolver(OsiTMINLPInterface * s) 176 { 177 nonlinearSolver_ = s; 178 } 179 /** @} */ 180 181 /** @name Methods to manipulate options. */ 182 /** @{ */ 183 /** Register all the options for this algorithm instance.*/ 184 virtual void registerOptions(); 185 /** Setup the defaults options for this algorithm. */ setBabDefaultOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)186 virtual void setBabDefaultOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions) 187 {} 188 /** Register all the options for this algorithm instance.*/ 189 static void registerAllOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions); 190 191 /** Get the options from default text file (bonmin.opt) if don't already have them.*/ readOptionsFile()192 virtual void readOptionsFile() 193 { 194 if (readOptions_) return; 195 readOptionsFile("bonmin.opt"); 196 } 197 198 /** Get the options from given fileName */ 199 void readOptionsFile(std::string fileName); 200 201 /** Get the options from long string containing all.*/ 202 void readOptionsString(std::string opt_string); 203 204 /** Get the options from stream.*/ 205 void readOptionsStream(std::istream& is); 206 207 /** May print documentation of options if options print_options_documentation is set to yes.*/ 208 void mayPrintDoc(); 209 210 211 /** Get prefix to use for options.*/ prefix() const212 const char * prefix() const { 213 return prefix_.c_str(); 214 } 215 216 /** Set the value for options, output...*/ setOptionsAndJournalist(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions,Ipopt::SmartPtr<Ipopt::OptionsList> options,Ipopt::SmartPtr<Ipopt::Journalist> journalist)217 void setOptionsAndJournalist(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions, 218 Ipopt::SmartPtr<Ipopt::OptionsList> options, 219 Ipopt::SmartPtr<Ipopt::Journalist> journalist) 220 { 221 options_ = options; 222 roptions_ = roptions; 223 journalist_ = journalist; 224 } 225 226 /** Initialize the options and the journalist.*/ 227 void initializeOptionsAndJournalist(); 228 /** @} */ 229 230 /** @name Elements of the branch-and-bound setup.*/ 231 /** @{ */ 232 /** Pointer to the non-linear solver used.*/ nonlinearSolver()233 OsiTMINLPInterface * nonlinearSolver() 234 { 235 return nonlinearSolver_; 236 } 237 /** Pointer to the continuous solver to use for relaxations. */ continuousSolver()238 OsiSolverInterface * continuousSolver() 239 { 240 return continuousSolver_; 241 } 242 /** list of cutting planes methods to apply with their frequencies. */ cutGenerators()243 CuttingMethods& cutGenerators() 244 { 245 return cutGenerators_; 246 } 247 /** list of Heuristic methods to use. */ heuristics()248 HeuristicMethods& heuristics() 249 { 250 return heuristics_; 251 } 252 /** branching method to use. */ branchingMethod()253 OsiChooseVariable * branchingMethod() 254 { 255 return branchingMethod_; 256 } 257 /** Method used to compare nodes. */ nodeComparisonMethod()258 NodeComparison& nodeComparisonMethod() 259 { 260 return nodeComparisonMethod_; 261 } 262 /** Method used to traverse tree.*/ treeTraversalMethod()263 TreeTraversal treeTraversalMethod() 264 { 265 return treeTraversalMethod_; 266 } 267 /** Return value of integer parameter. */ getIntParameter(const IntParameter & p) const268 int getIntParameter(const IntParameter &p) const 269 { 270 return intParam_[p]; 271 } 272 /** Return value of double parameter.*/ getDoubleParameter(const DoubleParameter & p) const273 double getDoubleParameter(const DoubleParameter &p) const 274 { 275 return doubleParam_[p]; 276 } 277 /** Return value of integer parameter. */ setIntParameter(const IntParameter & p,const int v)278 void setIntParameter(const IntParameter &p, const int v) 279 { 280 intParam_[p] = v; 281 } 282 /** Return value of double parameter.*/ setDoubleParameter(const DoubleParameter & p,const double v)283 void setDoubleParameter(const DoubleParameter &p, const double v) 284 { 285 doubleParam_[p] = v; 286 } 287 /** @} */ 288 289 /** Get the values of base parameters from the options stored.*/ gatherParametersValues()290 void gatherParametersValues() 291 { 292 gatherParametersValues(options_); 293 } 294 /** Get the values of the base parameters from the passed options.*/ 295 void gatherParametersValues(Ipopt::SmartPtr<Ipopt::OptionsList> options); 296 /** Acces storage of Journalist for output */ journalist()297 Ipopt::SmartPtr<Ipopt::Journalist> journalist() 298 { 299 return journalist_; 300 } 301 302 /** Acces list of Options */ options()303 Ipopt::SmartPtr<Ipopt::OptionsList> options() 304 { 305 return options_; 306 } 307 308 /** Access registered Options */ roptions()309 Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions() 310 { 311 return roptions_; 312 } 313 314 /** Access to extra objects.*/ objects() const315 const vector<OsiObject *>& objects() const 316 { 317 return objects_; 318 } 319 320 /** Access to extra objects.*/ objects()321 vector<OsiObject *>& objects() 322 { 323 return objects_; 324 } 325 addCutGenerator(CuttingMethod & cg)326 void addCutGenerator(CuttingMethod & cg){ 327 cutGenerators_.push_back(cg); 328 } 329 set_linearizer(TMINLP2OsiLP * linearizer)330 void set_linearizer(TMINLP2OsiLP * linearizer){ 331 linearizer_ = linearizer; 332 } 333 334 protected: 335 /** Set the priorities into OsiTMINLPInterface when needed.*/ 336 void setPriorities(); 337 /** Add SOS constraints to OsiTMINLPInterface when needed.*/ 338 void addSos(); 339 340 /** storage of integer parameters.*/ 341 int intParam_[NumberIntParam]; 342 /** default values for int parameters.*/ 343 static int defaultIntParam_[NumberIntParam]; 344 /** storage of double parameters. */ 345 double doubleParam_[NumberDoubleParam]; 346 /** default values for double parameters. */ 347 static double defaultDoubleParam_[NumberDoubleParam]; 348 /** Storage of the non-linear solver used.*/ 349 OsiTMINLPInterface * nonlinearSolver_; 350 /** Storage of continuous solver.*/ 351 OsiSolverInterface * continuousSolver_; 352 /** Method to linearize MINLPs */ 353 Ipopt::SmartPtr<TMINLP2OsiLP> linearizer_; 354 /** Cut generation methods. */ 355 CuttingMethods cutGenerators_; 356 /** Heuristic methods. */ 357 HeuristicMethods heuristics_; 358 /** Branching method.*/ 359 OsiChooseVariable * branchingMethod_; 360 /** Node comparison method.*/ 361 NodeComparison nodeComparisonMethod_; 362 /** Tree traversal method.*/ 363 TreeTraversal treeTraversalMethod_; 364 /** Extra object to add to Cbc (not OsiObjects).*/ 365 vector<OsiObject *> objects_; 366 367 368 /** Storage of Journalist for output */ 369 Ipopt::SmartPtr<Ipopt::Journalist> journalist_; 370 371 /** List of Options */ 372 Ipopt::SmartPtr<Ipopt::OptionsList> options_; 373 374 /** Registered Options */ 375 Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions_; 376 377 /** flag to say if option file was read.*/ 378 bool readOptions_; 379 /** separate message handler.*/ 380 CoinMessageHandler * messageHandler_; 381 /** Prefix to use when reading options.*/ 382 std::string prefix_; 383 }; 384 }/* End namespace Bonmin. */ 385 #endif 386 387