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

Last change on this file since 1943 was 1943, checked in by forrest, 5 years ago

more options, copy statistics structure analysis
start coding of "switch" variables i.e. badly scaled ints or hi/lo
changes to allow more influence on small branch and bound
changes to get correct printout with threads

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