source: trunk/Cbc/src/CbcTree.hpp @ 1573

Last change on this file since 1573 was 1573, checked in by lou, 8 years ago

Change to EPL license notice.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.9 KB
Line 
1/* $Id: CbcTree.hpp 1573 2011-01-05 01:12:36Z lou $ */
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 "CoinFinite.hpp"
14#include "CoinHelperFunctions.hpp"
15#include "CbcCompare.hpp"
16
17/*! \brief Using MS heap implementation
18
19  It's unclear if this is needed any longer, or even if it should be allowed.
20  Cbc occasionally tries to do things to the tree (typically tweaking the
21  comparison predicate) that can cause a violation of the heap property (parent better
22  than either child). In a debug build, Microsoft's heap implementation does checks that
23  detect this and fail. This symbol switched to an alternate implementation of CbcTree,
24  and there are clearly differences, but no explanation as to why or what for.
25
26  As of 100921, the code is cleaned up to make it through `cbc -unitTest' without
27  triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can
28  be used for debugging if this turns up again.
29*/
30//#define CBC_DUBIOUS_HEAP
31#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
32//#define CBC_DUBIOUS_HEAP
33#endif
34#ifndef CBC_DUBIOUS_HEAP
35
36/*! \brief Controls search tree debugging
37
38  In order to have validateHeap() available, set CBC_DEBUG_HEAP
39  to 1 or higher.
40
41  - 1 calls validateHeap() after each change to the heap
42  - 2 will print a line for major operations (clean, set comparison, etc.)
43  - 3 will print information about each push and pop
44
45#define CBC_DEBUG_HEAP 1
46*/
47
48
49/*! \class CbcTree
50    \brief Implementation of the live set as a heap.
51
52    This class is used to hold the set of live nodes in the search tree.
53*/
54class CbcTree {
55
56public:
57    /*! \name Constructors and related */
58//@{
59    /// Default Constructor
60    CbcTree ();
61
62    /// Copy constructor
63    CbcTree (const CbcTree &rhs);
64
65    /// = operator
66    CbcTree & operator=(const CbcTree &rhs);
67
68    /// Destructor
69    virtual ~CbcTree();
70
71    /// Clone
72    virtual CbcTree * clone() const;
73
74    /// Create C++ lines to get to current state
75    virtual void generateCpp(FILE *) {}
76//@}
77
78    /*! \name Heap access and maintenance methods */
79//@{
80    /// Set comparison function and resort heap
81    void setComparison(CbcCompareBase &compare);
82
83    /// Return the top node of the heap
84    virtual CbcNode * top() const;
85
86    /// Add a node to the heap
87    virtual void push(CbcNode *x);
88
89    /// Remove the top node from the heap
90    virtual void pop() ;
91
92    /*! \brief Gets best node and takes off heap
93
94      Before returning the node from the top of the heap, the node
95      is offered an opportunity to reevaluate itself. Callers should
96      be prepared to check that the node returned is suitable for use.
97    */
98    virtual CbcNode * bestNode(double cutoff);
99
100    /*! \brief Rebuild the heap */
101    virtual void rebuild() ;
102//@}
103
104    /*! \name Direct node access methods */
105//@{
106    /// Test for an empty tree
107    virtual bool empty() ;
108
109    /// Return size
110    virtual int size() const { return static_cast<int>(nodes_.size()); }
111
112    /// Return a node pointer
113    inline CbcNode * operator [] (int i) const { return nodes_[i]; }
114
115    /// Return a node pointer
116    inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
117//@}
118
119    /*! \name Search tree maintenance */
120//@{
121    /*! \brief Prune the tree using an objective function cutoff
122
123      This routine removes all nodes with objective worse than the
124      specified cutoff value. It also sets bestPossibleObjective to
125      the best objective over remaining nodes.
126    */
127    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
128
129    /// Get best on list using alternate method
130    CbcNode * bestAlternate();
131
132    /// We may have got an intelligent tree so give it one more chance
133    virtual void endSearch() {}
134
135    /// Get best possible objective function in the tree
136    virtual double getBestPossibleObjective();
137
138    /// Reset maximum node number
139    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
140
141    /// Get maximum node number
142    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
143
144    /// Set number of branches
145    inline void setNumberBranching(int value) { numberBranching_ = value; }
146
147    /// Get number of branches
148    inline int getNumberBranching() const { return numberBranching_; }
149
150    /// Set maximum branches
151    inline void setMaximumBranching(int value) { maximumBranching_ = value; }
152
153    /// Get maximum branches
154    inline int getMaximumBranching() const { return maximumBranching_; }
155
156    /// Get branched variables
157    inline unsigned int * branched() const { return branched_; }
158
159    /// Get bounds
160    inline int * newBounds() const { return newBound_; }
161
162    /// Adds branching information to complete state
163    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
164                                 const double * currentLower,
165                                 const double * currentUpper);
166    /// Increase space for data
167    void increaseSpace();
168//@}
169
170# if CBC_DEBUG_HEAP > 0
171  /*! \name Debugging methods */
172  //@{
173    /*! \brief Check that the heap property is satisfied. */
174    void validateHeap() ;
175  //@}
176# endif
177
178protected:
179    /// Storage vector for the heap
180    std::vector <CbcNode *> nodes_;
181          /// Sort predicate for heap ordering.
182    CbcCompare comparison_;
183    /// Maximum "node" number so far to split ties
184    int maximumNodeNumber_;
185    /// Size of variable list
186    int numberBranching_;
187    /// Maximum size of variable list
188    int maximumBranching_;
189    /** Integer variables branched or bounded
190        top bit set if new upper bound
191        next bit set if a branch
192    */
193    unsigned int * branched_;
194    /// New bound
195    int * newBound_;
196};
197
198#ifdef JJF_ZERO // not used
199/*! \brief Implementation of live set as a managed array.
200
201    This class is used to hold the set of live nodes in the search tree.
202*/
203class CbcTreeArray : public CbcTree {
204
205public:
206
207    // Default Constructor
208    CbcTreeArray ();
209
210    // Copy constructor
211    CbcTreeArray ( const CbcTreeArray & rhs);
212    // = operator
213    CbcTreeArray & operator=(const CbcTreeArray & rhs);
214
215    virtual ~CbcTreeArray();
216
217    /// Clone
218    virtual CbcTree * clone() const;
219    /// Create C++ lines to get to current state
220    virtual void generateCpp( FILE * ) {}
221
222    /*! \name Heap access and maintenance methods */
223//@{
224
225    /// Set comparison function and resort heap
226    void setComparison(CbcCompareBase  &compare);
227
228    /// Add a node to the heap
229    virtual void push(CbcNode * x);
230
231    /// Gets best node and takes off heap
232    virtual CbcNode * bestNode(double cutoff);
233
234//@}
235    /*! \name vector methods */
236//@{
237
238    /// Test if empty *** note may be overridden
239    virtual bool empty() ;
240
241//@}
242
243    /*! \name Search tree maintenance */
244//@{
245
246    /*! \brief Prune the tree using an objective function cutoff
247
248      This routine removes all nodes with objective worst than the
249      specified cutoff value.
250      It also sets bestPossibleObjective to best
251      of all on tree before deleting.
252    */
253
254    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
255    /// Get best possible objective function in the tree
256    virtual double getBestPossibleObjective();
257//@}
258protected:
259    /// Returns
260    /// Last node
261    CbcNode * lastNode_;
262    /// Last node popped
263    CbcNode * lastNodePopped_;
264    /// Not used yet
265    int switches_;
266
267};
268
269/// New style
270#include "CoinSearchTree.hpp"
271/*! \class tree
272    \brief Implementation of live set as a heap.
273
274    This class is used to hold the set of live nodes in the search tree.
275*/
276
277class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
278
279public:
280
281    // Default Constructor
282    CbcNewTree ();
283
284    // Copy constructor
285    CbcNewTree ( const CbcNewTree & rhs);
286    // = operator
287    CbcNewTree & operator=(const CbcNewTree & rhs);
288
289    virtual ~CbcNewTree();
290
291    /// Clone
292    virtual CbcNewTree * clone() const;
293    /// Create C++ lines to get to current state
294    virtual void generateCpp( FILE * ) {}
295
296    /*! \name Heap access and maintenance methods */
297//@{
298
299    /// Set comparison function and resort heap
300    void setComparison(CbcCompareBase  &compare);
301
302    /// Return the top node of the heap
303    virtual CbcNode * top() const;
304
305    /// Add a node to the heap
306    virtual void push(CbcNode * x);
307
308    /// Remove the top node from the heap
309    virtual void pop() ;
310    /// Gets best node and takes off heap
311    virtual CbcNode * bestNode(double cutoff);
312
313//@}
314    /*! \name vector methods */
315//@{
316
317    /// Test if empty *** note may be overridden
318    virtual bool empty() ;
319
320    /// Return size
321    inline int size() const {
322        return nodes_.size();
323    }
324
325    /// [] operator
326    inline CbcNode * operator [] (int i) const {
327        return nodes_[i];
328    }
329
330    /// Return a node pointer
331    inline CbcNode * nodePointer (int i) const {
332        return nodes_[i];
333    }
334
335//@}
336
337    /*! \name Search tree maintenance */
338//@{
339
340    /*! \brief Prune the tree using an objective function cutoff
341
342      This routine removes all nodes with objective worst than the
343      specified cutoff value.
344      It also sets bestPossibleObjective to best
345      of all on tree before deleting.
346    */
347
348    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
349
350    /// Get best on list using alternate method
351    CbcNode * bestAlternate();
352
353    /// We may have got an intelligent tree so give it one more chance
354    virtual void endSearch() {}
355//@}
356protected:
357
358
359};
360#endif
361#else
362/* CBC_DUBIOUS_HEAP is defined
363
364  See note at top of file. This code is highly suspect.
365  -- lh, 100921 --
366*/
367class CbcTree {
368
369public:
370
371    // Default Constructor
372    CbcTree ();
373
374    // Copy constructor
375    CbcTree ( const CbcTree & rhs);
376    // = operator
377    CbcTree & operator=(const CbcTree & rhs);
378
379    virtual ~CbcTree();
380
381    /// Clone
382    virtual CbcTree * clone() const;
383    /// Create C++ lines to get to current state
384    virtual void generateCpp( FILE * fp) {}
385
386    /*! \name Heap access and maintenance methods */
387//@{
388
389    /// Set comparison function and resort heap
390    void setComparison(CbcCompareBase  &compare);
391
392    /// Return the top node of the heap
393    virtual CbcNode * top() const;
394
395    /// Add a node to the heap
396    virtual void push(CbcNode * x);
397
398    /// Remove the top node from the heap
399    virtual void pop() ;
400    /// Gets best node and takes off heap
401    virtual CbcNode * bestNode(double cutoff);
402
403//@}
404    /*! \name vector methods */
405//@{
406
407    /// Test if empty *** note may be overridden
408    //virtual bool empty() ;
409
410    /// Return size
411    inline int size() const {
412        return nodes_.size();
413    }
414
415    /// [] operator
416    inline CbcNode * operator [] (int i) const {
417        return nodes_[i];
418    }
419
420    /// Return a node pointer
421    inline CbcNode * nodePointer (int i) const {
422        return nodes_[i];
423    }
424
425    virtual bool empty();
426    //inline int size() const { return size_; }
427    void realpop();
428    /** After changing data in the top node, fix the heap */
429    void fixTop();
430    void realpush(CbcNode * node);
431//@}
432
433    /*! \name Search tree maintenance */
434//@{
435
436    /*! \brief Prune the tree using an objective function cutoff
437
438      This routine removes all nodes with objective worst than the
439      specified cutoff value.
440      It also sets bestPossibleObjective to best
441      of all on tree before deleting.
442    */
443
444    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
445
446    /// Get best on list using alternate method
447    CbcNode * bestAlternate();
448
449    /// We may have got an intelligent tree so give it one more chance
450    virtual void endSearch() {}
451    /// Reset maximum node number
452    inline void resetNodeNumbers() {
453        maximumNodeNumber_ = 0;
454    }
455//@}
456protected:
457    std::vector <CbcNode *> nodes_;
458    CbcCompare comparison_;     ///> Sort function for heap ordering.
459    /// Maximum "node" number so far to split ties
460    int maximumNodeNumber_;
461
462
463};
464#endif
465#endif
466
Note: See TracBrowser for help on using the repository browser.