source: releases/2.7.1/Cbc/src/CbcTree.hpp @ 1995

Last change on this file since 1995 was 1675, checked in by stefan, 8 years ago

sync with trunk rev1674

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