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