source: branches/sandbox/Cbc/src/CbcTree.hpp @ 1393

Last change on this file since 1393 was 1393, checked in by lou, 10 years ago

Mark #if 0 with JJF_ZERO and #if 1 with JJF_ONE as a historical reference
point.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.2 KB
Line 
1/* $Id: CbcTree.hpp 1393 2009-12-11 00:29:38Z lou $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcTree_H
5#define CbcTree_H
6
7#include <vector>
8#include <algorithm>
9#include <cmath>
10
11#include "CoinFinite.hpp"
12#include "CoinHelperFunctions.hpp"
13#include "CbcCompare.hpp"
14
15/*! \class tree
16    \brief Implementation of live set as a heap.
17
18    This class is used to hold the set of live nodes in the search tree.
19*/
20//#define CBC_DUBIOUS_HEAP
21#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
22//#define CBC_DUBIOUS_HEAP
23#endif
24#ifndef CBC_DUBIOUS_HEAP
25class CbcTree {
26
27public:
28
29    // Default Constructor
30    CbcTree ();
31
32    // Copy constructor
33    CbcTree ( const CbcTree & rhs);
34    // = operator
35    CbcTree & operator=(const CbcTree & rhs);
36
37    virtual ~CbcTree();
38
39    /// Clone
40    virtual CbcTree * clone() const;
41    /// Create C++ lines to get to current state
42    virtual void generateCpp( FILE * ) {}
43
44    /*! \name Heap access and maintenance methods */
45//@{
46
47    /// Set comparison function and resort heap
48    void setComparison(CbcCompareBase  &compare);
49
50    /// Return the top node of the heap
51    virtual CbcNode * top() const;
52
53    /// Add a node to the heap
54    virtual void push(CbcNode * x);
55
56    /// Remove the top node from the heap
57    virtual void pop() ;
58    /// Gets best node and takes off heap
59    virtual CbcNode * bestNode(double cutoff);
60
61//@}
62    /*! \name vector methods */
63//@{
64
65    /// Test if empty *** note may be overridden
66    virtual bool empty() ;
67
68    /// Return size
69    virtual int size() const {
70        return nodes_.size();
71    }
72    /// [] operator
73    inline CbcNode * operator [] (int i) const {
74        return nodes_[i];
75    }
76
77    /// Return a node pointer
78    inline CbcNode * nodePointer (int i) const {
79        return nodes_[i];
80    }
81
82
83//@}
84
85    /*! \name Search tree maintenance */
86//@{
87
88    /*! \brief Prune the tree using an objective function cutoff
89
90      This routine removes all nodes with objective worst than the
91      specified cutoff value.
92      It also sets bestPossibleObjective to best
93      of all on tree before deleting.
94    */
95
96    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
97
98    /// Get best on list using alternate method
99    CbcNode * bestAlternate();
100
101    /// We may have got an intelligent tree so give it one more chance
102    virtual void endSearch() {}
103
104    /// Get best possible objective function in the tree
105    virtual double getBestPossibleObjective();
106    /// Reset maximum node number
107    inline void resetNodeNumbers() {
108        maximumNodeNumber_ = 0;
109    }
110    /// Get maximum node number
111    inline int maximumNodeNumber() const {
112        return maximumNodeNumber_;
113    }
114    /// Set number of branches
115    inline void setNumberBranching(int value) {
116        numberBranching_ = value;
117    }
118    /// Get number of branches
119    inline int getNumberBranching() const {
120        return numberBranching_;
121    }
122    /// Set maximum branches
123    inline void setMaximumBranching(int value) {
124        maximumBranching_ = value;
125    }
126    /// Get maximum branches
127    inline int getMaximumBranching() const {
128        return maximumBranching_;
129    }
130    /// Get branched variables
131    inline unsigned int * branched() const {
132        return branched_;
133    }
134    /// Get bounds
135    inline int * newBounds() const {
136        return newBound_;
137    }
138    /// Adds branching information to complete state
139    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
140                                 const double * currentLower,
141                                 const double * currentUpper);
142    /// Increase space for data
143    void increaseSpace();
144//@}
145protected:
146    std::vector <CbcNode *> nodes_;
147    CbcCompare comparison_;     ///> Sort function for heap ordering.
148    /// Maximum "node" number so far to split ties
149    int maximumNodeNumber_;
150    /// Size of variable list
151    int numberBranching_;
152    /// Maximum size of variable list
153    int maximumBranching_;
154    /** Integer variables branched or bounded
155        top bit set if new upper bound
156        next bit set if a branch
157    */
158    unsigned int * branched_;
159    /// New bound
160    int * newBound_;
161};
162/*! \class tree
163    \brief Implementation of live set as a managed array.
164
165    This class is used to hold the set of live nodes in the search tree.
166*/
167
168#ifdef JJF_ZERO // not used
169class CbcTreeArray : public CbcTree {
170
171public:
172
173    // Default Constructor
174    CbcTreeArray ();
175
176    // Copy constructor
177    CbcTreeArray ( const CbcTreeArray & rhs);
178    // = operator
179    CbcTreeArray & operator=(const CbcTreeArray & rhs);
180
181    virtual ~CbcTreeArray();
182
183    /// Clone
184    virtual CbcTree * clone() const;
185    /// Create C++ lines to get to current state
186    virtual void generateCpp( FILE * ) {}
187
188    /*! \name Heap access and maintenance methods */
189//@{
190
191    /// Set comparison function and resort heap
192    void setComparison(CbcCompareBase  &compare);
193
194    /// Add a node to the heap
195    virtual void push(CbcNode * x);
196
197    /// Gets best node and takes off heap
198    virtual CbcNode * bestNode(double cutoff);
199
200//@}
201    /*! \name vector methods */
202//@{
203
204    /// Test if empty *** note may be overridden
205    virtual bool empty() ;
206
207//@}
208
209    /*! \name Search tree maintenance */
210//@{
211
212    /*! \brief Prune the tree using an objective function cutoff
213
214      This routine removes all nodes with objective worst than the
215      specified cutoff value.
216      It also sets bestPossibleObjective to best
217      of all on tree before deleting.
218    */
219
220    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
221    /// Get best possible objective function in the tree
222    virtual double getBestPossibleObjective();
223//@}
224protected:
225    /// Returns
226    /// Last node
227    CbcNode * lastNode_;
228    /// Last node popped
229    CbcNode * lastNodePopped_;
230    /// Not used yet
231    int switches_;
232
233};
234
235/// New style
236#include "CoinSearchTree.hpp"
237/*! \class tree
238    \brief Implementation of live set as a heap.
239
240    This class is used to hold the set of live nodes in the search tree.
241*/
242
243class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
244
245public:
246
247    // Default Constructor
248    CbcNewTree ();
249
250    // Copy constructor
251    CbcNewTree ( const CbcNewTree & rhs);
252    // = operator
253    CbcNewTree & operator=(const CbcNewTree & rhs);
254
255    virtual ~CbcNewTree();
256
257    /// Clone
258    virtual CbcNewTree * clone() const;
259    /// Create C++ lines to get to current state
260    virtual void generateCpp( FILE * ) {}
261
262    /*! \name Heap access and maintenance methods */
263//@{
264
265    /// Set comparison function and resort heap
266    void setComparison(CbcCompareBase  &compare);
267
268    /// Return the top node of the heap
269    virtual CbcNode * top() const;
270
271    /// Add a node to the heap
272    virtual void push(CbcNode * x);
273
274    /// Remove the top node from the heap
275    virtual void pop() ;
276    /// Gets best node and takes off heap
277    virtual CbcNode * bestNode(double cutoff);
278
279//@}
280    /*! \name vector methods */
281//@{
282
283    /// Test if empty *** note may be overridden
284    virtual bool empty() ;
285
286    /// Return size
287    inline int size() const {
288        return nodes_.size();
289    }
290
291    /// [] operator
292    inline CbcNode * operator [] (int i) const {
293        return nodes_[i];
294    }
295
296    /// Return a node pointer
297    inline CbcNode * nodePointer (int i) const {
298        return nodes_[i];
299    }
300
301//@}
302
303    /*! \name Search tree maintenance */
304//@{
305
306    /*! \brief Prune the tree using an objective function cutoff
307
308      This routine removes all nodes with objective worst than the
309      specified cutoff value.
310      It also sets bestPossibleObjective to best
311      of all on tree before deleting.
312    */
313
314    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
315
316    /// Get best on list using alternate method
317    CbcNode * bestAlternate();
318
319    /// We may have got an intelligent tree so give it one more chance
320    virtual void endSearch() {}
321//@}
322protected:
323
324
325};
326#endif
327#else
328class CbcTree {
329
330public:
331
332    // Default Constructor
333    CbcTree ();
334
335    // Copy constructor
336    CbcTree ( const CbcTree & rhs);
337    // = operator
338    CbcTree & operator=(const CbcTree & rhs);
339
340    virtual ~CbcTree();
341
342    /// Clone
343    virtual CbcTree * clone() const;
344    /// Create C++ lines to get to current state
345    virtual void generateCpp( FILE * fp) {}
346
347    /*! \name Heap access and maintenance methods */
348//@{
349
350    /// Set comparison function and resort heap
351    void setComparison(CbcCompareBase  &compare);
352
353    /// Return the top node of the heap
354    virtual CbcNode * top() const;
355
356    /// Add a node to the heap
357    virtual void push(CbcNode * x);
358
359    /// Remove the top node from the heap
360    virtual void pop() ;
361    /// Gets best node and takes off heap
362    virtual CbcNode * bestNode(double cutoff);
363
364//@}
365    /*! \name vector methods */
366//@{
367
368    /// Test if empty *** note may be overridden
369    //virtual bool empty() ;
370
371    /// Return size
372    inline int size() const {
373        return nodes_.size();
374    }
375
376    /// [] operator
377    inline CbcNode * operator [] (int i) const {
378        return nodes_[i];
379    }
380
381    /// Return a node pointer
382    inline CbcNode * nodePointer (int i) const {
383        return nodes_[i];
384    }
385
386    virtual bool empty();
387    //inline int size() const { return size_; }
388    void realpop();
389    /** After changing data in the top node, fix the heap */
390    void fixTop();
391    void realpush(CbcNode * node);
392//@}
393
394    /*! \name Search tree maintenance */
395//@{
396
397    /*! \brief Prune the tree using an objective function cutoff
398
399      This routine removes all nodes with objective worst than the
400      specified cutoff value.
401      It also sets bestPossibleObjective to best
402      of all on tree before deleting.
403    */
404
405    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
406
407    /// Get best on list using alternate method
408    CbcNode * bestAlternate();
409
410    /// We may have got an intelligent tree so give it one more chance
411    virtual void endSearch() {}
412    /// Reset maximum node number
413    inline void resetNodeNumbers() {
414        maximumNodeNumber_ = 0;
415    }
416//@}
417protected:
418    std::vector <CbcNode *> nodes_;
419    CbcCompare comparison_;     ///> Sort function for heap ordering.
420    /// Maximum "node" number so far to split ties
421    int maximumNodeNumber_;
422
423
424};
425#endif
426#endif
427
Note: See TracBrowser for help on using the repository browser.