Bonmin 1.8.9
Loading...
Searching...
No Matches
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"
20#include <list>
21namespace Bonmin
22{
23 class BabSetupBase;
26 class CbcDiver : public CbcTree
27 {
28 public:
31
33 CbcDiver(const CbcDiver &rhs);
34
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
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
324 {
325 delete comparisonDive_;
326 delete comparisonBound_;
327 }
328
329 // Copy constructor
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 CbcNode * top() const
Return top node (next node to process.*‍/.
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
CbcDfsDiver & operator=(const CbcDfsDiver &rhs)
Assignment operator.
int maxDepthBFS_
Maximum depth until which we'll do a bredth-first-search.
Definition BonDiver.hpp:295
virtual CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
int nBacktracks_
number of backtracks done in current dive.
Definition BonDiver.hpp:291
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
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 CbcTree * clone() const
Virtual copy constructor.
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.
virtual CbcTree * clone() const
Virtual copy constructor.
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 CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
CbcDiver & operator=(const CbcDiver &rhs)
Assignment operator.
virtual CbcNode * top() const
Return top node (next node to process.*‍/.
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 CbcNode * bestNode(double cutoff)
Remove the best node from the heap and return it.
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 double getBestPossibleObjective()
Get best possible objective function in the tree.
void initialize(BabSetupBase &b)
Initialize the method (get options)
virtual bool empty()
Test if empty.
CbcProbedDiver & operator=(const CbcProbedDiver &rhs)
Assignment operator.
virtual CbcTree * clone() const
Virtual copy constructor.
CbcProbedDiver()
Default constructor.
virtual CbcNode * top() const
Return top node (next node to process.*‍/.
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
virtual ~DiverCompare()
Definition BonDiver.hpp:323
void setNumberSolToStopDive(int val)
Set numberSolToStopDive_.
Definition BonDiver.hpp:385
virtual bool newSolution(CbcModel *model, double objectiveAtContinuous, int numberInfeasibilitiesAtContinuous)
Called after each new solution.
DiverCompare & operator=(const DiverCompare &rhs)
Definition BonDiver.hpp:340
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.
virtual CbcCompareBase * clone() const
Clone.
Definition BonDiver.hpp:358
void setNumberNodesToLimitTreeSize(int val)
Set numberNodesToLimitTreeSize_.
Definition BonDiver.hpp:391
(C) Copyright International Business Machines Corporation 2007