source: stable/2.8/Cbc/src/CbcTree.hpp @ 2128

Last change on this file since 2128 was 1813, checked in by forrest, 7 years ago

add random seed setting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.1 KB
Line 
1/* $Id: CbcTree.hpp 1813 2012-11-22 19:00:22Z forrest $ */
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#if 1 //ndef 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    void realpop();
117    /** After changing data in the top node, fix the heap */
118    void fixTop();
119    void realpush(CbcNode * node);
120//@}
121
122    /*! \name Search tree maintenance */
123//@{
124    /*! \brief Prune the tree using an objective function cutoff
125
126      This routine removes all nodes with objective worse than the
127      specified cutoff value. It also sets bestPossibleObjective to
128      the best objective over remaining nodes.
129    */
130    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
131
132    /// Get best on list using alternate method
133    CbcNode * bestAlternate();
134
135    /// We may have got an intelligent tree so give it one more chance
136    virtual void endSearch() {}
137
138    /// Get best possible objective function in the tree
139    virtual double getBestPossibleObjective();
140
141    /// Reset maximum node number
142    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
143
144    /// Get maximum node number
145    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
146
147    /// Set number of branches
148    inline void setNumberBranching(int value) { numberBranching_ = value; }
149
150    /// Get number of branches
151    inline int getNumberBranching() const { return numberBranching_; }
152
153    /// Set maximum branches
154    inline void setMaximumBranching(int value) { maximumBranching_ = value; }
155
156    /// Get maximum branches
157    inline int getMaximumBranching() const { return maximumBranching_; }
158
159    /// Get branched variables
160    inline unsigned int * branched() const { return branched_; }
161
162    /// Get bounds
163    inline int * newBounds() const { return newBound_; }
164
165    /// Adds branching information to complete state
166    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
167                                 const double * currentLower,
168                                 const double * currentUpper);
169    /// Increase space for data
170    void increaseSpace();
171//@}
172
173# if CBC_DEBUG_HEAP > 0
174  /*! \name Debugging methods */
175  //@{
176    /*! \brief Check that the heap property is satisfied. */
177    void validateHeap() ;
178  //@}
179# endif
180
181protected:
182    /// Storage vector for the heap
183    std::vector <CbcNode *> nodes_;
184          /// Sort predicate for heap ordering.
185    CbcCompare comparison_;
186    /// Maximum "node" number so far to split ties
187    int maximumNodeNumber_;
188    /// Size of variable list
189    int numberBranching_;
190    /// Maximum size of variable list
191    int maximumBranching_;
192    /** Integer variables branched or bounded
193        top bit set if new upper bound
194        next bit set if a branch
195    */
196    unsigned int * branched_;
197    /// New bound
198    int * newBound_;
199};
200
201#ifdef JJF_ZERO // not used
202/*! \brief Implementation of live set as a managed array.
203
204    This class is used to hold the set of live nodes in the search tree.
205*/
206class CbcTreeArray : public CbcTree {
207
208public:
209
210    // Default Constructor
211    CbcTreeArray ();
212
213    // Copy constructor
214    CbcTreeArray ( const CbcTreeArray & rhs);
215    // = operator
216    CbcTreeArray & operator=(const CbcTreeArray & rhs);
217
218    virtual ~CbcTreeArray();
219
220    /// Clone
221    virtual CbcTree * clone() const;
222    /// Create C++ lines to get to current state
223    virtual void generateCpp( FILE * ) {}
224
225    /*! \name Heap access and maintenance methods */
226//@{
227
228    /// Set comparison function and resort heap
229    void setComparison(CbcCompareBase  &compare);
230
231    /// Add a node to the heap
232    virtual void push(CbcNode * x);
233
234    /// Gets best node and takes off heap
235    virtual CbcNode * bestNode(double cutoff);
236
237//@}
238    /*! \name vector methods */
239//@{
240
241    /// Test if empty *** note may be overridden
242    virtual bool empty() ;
243
244//@}
245
246    /*! \name Search tree maintenance */
247//@{
248
249    /*! \brief Prune the tree using an objective function cutoff
250
251      This routine removes all nodes with objective worst than the
252      specified cutoff value.
253      It also sets bestPossibleObjective to best
254      of all on tree before deleting.
255    */
256
257    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
258    /// Get best possible objective function in the tree
259    virtual double getBestPossibleObjective();
260//@}
261protected:
262    /// Returns
263    /// Last node
264    CbcNode * lastNode_;
265    /// Last node popped
266    CbcNode * lastNodePopped_;
267    /// Not used yet
268    int switches_;
269
270};
271
272/// New style
273#include "CoinSearchTree.hpp"
274/*! \class tree
275    \brief Implementation of live set as a heap.
276
277    This class is used to hold the set of live nodes in the search tree.
278*/
279
280class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
281
282public:
283
284    // Default Constructor
285    CbcNewTree ();
286
287    // Copy constructor
288    CbcNewTree ( const CbcNewTree & rhs);
289    // = operator
290    CbcNewTree & operator=(const CbcNewTree & rhs);
291
292    virtual ~CbcNewTree();
293
294    /// Clone
295    virtual CbcNewTree * clone() const;
296    /// Create C++ lines to get to current state
297    virtual void generateCpp( FILE * ) {}
298
299    /*! \name Heap access and maintenance methods */
300//@{
301
302    /// Set comparison function and resort heap
303    void setComparison(CbcCompareBase  &compare);
304
305    /// Return the top node of the heap
306    virtual CbcNode * top() const;
307
308    /// Add a node to the heap
309    virtual void push(CbcNode * x);
310
311    /// Remove the top node from the heap
312    virtual void pop() ;
313    /// Gets best node and takes off heap
314    virtual CbcNode * bestNode(double cutoff);
315
316//@}
317    /*! \name vector methods */
318//@{
319
320    /// Test if empty *** note may be overridden
321    virtual bool empty() ;
322
323    /// Return size
324    inline int size() const {
325        return nodes_.size();
326    }
327
328    /// [] operator
329    inline CbcNode * operator [] (int i) const {
330        return nodes_[i];
331    }
332
333    /// Return a node pointer
334    inline CbcNode * nodePointer (int i) const {
335        return nodes_[i];
336    }
337
338//@}
339
340    /*! \name Search tree maintenance */
341//@{
342
343    /*! \brief Prune the tree using an objective function cutoff
344
345      This routine removes all nodes with objective worst than the
346      specified cutoff value.
347      It also sets bestPossibleObjective to best
348      of all on tree before deleting.
349    */
350
351    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
352
353    /// Get best on list using alternate method
354    CbcNode * bestAlternate();
355
356    /// We may have got an intelligent tree so give it one more chance
357    virtual void endSearch() {}
358//@}
359protected:
360
361
362};
363#endif
364#else
365/* CBC_DUBIOUS_HEAP is defined
366
367  See note at top of file. This code is highly suspect.
368  -- lh, 100921 --
369*/
370class CbcTree {
371
372public:
373
374    // Default Constructor
375    CbcTree ();
376
377    // Copy constructor
378    CbcTree ( const CbcTree & rhs);
379    // = operator
380    CbcTree & operator=(const CbcTree & rhs);
381
382    virtual ~CbcTree();
383
384    /// Clone
385    virtual CbcTree * clone() const;
386    /// Create C++ lines to get to current state
387    virtual void generateCpp( FILE * fp) {}
388
389    /*! \name Heap access and maintenance methods */
390//@{
391
392    /// Set comparison function and resort heap
393    void setComparison(CbcCompareBase  &compare);
394
395    /// Return the top node of the heap
396    virtual CbcNode * top() const;
397
398    /// Add a node to the heap
399    virtual void push(CbcNode * x);
400
401    /// Remove the top node from the heap
402    virtual void pop() ;
403    /// Gets best node and takes off heap
404    virtual CbcNode * bestNode(double cutoff);
405
406//@}
407    /*! \name vector methods */
408//@{
409
410    /// Test if empty *** note may be overridden
411    //virtual bool empty() ;
412
413    /// Return size
414    inline int size() const {
415        return nodes_.size();
416    }
417
418    /// [] operator
419    inline CbcNode * operator [] (int i) const {
420        return nodes_[i];
421    }
422
423    /// Return a node pointer
424    inline CbcNode * nodePointer (int i) const {
425        return nodes_[i];
426    }
427
428    virtual bool empty();
429    //inline int size() const { return size_; }
430    void realpop();
431    /** After changing data in the top node, fix the heap */
432    void fixTop();
433    void realpush(CbcNode * node);
434//@}
435
436    /*! \name Search tree maintenance */
437//@{
438
439    /*! \brief Prune the tree using an objective function cutoff
440
441      This routine removes all nodes with objective worst than the
442      specified cutoff value.
443      It also sets bestPossibleObjective to best
444      of all on tree before deleting.
445    */
446
447    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
448
449    /// Get best on list using alternate method
450    CbcNode * bestAlternate();
451
452    /// We may have got an intelligent tree so give it one more chance
453    virtual void endSearch() {}
454    /// Reset maximum node number
455    inline void resetNodeNumbers() {
456        maximumNodeNumber_ = 0;
457    }
458
459    /// Get maximum node number
460    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
461//@}
462protected:
463    std::vector <CbcNode *> nodes_;
464    CbcCompare comparison_;     ///> Sort function for heap ordering.
465    /// Maximum "node" number so far to split ties
466    int maximumNodeNumber_;
467
468
469};
470#endif
471#endif
472
Note: See TracBrowser for help on using the repository browser.