File: CbcTree.hpp

package info (click to toggle)
coinor-cbc 2.9.9+repack1-1
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 7,848 kB
  • ctags: 5,787
  • sloc: cpp: 104,337; sh: 8,921; xml: 2,950; makefile: 520; ansic: 491; awk: 197
file content (490 lines) | stat: -rw-r--r-- 13,004 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
/* $Id: CbcTree.hpp 1943 2013-07-21 09:05:45Z forrest $ */
// Copyright (C) 2004, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#ifndef CbcTree_H
#define CbcTree_H

#include <vector>
#include <algorithm>
#include <cmath>

#include "CoinHelperFunctions.hpp"
#include "CbcCompare.hpp"

/*! \brief Using MS heap implementation

  It's unclear if this is needed any longer, or even if it should be allowed.
  Cbc occasionally tries to do things to the tree (typically tweaking the
  comparison predicate) that can cause a violation of the heap property (parent better
  than either child). In a debug build, Microsoft's heap implementation does checks that
  detect this and fail. This symbol switched to an alternate implementation of CbcTree,
  and there are clearly differences, but no explanation as to why or what for.

  As of 100921, the code is cleaned up to make it through `cbc -unitTest' without
  triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can
  be used for debugging if this turns up again.
*/
//#define CBC_DUBIOUS_HEAP
#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
//#define CBC_DUBIOUS_HEAP
#endif
#if 1 //ndef CBC_DUBIOUS_HEAP

/*! \brief Controls search tree debugging

  In order to have validateHeap() available, set CBC_DEBUG_HEAP
  to 1 or higher.

  - 1 calls validateHeap() after each change to the heap
  - 2 will print a line for major operations (clean, set comparison, etc.)
  - 3 will print information about each push and pop

#define CBC_DEBUG_HEAP 1
*/


/*! \class CbcTree
    \brief Implementation of the live set as a heap.

    This class is used to hold the set of live nodes in the search tree.
*/
class CbcTree {

public:
    /*! \name Constructors and related */
//@{
    /// Default Constructor
    CbcTree ();

    /// Copy constructor
    CbcTree (const CbcTree &rhs);

    /// = operator
    CbcTree & operator=(const CbcTree &rhs);

    /// Destructor
    virtual ~CbcTree();

    /// Clone
    virtual CbcTree * clone() const;

    /// Create C++ lines to get to current state
    virtual void generateCpp(FILE *) {}
//@}

    /*! \name Heap access and maintenance methods */
//@{
    /// Set comparison function and resort heap
    void setComparison(CbcCompareBase &compare);

    /// Return the top node of the heap
    virtual CbcNode * top() const;

    /// Add a node to the heap
    virtual void push(CbcNode *x);

    /// Remove the top node from the heap
    virtual void pop() ;

    /*! \brief Gets best node and takes off heap

      Before returning the node from the top of the heap, the node
      is offered an opportunity to reevaluate itself. Callers should
      be prepared to check that the node returned is suitable for use.
    */
    virtual CbcNode * bestNode(double cutoff);

    /*! \brief Rebuild the heap */
    virtual void rebuild() ;
//@}

    /*! \name Direct node access methods */
//@{
    /// Test for an empty tree
    virtual bool empty() ;

    /// Return size
    virtual int size() const { return static_cast<int>(nodes_.size()); }

    /// Return a node pointer
    inline CbcNode * operator [] (int i) const { return nodes_[i]; }

    /// Return a node pointer
    inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
    void realpop();
    /** After changing data in the top node, fix the heap */
    void fixTop();
    void realpush(CbcNode * node);
//@}

    /*! \name Search tree maintenance */
//@{
    /*! \brief Prune the tree using an objective function cutoff

      This routine removes all nodes with objective worse than the
      specified cutoff value. It also sets bestPossibleObjective to
      the best objective over remaining nodes.
    */
    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);

    /// Get best on list using alternate method
    CbcNode * bestAlternate();

    /// We may have got an intelligent tree so give it one more chance
    virtual void endSearch() {}

    /// Get best possible objective function in the tree
    virtual double getBestPossibleObjective();

    /// Reset maximum node number
    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }

    /// Get maximum node number
    inline int maximumNodeNumber() const { return maximumNodeNumber_; }

    /// Set number of branches
    inline void setNumberBranching(int value) { numberBranching_ = value; }

    /// Get number of branches
    inline int getNumberBranching() const { return numberBranching_; }

    /// Set maximum branches
    inline void setMaximumBranching(int value) { maximumBranching_ = value; }

    /// Get maximum branches
    inline int getMaximumBranching() const { return maximumBranching_; }

    /// Get branched variables
    inline unsigned int * branched() const { return branched_; }

    /// Get bounds
    inline int * newBounds() const { return newBound_; }

    /// Last objective in branch-and-cut search tree
    inline double lastObjective() const {
        return lastObjective_;
    }
    /// Last depth in branch-and-cut search tree
    inline int lastDepth() const {
        return lastDepth_;
    }
    /// Last number of objects unsatisfied
    inline int lastUnsatisfied() const {
        return lastUnsatisfied_;
    }
    /// Adds branching information to complete state
    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
                                 const double * currentLower,
                                 const double * currentUpper);
    /// Increase space for data
    void increaseSpace();
//@}

# if CBC_DEBUG_HEAP > 0
  /*! \name Debugging methods */
  //@{
    /*! \brief Check that the heap property is satisfied. */
    void validateHeap() ;
  //@}
# endif

protected:
    /// Storage vector for the heap
    std::vector <CbcNode *> nodes_;
    /// Sort predicate for heap ordering.
    CbcCompare comparison_;
    /// Maximum "node" number so far to split ties
    int maximumNodeNumber_;
    /// Size of variable list
    int numberBranching_;
    /// Maximum size of variable list
    int maximumBranching_;
    /// Objective of last node pushed on tree
    double lastObjective_;
    /// Depth of last node pushed on tree
    int lastDepth_;
    /// Number unsatisfied of last node pushed on tree
    int lastUnsatisfied_;
    /** Integer variables branched or bounded
        top bit set if new upper bound
        next bit set if a branch
    */
    unsigned int * branched_;
    /// New bound
    int * newBound_;
};

#ifdef JJF_ZERO // not used
/*! \brief Implementation of live set as a managed array.

    This class is used to hold the set of live nodes in the search tree.
*/
class CbcTreeArray : public CbcTree {

public:

    // Default Constructor
    CbcTreeArray ();

    // Copy constructor
    CbcTreeArray ( const CbcTreeArray & rhs);
    // = operator
    CbcTreeArray & operator=(const CbcTreeArray & rhs);

    virtual ~CbcTreeArray();

    /// Clone
    virtual CbcTree * clone() const;
    /// Create C++ lines to get to current state
    virtual void generateCpp( FILE * ) {}

    /*! \name Heap access and maintenance methods */
//@{

    /// Set comparison function and resort heap
    void setComparison(CbcCompareBase  &compare);

    /// Add a node to the heap
    virtual void push(CbcNode * x);

    /// Gets best node and takes off heap
    virtual CbcNode * bestNode(double cutoff);

//@}
    /*! \name vector methods */
//@{

    /// Test if empty *** note may be overridden
    virtual bool empty() ;

//@}

    /*! \name Search tree maintenance */
//@{

    /*! \brief Prune the tree using an objective function cutoff

      This routine removes all nodes with objective worst than the
      specified cutoff value.
      It also sets bestPossibleObjective to best
      of all on tree before deleting.
    */

    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    /// Get best possible objective function in the tree
    virtual double getBestPossibleObjective();
//@}
protected:
    /// Returns
    /// Last node
    CbcNode * lastNode_;
    /// Last node popped
    CbcNode * lastNodePopped_;
    /// Not used yet
    int switches_;

};

/// New style
#include "CoinSearchTree.hpp"
/*! \class tree
    \brief Implementation of live set as a heap.

    This class is used to hold the set of live nodes in the search tree.
*/

class CbcNewTree : public CbcTree, public CoinSearchTreeManager {

public:

    // Default Constructor
    CbcNewTree ();

    // Copy constructor
    CbcNewTree ( const CbcNewTree & rhs);
    // = operator
    CbcNewTree & operator=(const CbcNewTree & rhs);

    virtual ~CbcNewTree();

    /// Clone
    virtual CbcNewTree * clone() const;
    /// Create C++ lines to get to current state
    virtual void generateCpp( FILE * ) {}

    /*! \name Heap access and maintenance methods */
//@{

    /// Set comparison function and resort heap
    void setComparison(CbcCompareBase  &compare);

    /// Return the top node of the heap
    virtual CbcNode * top() const;

    /// Add a node to the heap
    virtual void push(CbcNode * x);

    /// Remove the top node from the heap
    virtual void pop() ;
    /// Gets best node and takes off heap
    virtual CbcNode * bestNode(double cutoff);

//@}
    /*! \name vector methods */
//@{

    /// Test if empty *** note may be overridden
    virtual bool empty() ;

    /// Return size
    inline int size() const {
        return nodes_.size();
    }

    /// [] operator
    inline CbcNode * operator [] (int i) const {
        return nodes_[i];
    }

    /// Return a node pointer
    inline CbcNode * nodePointer (int i) const {
        return nodes_[i];
    }

//@}

    /*! \name Search tree maintenance */
//@{

    /*! \brief Prune the tree using an objective function cutoff

      This routine removes all nodes with objective worst than the
      specified cutoff value.
      It also sets bestPossibleObjective to best
      of all on tree before deleting.
    */

    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);

    /// Get best on list using alternate method
    CbcNode * bestAlternate();

    /// We may have got an intelligent tree so give it one more chance
    virtual void endSearch() {}
//@}
protected:


};
#endif
#else
/* CBC_DUBIOUS_HEAP is defined

  See note at top of file. This code is highly suspect.
  -- lh, 100921 --
*/
class CbcTree {

public:

    // Default Constructor
    CbcTree ();

    // Copy constructor
    CbcTree ( const CbcTree & rhs);
    // = operator
    CbcTree & operator=(const CbcTree & rhs);

    virtual ~CbcTree();

    /// Clone
    virtual CbcTree * clone() const;
    /// Create C++ lines to get to current state
    virtual void generateCpp( FILE * fp) {}

    /*! \name Heap access and maintenance methods */
//@{

    /// Set comparison function and resort heap
    void setComparison(CbcCompareBase  &compare);

    /// Return the top node of the heap
    virtual CbcNode * top() const;

    /// Add a node to the heap
    virtual void push(CbcNode * x);

    /// Remove the top node from the heap
    virtual void pop() ;
    /// Gets best node and takes off heap
    virtual CbcNode * bestNode(double cutoff);

//@}
    /*! \name vector methods */
//@{

    /// Test if empty *** note may be overridden
    //virtual bool empty() ;

    /// Return size
    inline int size() const {
        return nodes_.size();
    }

    /// [] operator
    inline CbcNode * operator [] (int i) const {
        return nodes_[i];
    }

    /// Return a node pointer
    inline CbcNode * nodePointer (int i) const {
        return nodes_[i];
    }

    virtual bool empty();
    //inline int size() const { return size_; }
    void realpop();
    /** After changing data in the top node, fix the heap */
    void fixTop();
    void realpush(CbcNode * node);
//@}

    /*! \name Search tree maintenance */
//@{

    /*! \brief Prune the tree using an objective function cutoff

      This routine removes all nodes with objective worst than the
      specified cutoff value.
      It also sets bestPossibleObjective to best
      of all on tree before deleting.
    */

    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);

    /// Get best on list using alternate method
    CbcNode * bestAlternate();

    /// We may have got an intelligent tree so give it one more chance
    virtual void endSearch() {}
    /// Reset maximum node number
    inline void resetNodeNumbers() {
        maximumNodeNumber_ = 0;
    }

    /// Get maximum node number
    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
//@}
protected:
    std::vector <CbcNode *> nodes_;
    CbcCompare comparison_;	///> Sort function for heap ordering.
    /// Maximum "node" number so far to split ties
    int maximumNodeNumber_;


};
#endif
#endif