source: branches/sandbox/Cbc/src/CbcTree_stroP.hpp @ 1286

Last change on this file since 1286 was 1278, checked in by bjarni, 10 years ago

Astyle conversion with --pad-oper (-p) to add consistent padding around operators.

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