Bonmin  1.8.8
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:
31 
33  CbcDiver(const CbcDiver &rhs);
34 
36  CbcDiver & operator=(const CbcDiver &rhs);
37 
39  virtual ~CbcDiver();
40 
42  virtual CbcTree * clone() const;
43 
47  virtual CbcNode * top() const;
48 
50  virtual void push(CbcNode * x);
52  virtual void pop();
54  virtual CbcNode * bestNode(double cutoff);
58 
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 
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:
113 
116 
119 
121  virtual ~CbcProbedDiver();
122 
124  virtual CbcTree * clone() const;
125 
129  virtual CbcNode * top() const;
130 
132  virtual void push(CbcNode * x);
134  virtual void pop();
136  virtual CbcNode * bestNode(double cutoff);
140 
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 
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:
209 
212 
215 
217  virtual ~CbcDfsDiver();
218 
220  virtual CbcTree * clone() const;
221 
225  virtual CbcNode * top() const;
226 
228  virtual void push(CbcNode * x);
230  virtual void pop();
232  virtual CbcNode * bestNode(double cutoff);
236 
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 
265 //#endif
267  virtual void endSearch()
268  {}
269 
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 
A class to have all elements necessary to setup a branch-and-bound.
A more elaborate diving class.
Definition: BonDiver.hpp:200
virtual void push(CbcNode *x)
Add node to the heap.
void initialize(BabSetupBase &b)
Initialize the method (get options)
ComparisonModes getComparisonMode()
get the mode of comparison of the tree.
Definition: BonDiver.hpp:274
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:240
int maxDiveBacktracks_
Maximum number of backtrack in one dive.
Definition: BonDiver.hpp:297
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
void setComparisonMode(ComparisonModes newMode)
Changes the mode of comparison of the tree for "safety reasons" if the mode really changes we always ...
virtual ~CbcDfsDiver()
Destructor.
int maxDiveDepth_
Maximum depth to go from divingBoard.
Definition: BonDiver.hpp:299
int diveListSize_
Record dive list size for constant time access.
Definition: BonDiver.hpp:285
@ Enlarge
At the very beginning we might want to enlarge the tree just a bit.
Definition: BonDiver.hpp:203
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
int maxDepthBFS_
Maximum depth until which we'll do a bredth-first-search.
Definition: BonDiver.hpp:295
virtual CbcNode * top() const
Return top node (next node to process.*‍/.
int nBacktracks_
number of backtracks done in current dive.
Definition: BonDiver.hpp:291
CbcDfsDiver & operator=(const CbcDfsDiver &rhs)
Assignment operator.
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
int treeCleaning_
Flag to say that we are currently cleaning the tree and should work only on the heap.
Definition: BonDiver.hpp:281
virtual bool empty()
Test if empty.
ComparisonModes mode_
Current mode of the diving strategy.
Definition: BonDiver.hpp:301
CbcDfsDiver()
Default constructor.
std::list< CbcNode * > dive_
List of the nodes in the current dive.
Definition: BonDiver.hpp:283
virtual CbcTree * clone() const
Virtual copy constructor.
CbcDfsDiver(const CbcDfsDiver &rhs)
Copy constructor.
double cutoff_
Last reported cutoff.
Definition: BonDiver.hpp:289
virtual void pop()
Remove the top node of the heap.
int divingBoardDepth_
Depth of the node from which diving was started (we call this node the diving board).
Definition: BonDiver.hpp:287
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:267
Class to do diving in the tree.
Definition: BonDiver.hpp:27
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.
CbcDiver & operator=(const CbcDiver &rhs)
Assignment operator.
CbcDiver()
Default constructor.
virtual ~CbcDiver()
Destructor.
virtual int size()
Give size of the tree.
Definition: BonDiver.hpp:62
static void registerOptions(Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)
Register the options of the method.
virtual CbcTree * clone() const
Virtual copy constructor.
virtual CbcNode * top() const
Return top node (next node to process.*‍/.
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
virtual bool empty()
Test if empty.
virtual void pop()
Remove the top node of the heap.
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
CbcDiver(const CbcDiver &rhs)
Copy constructor.
virtual void push(CbcNode *x)
Add node to the heap.
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:82
Class to do probed diving in the tree.
Definition: BonDiver.hpp:109
virtual ~CbcProbedDiver()
Destructor.
virtual int size()
Give size of the tree.
Definition: BonDiver.hpp:144
virtual void pop()
Remove the top node of the heap.
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
CbcProbedDiver(const CbcProbedDiver &rhs)
Copy constructor.
virtual void endSearch()
Don't know what this is yet?
Definition: BonDiver.hpp:164
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
void initialize(BabSetupBase &b)
Initialize the method (get options)
CbcProbedDiver & operator=(const CbcProbedDiver &rhs)
Assignment operator.
virtual CbcNode * top() const
Return top node (next node to process.*‍/.
virtual bool empty()
Test if empty.
CbcProbedDiver()
Default constructor.
virtual CbcTree * clone() const
Virtual copy constructor.
virtual void push(CbcNode *x)
Add node to the heap.
void setComparisonBound(const CbcCompareBase &val)
Set comparison method when closing bound.
Definition: BonDiver.hpp:402
virtual bool newSolution(CbcModel *model)
Called after each new solution.
DiverCompare(const DiverCompare &rhs)
Definition: BonDiver.hpp:330
void setDiver(CbcDfsDiver *diver)
Set the dfs diver to use.
Definition: BonDiver.hpp:379
DiverCompare & operator=(const DiverCompare &rhs)
Definition: BonDiver.hpp:340
virtual ~DiverCompare()
Definition: BonDiver.hpp:323
virtual CbcCompareBase * clone() const
Clone.
Definition: BonDiver.hpp:358
void setNumberSolToStopDive(int val)
Set numberSolToStopDive_.
Definition: BonDiver.hpp:385
virtual bool newSolution(CbcModel *model, double objectiveAtContinuous, int numberInfeasibilitiesAtContinuous)
Called after each new solution.
virtual bool test(CbcNode *x, CbcNode *y)
This is test function.
void setComparisonDive(const CbcCompareBase &val)
Set comparison method when diving.
Definition: BonDiver.hpp:397
virtual bool every1000Nodes(CbcModel *model, int numberNodes)
Called 1000 nodes.
void setNumberNodesToLimitTreeSize(int val)
Set numberNodesToLimitTreeSize_.
Definition: BonDiver.hpp:391
(C) Copyright International Business Machines Corporation 2007