Bonmin  1.8.7
BonDiver.hpp
Go to the documentation of this file.
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 : 09/01/2007
9 
10 #ifndef BonDiver_H
11 #define BonDiver_H
12 
13 #include "BonminConfig.h"
14 #include "CbcCompareBase.hpp"
15 #include "CbcTree.hpp"
16 #include "IpRegOptions.hpp"
17 #include "IpOptionsList.hpp"
18 #include "CbcCompareActual.hpp"
19 #include "BonRegisteredOptions.hpp"
20 #include <list>
21 namespace Bonmin
22 {
23  class BabSetupBase;
26  class CbcDiver : public CbcTree
27  {
28  public:
30  CbcDiver();
31 
33  CbcDiver(const CbcDiver &rhs);
34 
36  CbcDiver & operator=(const CbcDiver &rhs);
37 
39  virtual ~CbcDiver();
40 
42  virtual CbcTree * clone() const;
43 
46  virtual CbcNode * top() const;
48 
50  virtual void push(CbcNode * x);
52  virtual void pop();
54  virtual CbcNode * bestNode(double cutoff);
57 
60  virtual bool empty();
62  virtual int size()
63  {
64  return (static_cast<int>(nodes_.size()) + (nextOnBranch_ != NULL) );
65  }
75  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
76 
78  virtual double getBestPossibleObjective();
79 
80 
82  virtual void endSearch()
83  {
84  nextOnBranch_ = NULL;
85  }
86 
89 
91  void initialize(BabSetupBase &b);
92 
93  private:
95  bool treeCleaning_;
97  CbcNode * nextOnBranch_;
100  bool stop_diving_on_cutoff_;
101  };
102 
103 
108  class CbcProbedDiver : public CbcTree
109  {
110  public:
112  CbcProbedDiver();
113 
115  CbcProbedDiver(const CbcProbedDiver &rhs);
116 
119 
121  virtual ~CbcProbedDiver();
122 
124  virtual CbcTree * clone() const;
125 
128  virtual CbcNode * top() const;
130 
132  virtual void push(CbcNode * x);
134  virtual void pop();
136  virtual CbcNode * bestNode(double cutoff);
139 
142  virtual bool empty();
144  virtual int size()
145  {
146  return (static_cast<int>(nodes_.size()) + (nextOnBranch_ != NULL) + (candidateChild_ != NULL) );
147  }
157  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
158 
160  virtual double getBestPossibleObjective();
161 
162 
164  virtual void endSearch()
165  {
166  nextOnBranch_ = NULL;
167  }
168 
170  void initialize(BabSetupBase &b);
171 
172  private:
174  bool treeCleaning_;
176  CbcNode * nextOnBranch_;
178  CbcNode * candidateChild_;
181  bool stop_diving_on_cutoff_;
182  };
183 
184 
199  class CbcDfsDiver :public CbcTree
200  {
201  public:
208  CbcDfsDiver();
209 
211  CbcDfsDiver(const CbcDfsDiver &rhs);
212 
214  CbcDfsDiver & operator=(const CbcDfsDiver &rhs);
215 
217  virtual ~CbcDfsDiver();
218 
220  virtual CbcTree * clone() const;
221 
224  virtual CbcNode * top() const;
226 
228  virtual void push(CbcNode * x);
230  virtual void pop();
232  virtual CbcNode * bestNode(double cutoff);
235 
238  virtual bool empty();
240  virtual int size()
241  {
242  return static_cast<int>(nodes_.size()) + diveListSize_;
243  }
254  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
255 
257  virtual double getBestPossibleObjective();
258 
259 //#ifdef COIN_HAS_BONMIN
262 
264  void initialize(BabSetupBase &b);
265 //#endif
267  virtual void endSearch()
268  {}
269 
272  void setComparisonMode(ComparisonModes newMode);
275  {
276  return mode_;
277  }
278  protected:
283  std::list<CbcNode *> dive_;
289  double cutoff_;
303  private:
305  void pushDiveOntoHeap(double cutoff);
306 
307  };
308 
309  class DiverCompare : public CbcCompareBase
310  {
311  public:
312  // Default Constructor
314  CbcCompareBase(),
315  diver_(NULL),
316  numberSolToStopDive_(5),
317  numberNodesToLimitTreeSize_(1000000),
318  comparisonDive_(NULL),
319  comparisonBound_(NULL)
320  {}
321 
322 
323  virtual ~DiverCompare()
324  {
325  delete comparisonDive_;
326  delete comparisonBound_;
327  }
328 
329  // Copy constructor
330  DiverCompare ( const DiverCompare & rhs):
331  CbcCompareBase(rhs),
332  diver_(rhs.diver_),
333  numberSolToStopDive_(rhs.numberSolToStopDive_),
334  numberNodesToLimitTreeSize_(rhs.numberNodesToLimitTreeSize_),
335  comparisonDive_(rhs.comparisonDive_->clone()),
336  comparisonBound_(rhs.comparisonBound_->clone())
337  {}
338 
339  // Assignment operator
341  {
342  if (this != &rhs) {
343  CbcCompareBase::operator=(rhs);
344  diver_ = rhs.diver_;
345  numberSolToStopDive_ = rhs.numberSolToStopDive_;
346  numberNodesToLimitTreeSize_ = rhs.numberNodesToLimitTreeSize_;
347  delete comparisonDive_;
348  delete comparisonBound_;
349  comparisonDive_ = NULL;
350  comparisonBound_ = NULL;
351  if (rhs.comparisonDive_) comparisonDive_ = rhs.comparisonDive_->clone();
352  if (rhs.comparisonBound_) comparisonBound_ = rhs.comparisonBound_->clone();
353  }
354  return *this;
355  }
356 
358  virtual CbcCompareBase * clone() const
359  {
360  return new DiverCompare(*this);
361  }
362 
364  virtual bool test (CbcNode * x, CbcNode * y);
365 
367  virtual bool newSolution(CbcModel * model);
368 
370  virtual bool newSolution(CbcModel * model,
371  double objectiveAtContinuous,
372  int numberInfeasibilitiesAtContinuous);
373 
376  virtual bool every1000Nodes(CbcModel * model,int numberNodes);
377 
379  void setDiver(CbcDfsDiver * diver)
380  {
381  diver_ = diver;
382  }
383 
386  {
387  numberSolToStopDive_ = val;
388  }
389 
392  {
393  numberNodesToLimitTreeSize_ = val;
394  }
395 
397  void setComparisonDive(const CbcCompareBase & val)
398  {
399  comparisonDive_ = val.clone();
400  }
402  void setComparisonBound(const CbcCompareBase & val)
403  {
404  comparisonBound_ = val.clone();
405  }
406  private:
408  CbcDfsDiver * diver_;
410  int numberSolToStopDive_;
412  int numberNodesToLimitTreeSize_;
414  CbcCompareBase * comparisonDive_;
416  CbcCompareBase * comparisonBound_;
418  CbcCompareDepth comparisonDepth_;
419  };
420 
421 }/* Ends bonmin namespace.*/
422 
423 #endif
424 
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
Number * x
void setComparisonBound(const CbcCompareBase &val)
Set comparison method when closing bound.
Definition: BonDiver.hpp:402
void setNumberSolToStopDive(int val)
Set numberSolToStopDive_.
Definition: BonDiver.hpp:385
void initialize(BabSetupBase &b)
Initialize the method (get options)
virtual void pop()
Remove the top node of the heap.
DiverCompare(const DiverCompare &rhs)
Definition: BonDiver.hpp:330
int treeCleaning_
Flag to say that we are currently cleaning the tree and should work only on the heap.
Definition: BonDiver.hpp:281
std::list< CbcNode * > dive_
List of the nodes in the current dive.
Definition: BonDiver.hpp:283
int nBacktracks_
number of backtracks done in current dive.
Definition: BonDiver.hpp:291
virtual bool empty()
Test if empty.
CbcDiver & operator=(const CbcDiver &rhs)
Assignment operator.
virtual CbcCompareBase * clone() const
Clone.
Definition: BonDiver.hpp:358
ComparisonModes mode_
Current mode of the diving strategy.
Definition: BonDiver.hpp:301
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
int diveListSize_
Record dive list size for constant time access.
Definition: BonDiver.hpp:285
double cutoff_
Last reported cutoff.
Definition: BonDiver.hpp:289
virtual CbcTree * clone() const
Virtual copy constructor.
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:82
CbcProbedDiver & operator=(const CbcProbedDiver &rhs)
Assignment operator.
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:164
(C) Copyright International Business Machines Corporation 2007
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
virtual ~CbcDfsDiver()
Destructor.
virtual void push(CbcNode *x)
Add node to the heap.
virtual int size()
Give size of the tree.
Definition: BonDiver.hpp:240
virtual bool every1000Nodes(CbcModel *model, int numberNodes)
Called 1000 nodes.
void setComparisonMode(ComparisonModes newMode)
Changes the mode of comparison of the tree for "safety reasons" if the mode really changes we always ...
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:267
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
virtual bool empty()
Test if empty.
static void registerOptions(Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
Register the options of the method.
virtual CbcTree * clone() const
Virtual copy constructor.
virtual void push(CbcNode *x)
Add node to the heap.
virtual ~CbcDiver()
Destructor.
virtual int size()
Give size of the tree.
Definition: BonDiver.hpp:144
char char * val
void initialize(BabSetupBase &b)
Initialize the method (get options)
At the very beginning we might want to enlarge the tree just a bit.
Definition: BonDiver.hpp:203
void setComparisonDive(const CbcCompareBase &val)
Set comparison method when diving.
Definition: BonDiver.hpp:397
CbcDfsDiver & operator=(const CbcDfsDiver &rhs)
Assignment operator.
virtual CbcNode * top() const
Return top node (next node to process.*/.
virtual ~CbcProbedDiver()
Destructor.
CbcProbedDiver()
Default constructor.
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
DiverCompare & operator=(const DiverCompare &rhs)
Definition: BonDiver.hpp:340
int maxDiveDepth_
Maximum depth to go from divingBoard.
Definition: BonDiver.hpp:299
void setDiver(CbcDfsDiver *diver)
Set the dfs diver to use.
Definition: BonDiver.hpp:379
virtual bool empty()
Test if empty.
Class to do diving in the tree.
Definition: BonDiver.hpp:26
A class to have all elements necessary to setup a branch-and-bound.
virtual bool test(CbcNode *x, CbcNode *y)
This is test function.
static void registerOptions(Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
Register the options of the method.
virtual int size()
Give size of the tree.
Definition: BonDiver.hpp:62
void initialize(BabSetupBase &b)
Initialize the method (get options)
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
Class to do probed diving in the tree.
Definition: BonDiver.hpp:108
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
void setNumberNodesToLimitTreeSize(int val)
Set numberNodesToLimitTreeSize_.
Definition: BonDiver.hpp:391
virtual void push(CbcNode *x)
Add node to the heap.
CbcDiver()
Default constructor.
A more elaborate diving class.
Definition: BonDiver.hpp:199
virtual void pop()
Remove the top node of the heap.
int maxDepthBFS_
Maximum depth until which we'll do a bredth-first-search.
Definition: BonDiver.hpp:295
int maxDiveBacktracks_
Maximum number of backtrack in one dive.
Definition: BonDiver.hpp:297
virtual CbcTree * clone() const
Virtual copy constructor.
ComparisonModes getComparisonMode()
get the mode of comparison of the tree.
Definition: BonDiver.hpp:274
virtual CbcNode * top() const
Return top node (next node to process.*/.
virtual void pop()
Remove the top node of the heap.
CbcDfsDiver()
Default constructor.
int divingBoardDepth_
Depth of the node from which diving was started (we call this node the diving board).
Definition: BonDiver.hpp:287
virtual CbcNode * top() const
Return top node (next node to process.*/.
virtual bool newSolution(CbcModel *model)
Called after each new solution.
virtual ~DiverCompare()
Definition: BonDiver.hpp:323