source: trunk/Cbc/src/CbcTree.hpp

Last change on this file was 2467, checked in by unxusr, 5 months ago

spaces after angles

  • 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 2467 2019-01-03 21:26:29Z 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/*! \class CbcTree
48    \brief Implementation of the live set as a heap.
49
50    This class is used to hold the set of live nodes in the search tree.
51*/
52class CbcTree {
53
54public:
55  /*! \name Constructors and related */
56  //@{
57  /// Default Constructor
58  CbcTree();
59
60  /// Copy constructor
61  CbcTree(const CbcTree &rhs);
62
63  /// = operator
64  CbcTree &operator=(const CbcTree &rhs);
65
66  /// Destructor
67  virtual ~CbcTree();
68
69  /// Clone
70  virtual CbcTree *clone() const;
71
72  /// Create C++ lines to get to current state
73  virtual void generateCpp(FILE *) {}
74  //@}
75
76  /*! \name Heap access and maintenance methods */
77  //@{
78  /// Set comparison function and resort heap
79  void setComparison(CbcCompareBase &compare);
80
81  /// Return the top node of the heap
82  virtual CbcNode *top() const;
83
84  /// Add a node to the heap
85  virtual void push(CbcNode *x);
86
87  /// Remove the top node from the heap
88  virtual void pop();
89
90  /*! \brief Gets best node and takes off heap
91
92      Before returning the node from the top of the heap, the node
93      is offered an opportunity to reevaluate itself. Callers should
94      be prepared to check that the node returned is suitable for use.
95    */
96  virtual CbcNode *bestNode(double cutoff);
97
98  /*! \brief Rebuild the heap */
99  virtual void rebuild();
100  //@}
101
102  /*! \name Direct node access methods */
103  //@{
104  /// Test for an empty tree
105  virtual bool empty();
106
107  /// Return size
108  virtual int size() const { return static_cast< int >(nodes_.size()); }
109
110  /// Return a node pointer
111  inline CbcNode *operator[](int i) const { return nodes_[i]; }
112
113  /// Return a node pointer
114  inline CbcNode *nodePointer(int i) const { return nodes_[i]; }
115  void realpop();
116  /** After changing data in the top node, fix the heap */
117  void fixTop();
118  void realpush(CbcNode *node);
119  //@}
120
121  /*! \name Search tree maintenance */
122  //@{
123  /*! \brief Prune the tree using an objective function cutoff
124
125      This routine removes all nodes with objective worse than the
126      specified cutoff value. It also sets bestPossibleObjective to
127      the best objective over remaining nodes.
128    */
129  virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
130
131  /// Get best on list using alternate method
132  CbcNode *bestAlternate();
133
134  /// We may have got an intelligent tree so give it one more chance
135  virtual void endSearch() {}
136
137  /// Get best possible objective function in the tree
138  virtual double getBestPossibleObjective();
139
140  /// Reset maximum node number
141  inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
142
143  /// Get maximum node number
144  inline int maximumNodeNumber() const { return maximumNodeNumber_; }
145
146  /// Set number of branches
147  inline void setNumberBranching(int value) { numberBranching_ = value; }
148
149  /// Get number of branches
150  inline int getNumberBranching() const { return numberBranching_; }
151
152  /// Set maximum branches
153  inline void setMaximumBranching(int value) { maximumBranching_ = value; }
154
155  /// Get maximum branches
156  inline int getMaximumBranching() const { return maximumBranching_; }
157
158  /// Get branched variables
159  inline unsigned int *branched() const { return branched_; }
160
161  /// Get bounds
162  inline int *newBounds() const { return newBound_; }
163
164  /// Last objective in branch-and-cut search tree
165  inline double lastObjective() const
166  {
167    return lastObjective_;
168  }
169  /// Last depth in branch-and-cut search tree
170  inline int lastDepth() const
171  {
172    return lastDepth_;
173  }
174  /// Last number of objects unsatisfied
175  inline int lastUnsatisfied() const
176  {
177    return lastUnsatisfied_;
178  }
179  /// Adds branching information to complete state
180  void addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo,
181    const double *currentLower,
182    const double *currentUpper);
183  /// Increase space for data
184  void increaseSpace();
185  //@}
186
187#if CBC_DEBUG_HEAP > 0
188  /*! \name Debugging methods */
189  //@{
190  /*! \brief Check that the heap property is satisfied. */
191  void validateHeap();
192  //@}
193#endif
194
195protected:
196  /// Storage vector for the heap
197  std::vector< CbcNode * > nodes_;
198  /// Sort predicate for heap ordering.
199  CbcCompare comparison_;
200  /// Maximum "node" number so far to split ties
201  int maximumNodeNumber_;
202  /// Size of variable list
203  int numberBranching_;
204  /// Maximum size of variable list
205  int maximumBranching_;
206  /// Objective of last node pushed on tree
207  double lastObjective_;
208  /// Depth of last node pushed on tree
209  int lastDepth_;
210  /// Number unsatisfied of last node pushed on tree
211  int lastUnsatisfied_;
212  /** Integer variables branched or bounded
213        top bit set if new upper bound
214        next bit set if a branch
215    */
216  unsigned int *branched_;
217  /// New bound
218  int *newBound_;
219};
220
221#ifdef JJF_ZERO // not used
222/*! \brief Implementation of live set as a managed array.
223
224    This class is used to hold the set of live nodes in the search tree.
225*/
226class CbcTreeArray : public CbcTree {
227
228public:
229  // Default Constructor
230  CbcTreeArray();
231
232  // Copy constructor
233  CbcTreeArray(const CbcTreeArray &rhs);
234  // = operator
235  CbcTreeArray &operator=(const CbcTreeArray &rhs);
236
237  virtual ~CbcTreeArray();
238
239  /// Clone
240  virtual CbcTree *clone() const;
241  /// Create C++ lines to get to current state
242  virtual void generateCpp(FILE *) {}
243
244  /*! \name Heap access and maintenance methods */
245  //@{
246
247  /// Set comparison function and resort heap
248  void setComparison(CbcCompareBase &compare);
249
250  /// Add a node to the heap
251  virtual void push(CbcNode *x);
252
253  /// Gets best node and takes off heap
254  virtual CbcNode *bestNode(double cutoff);
255
256  //@}
257  /*! \name vector methods */
258  //@{
259
260  /// Test if empty *** note may be overridden
261  virtual bool empty();
262
263  //@}
264
265  /*! \name Search tree maintenance */
266  //@{
267
268  /*! \brief Prune the tree using an objective function cutoff
269
270      This routine removes all nodes with objective worst than the
271      specified cutoff value.
272      It also sets bestPossibleObjective to best
273      of all on tree before deleting.
274    */
275
276  void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
277  /// Get best possible objective function in the tree
278  virtual double getBestPossibleObjective();
279  //@}
280protected:
281  /// Returns
282  /// Last node
283  CbcNode *lastNode_;
284  /// Last node popped
285  CbcNode *lastNodePopped_;
286  /// Not used yet
287  int switches_;
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  // Default Constructor
302  CbcNewTree();
303
304  // Copy constructor
305  CbcNewTree(const CbcNewTree &rhs);
306  // = operator
307  CbcNewTree &operator=(const CbcNewTree &rhs);
308
309  virtual ~CbcNewTree();
310
311  /// Clone
312  virtual CbcNewTree *clone() const;
313  /// Create C++ lines to get to current state
314  virtual void generateCpp(FILE *) {}
315
316  /*! \name Heap access and maintenance methods */
317  //@{
318
319  /// Set comparison function and resort heap
320  void setComparison(CbcCompareBase &compare);
321
322  /// Return the top node of the heap
323  virtual CbcNode *top() const;
324
325  /// Add a node to the heap
326  virtual void push(CbcNode *x);
327
328  /// Remove the top node from the heap
329  virtual void pop();
330  /// Gets best node and takes off heap
331  virtual CbcNode *bestNode(double cutoff);
332
333  //@}
334  /*! \name vector methods */
335  //@{
336
337  /// Test if empty *** note may be overridden
338  virtual bool empty();
339
340  /// Return size
341  inline int size() const
342  {
343    return nodes_.size();
344  }
345
346  /// [] operator
347  inline CbcNode *operator[](int i) const
348  {
349    return nodes_[i];
350  }
351
352  /// Return a node pointer
353  inline CbcNode *nodePointer(int i) const
354  {
355    return nodes_[i];
356  }
357
358  //@}
359
360  /*! \name Search tree maintenance */
361  //@{
362
363  /*! \brief Prune the tree using an objective function cutoff
364
365      This routine removes all nodes with objective worst than the
366      specified cutoff value.
367      It also sets bestPossibleObjective to best
368      of all on tree before deleting.
369    */
370
371  void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
372
373  /// Get best on list using alternate method
374  CbcNode *bestAlternate();
375
376  /// We may have got an intelligent tree so give it one more chance
377  virtual void endSearch() {}
378  //@}
379protected:
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  // Default Constructor
392  CbcTree();
393
394  // Copy constructor
395  CbcTree(const CbcTree &rhs);
396  // = operator
397  CbcTree &operator=(const CbcTree &rhs);
398
399  virtual ~CbcTree();
400
401  /// Clone
402  virtual CbcTree *clone() const;
403  /// Create C++ lines to get to current state
404  virtual void generateCpp(FILE *fp) {}
405
406  /*! \name Heap access and maintenance methods */
407  //@{
408
409  /// Set comparison function and resort heap
410  void setComparison(CbcCompareBase &compare);
411
412  /// Return the top node of the heap
413  virtual CbcNode *top() const;
414
415  /// Add a node to the heap
416  virtual void push(CbcNode *x);
417
418  /// Remove the top node from the heap
419  virtual void pop();
420  /// Gets best node and takes off heap
421  virtual CbcNode *bestNode(double cutoff);
422
423  //@}
424  /*! \name vector methods */
425  //@{
426
427  /// Test if empty *** note may be overridden
428  //virtual bool empty() ;
429
430  /// Return size
431  inline int size() const
432  {
433    return nodes_.size();
434  }
435
436  /// [] operator
437  inline CbcNode *operator[](int i) const
438  {
439    return nodes_[i];
440  }
441
442  /// Return a node pointer
443  inline CbcNode *nodePointer(int i) const
444  {
445    return nodes_[i];
446  }
447
448  virtual bool empty();
449  //inline int size() const { return size_; }
450  void realpop();
451  /** After changing data in the top node, fix the heap */
452  void fixTop();
453  void realpush(CbcNode *node);
454  //@}
455
456  /*! \name Search tree maintenance */
457  //@{
458
459  /*! \brief Prune the tree using an objective function cutoff
460
461      This routine removes all nodes with objective worst than the
462      specified cutoff value.
463      It also sets bestPossibleObjective to best
464      of all on tree before deleting.
465    */
466
467  void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective);
468
469  /// Get best on list using alternate method
470  CbcNode *bestAlternate();
471
472  /// We may have got an intelligent tree so give it one more chance
473  virtual void endSearch() {}
474  /// Reset maximum node number
475  inline void resetNodeNumbers()
476  {
477    maximumNodeNumber_ = 0;
478  }
479
480  /// Get maximum node number
481  inline int maximumNodeNumber() const { return maximumNodeNumber_; }
482  //@}
483protected:
484  std::vector< CbcNode * > nodes_;
485  CbcCompare comparison_; ///> Sort function for heap ordering.
486  /// Maximum "node" number so far to split ties
487  int maximumNodeNumber_;
488};
489#endif
490#endif
491
492/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
493*/
Note: See TracBrowser for help on using the repository browser.