Cbc 2.10.12
Loading...
Searching...
No Matches
CbcTree.hpp
Go to the documentation of this file.
1/* $Id$ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CbcTree_H
7#define CbcTree_H
8
9#include <vector>
10#include <algorithm>
11#include <cmath>
12
13#include "CoinHelperFunctions.hpp"
14#include "CbcCompare.hpp"
15
29//#define CBC_DUBIOUS_HEAP
30#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
31//#define CBC_DUBIOUS_HEAP
32#endif
33#if 1 //ndef CBC_DUBIOUS_HEAP
34
52class CbcTree {
53
54public:
59
61 CbcTree(const CbcTree &rhs);
62
65
67 virtual ~CbcTree();
68
70 virtual CbcTree *clone() const;
71
73 virtual void generateCpp(FILE *) {}
75
80
82 virtual CbcNode *top() const;
83
85 virtual void push(CbcNode *x);
86
88 virtual void pop();
89
96 virtual CbcNode *bestNode(double cutoff);
97
99 virtual void rebuild();
101
105 virtual bool empty();
106
108 virtual int size() const { return static_cast< int >(nodes_.size()); }
109
111 inline CbcNode *operator[](int i) const { return nodes_[i]; }
112
114 inline CbcNode *nodePointer(int i) const { return nodes_[i]; }
115 void realpop();
117 void fixTop();
118 void realpush(CbcNode *node);
120
129 virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
130
133
135 virtual void endSearch() {}
136
138 virtual double getBestPossibleObjective();
139
142
144 inline int maximumNodeNumber() const { return maximumNodeNumber_; }
145
147 inline void setNumberBranching(int value) { numberBranching_ = value; }
148
150 inline int getNumberBranching() const { return numberBranching_; }
151
153 inline void setMaximumBranching(int value) { maximumBranching_ = value; }
154
156 inline int getMaximumBranching() const { return maximumBranching_; }
157
159 inline unsigned int *branched() const { return branched_; }
160
162 inline int *newBounds() const { return newBound_; }
163
165 inline double lastObjective() const
166 {
167 return lastObjective_;
168 }
170 inline int lastDepth() const
171 {
172 return lastDepth_;
173 }
175 inline int lastUnsatisfied() const
176 {
177 return lastUnsatisfied_;
178 }
180 void addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo,
181 const double *currentLower,
182 const double *currentUpper);
186
187#if CBC_DEBUG_HEAP > 0
191 void validateHeap();
193#endif
194
195protected:
197 std::vector< CbcNode * > nodes_;
216 unsigned int *branched_;
219};
220
221#ifdef JJF_ZERO // not used
226class CbcTreeArray : public CbcTree {
227
228public:
229 // Default Constructor
230 CbcTreeArray();
231
232 // Copy constructor
233 CbcTreeArray(const CbcTreeArray &rhs);
234 // = operator
235 CbcTreeArray &operator=(const CbcTreeArray &rhs);
236
237 virtual ~CbcTreeArray();
238
240 virtual CbcTree *clone() const;
242 virtual void generateCpp(FILE *) {}
243
246
248 void setComparison(CbcCompareBase &compare);
249
251 virtual void push(CbcNode *x);
252
254 virtual CbcNode *bestNode(double cutoff);
255
257
259
261 virtual bool empty();
262
264
267
276 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
278 virtual double getBestPossibleObjective();
280protected:
283 CbcNode *lastNode_;
285 CbcNode *lastNodePopped_;
287 int switches_;
288};
289
291#include "CoinSearchTree.hpp"
298class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
299
300public:
301 // Default Constructor
302 CbcNewTree();
303
304 // Copy constructor
305 CbcNewTree(const CbcNewTree &rhs);
306 // = operator
307 CbcNewTree &operator=(const CbcNewTree &rhs);
308
309 virtual ~CbcNewTree();
310
312 virtual CbcNewTree *clone() const;
314 virtual void generateCpp(FILE *) {}
315
318
320 void setComparison(CbcCompareBase &compare);
321
323 virtual CbcNode *top() const;
324
326 virtual void push(CbcNode *x);
327
329 virtual void pop();
331 virtual CbcNode *bestNode(double cutoff);
332
334
336
338 virtual bool empty();
339
341 inline int size() const
342 {
343 return nodes_.size();
344 }
345
347 inline CbcNode *operator[](int i) const
348 {
349 return nodes_[i];
350 }
351
353 inline CbcNode *nodePointer(int i) const
354 {
355 return nodes_[i];
356 }
357
359
362
371 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
372
374 CbcNode *bestAlternate();
375
377 virtual void endSearch() {}
379protected:
380};
381#endif
382#else
383/* CBC_DUBIOUS_HEAP is defined
384
385 See note at top of file. This code is highly suspect.
386 -- lh, 100921 --
387*/
388class CbcTree {
389
390public:
391 // Default Constructor
392 CbcTree();
393
394 // Copy constructor
395 CbcTree(const CbcTree &rhs);
396 // = operator
397 CbcTree &operator=(const CbcTree &rhs);
398
399 virtual ~CbcTree();
400
402 virtual CbcTree *clone() const;
404 virtual void generateCpp(FILE *fp) {}
405
408
410 void setComparison(CbcCompareBase &compare);
411
413 virtual CbcNode *top() const;
414
416 virtual void push(CbcNode *x);
417
419 virtual void pop();
421 virtual CbcNode *bestNode(double cutoff);
422
424
426
428 //virtual bool empty() ;
429
431 inline int size() const
432 {
433 return nodes_.size();
434 }
435
437 inline CbcNode *operator[](int i) const
438 {
439 return nodes_[i];
440 }
441
443 inline CbcNode *nodePointer(int i) const
444 {
445 return nodes_[i];
446 }
447
448 virtual bool empty();
449 //inline int size() const { return size_; }
450 void realpop();
452 void fixTop();
453 void realpush(CbcNode *node);
455
458
467 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
468
471
473 virtual void endSearch() {}
475 inline void resetNodeNumbers()
476 {
478 }
479
481 inline int maximumNodeNumber() const { return maximumNodeNumber_; }
483protected:
484 std::vector< CbcNode * > nodes_;
488};
489#endif
490#endif
491
492/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
493*/
Simple Branch and bound class.
Definition CbcModel.hpp:100
Information required to recreate the subproblem at this node.
Information required while the node is live.
Definition CbcNode.hpp:49
Using MS heap implementation.
Definition CbcTree.hpp:52
int lastDepth_
Depth of last node pushed on tree.
Definition CbcTree.hpp:209
CbcTree & operator=(const CbcTree &rhs)
= operator
int maximumBranching_
Maximum size of variable list.
Definition CbcTree.hpp:205
CbcNode * bestAlternate()
Get best on list using alternate method.
virtual CbcTree * clone() const
Clone.
virtual CbcNode * bestNode(double cutoff)
Gets best node and takes off heap.
virtual ~CbcTree()
Destructor.
void setComparison(CbcCompareBase &compare)
Set comparison function and resort heap.
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
Definition CbcTree.hpp:135
double lastObjective_
Objective of last node pushed on tree.
Definition CbcTree.hpp:207
void increaseSpace()
Increase space for data.
void setNumberBranching(int value)
Set number of branches.
Definition CbcTree.hpp:147
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
int numberBranching_
Size of variable list.
Definition CbcTree.hpp:203
double lastObjective() const
Last objective in branch-and-cut search tree.
Definition CbcTree.hpp:165
virtual CbcNode * top() const
Return the top node of the heap.
CbcNode * nodePointer(int i) const
Return a node pointer.
Definition CbcTree.hpp:114
int maximumNodeNumber_
Maximum "node" number so far to split ties.
Definition CbcTree.hpp:201
virtual void rebuild()
Rebuild the heap.
int lastUnsatisfied() const
Last number of objects unsatisfied.
Definition CbcTree.hpp:175
void addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo, const double *currentLower, const double *currentUpper)
Adds branching information to complete state.
int * newBounds() const
Get bounds.
Definition CbcTree.hpp:162
int maximumNodeNumber() const
Get maximum node number.
Definition CbcTree.hpp:144
int lastUnsatisfied_
Number unsatisfied of last node pushed on tree.
Definition CbcTree.hpp:211
virtual bool empty()
Test for an empty tree.
CbcTree(const CbcTree &rhs)
Copy constructor.
void fixTop()
After changing data in the top node, fix the heap.
virtual void push(CbcNode *x)
Add a node to the heap.
unsigned int * branched() const
Get branched variables.
Definition CbcTree.hpp:159
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
CbcTree()
Default Constructor.
void resetNodeNumbers()
Reset maximum node number.
Definition CbcTree.hpp:141
void realpop()
int getNumberBranching() const
Get number of branches.
Definition CbcTree.hpp:150
CbcNode * operator[](int i) const
Return a node pointer.
Definition CbcTree.hpp:111
virtual void pop()
Remove the top node from the heap.
void setMaximumBranching(int value)
Set maximum branches.
Definition CbcTree.hpp:153
unsigned int * branched_
Integer variables branched or bounded top bit set if new upper bound next bit set if a branch.
Definition CbcTree.hpp:216
void realpush(CbcNode *node)
virtual int size() const
Return size.
Definition CbcTree.hpp:108
std::vector< CbcNode * > nodes_
Storage vector for the heap.
Definition CbcTree.hpp:197
int getMaximumBranching() const
Get maximum branches.
Definition CbcTree.hpp:156
int lastDepth() const
Last depth in branch-and-cut search tree.
Definition CbcTree.hpp:170
int * newBound_
New bound.
Definition CbcTree.hpp:218
CbcCompare comparison_
Sort predicate for heap ordering.
Definition CbcTree.hpp:199
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
Definition CbcTree.hpp:73