source: branches/sandbox/Cbc/src/CbcTree.cpp @ 1389

Last change on this file since 1389 was 1342, checked in by dfylstra, 10 years ago

Removed (via #ifdef 0) class CbcTreeArray? and CbcNewTree? - not used according to John Forrest

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 39.5 KB
Line 
1/* $Id: CbcTree.cpp 1342 2009-12-03 17:33:17Z caphillSNL $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4
5#include "CbcModel.hpp"
6#include "CbcNode.hpp"
7#include "CbcTree.hpp"
8#include "CbcCountRowCut.hpp"
9#include "CbcCompareActual.hpp"
10#include "CbcBranchActual.hpp"
11
12CbcTree::CbcTree()
13{
14    maximumNodeNumber_ = 0;
15    numberBranching_ = 0;
16    maximumBranching_ = 0;
17    branched_ = NULL;
18    newBound_ = NULL;
19}
20CbcTree::~CbcTree()
21{
22    delete [] branched_;
23    delete [] newBound_;
24}
25// Copy constructor
26CbcTree::CbcTree ( const CbcTree & rhs)
27{
28    nodes_ = rhs.nodes_;
29    maximumNodeNumber_ = rhs.maximumNodeNumber_;
30    numberBranching_ = rhs.numberBranching_;
31    maximumBranching_ = rhs.maximumBranching_;
32    if (maximumBranching_ > 0) {
33        branched_ = CoinCopyOfArray(rhs.branched_, maximumBranching_);
34        newBound_ = CoinCopyOfArray(rhs.newBound_, maximumBranching_);
35    } else {
36        branched_ = NULL;
37        newBound_ = NULL;
38    }
39}
40// Assignment operator
41CbcTree &
42CbcTree::operator=(const CbcTree & rhs)
43{
44    if (this != &rhs) {
45        nodes_ = rhs.nodes_;
46        maximumNodeNumber_ = rhs.maximumNodeNumber_;
47        delete [] branched_;
48        delete [] newBound_;
49        numberBranching_ = rhs.numberBranching_;
50        maximumBranching_ = rhs.maximumBranching_;
51        if (maximumBranching_ > 0) {
52            branched_ = CoinCopyOfArray(rhs.branched_, maximumBranching_);
53            newBound_ = CoinCopyOfArray(rhs.newBound_, maximumBranching_);
54        } else {
55            branched_ = NULL;
56            newBound_ = NULL;
57        }
58    }
59    return *this;
60}
61// Adds branching information to complete state
62void
63CbcTree::addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
64                                 const double * currentLower,
65                                 const double * currentUpper)
66{
67    const OsiBranchingObject * objA  = nodeInfo->owner()->branchingObject();
68    const CbcIntegerBranchingObject * objBranch  = dynamic_cast<const CbcIntegerBranchingObject *> (objA);
69    if (objBranch) {
70        const CbcObject * objB = objBranch->object();
71        const CbcSimpleInteger * obj = dynamic_cast<const CbcSimpleInteger *> (objB);
72        assert (obj);
73        int iColumn = obj->columnNumber();
74        const double * down = objBranch->downBounds();
75        const double * up = objBranch->upBounds();
76        assert (currentLower[iColumn] == down[0]);
77        assert (currentUpper[iColumn] == up[1]);
78        if (dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo)) {
79            const CbcPartialNodeInfo * info = dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo);
80            const double * newBounds = info->newBounds();
81            const int * variables = info->variables();
82            int numberChanged = info->numberChangedBounds();
83            for (int i = 0; i < numberChanged; i++) {
84                int jColumn = variables[i];
85                int kColumn = jColumn & (~0x80000000);
86                if (iColumn == kColumn) {
87                    jColumn |= 0x40000000;
88#ifndef NDEBUG
89                    double value = newBounds[i];
90                    if ((jColumn&0x80000000) == 0) {
91                        assert (value == up[0]);
92                    } else {
93                        assert (value == down[1]);
94                    }
95#endif
96                }
97                if (numberBranching_ == maximumBranching_)
98                    increaseSpace();
99                newBound_[numberBranching_] = static_cast<int> (newBounds[i]);
100                branched_[numberBranching_++] = jColumn;
101            }
102        } else {
103            const CbcFullNodeInfo * info = dynamic_cast<const CbcFullNodeInfo *> (nodeInfo);
104            int numberIntegers = model->numberIntegers();
105            const int * which = model->integerVariable();
106            const double * newLower = info->lower();
107            const double * newUpper = info->upper();
108            if (numberBranching_ == maximumBranching_)
109                increaseSpace();
110            assert (newLower[iColumn] == up[0] ||
111                    newUpper[iColumn] == down[1]);
112            int jColumn = iColumn | 0x40000000;
113            if (newLower[iColumn] == up[0]) {
114                newBound_[numberBranching_] = static_cast<int> (up[0]);
115            } else {
116                newBound_[numberBranching_] = static_cast<int> (down[1]);
117                jColumn |= 0x80000000;
118            }
119            branched_[numberBranching_++] = jColumn;
120            for (int i = 0; i < numberIntegers; i++) {
121                int jColumn = which[i];
122                assert (currentLower[jColumn] == newLower[jColumn] ||
123                        currentUpper[jColumn] == newUpper[jColumn]);
124                if (jColumn != iColumn) {
125                    bool changed = false;
126                    double value;
127                    if (newLower[jColumn] > currentLower[jColumn]) {
128                        value = newLower[jColumn];
129                        changed = true;
130                    } else if (newUpper[jColumn] < currentUpper[jColumn]) {
131                        value = newUpper[jColumn];
132                        jColumn |= 0x80000000;
133                        changed = true;
134                    }
135                    if (changed) {
136                        if (numberBranching_ == maximumBranching_)
137                            increaseSpace();
138                        newBound_[numberBranching_] = static_cast<int> (value);
139                        branched_[numberBranching_++] = jColumn;
140                    }
141                }
142            }
143        }
144    } else {
145        // switch off
146        delete [] branched_;
147        delete [] newBound_;
148        maximumBranching_ = -1;
149        branched_ = NULL;
150        newBound_ = NULL;
151    }
152}
153// Increase space for data
154void
155CbcTree::increaseSpace()
156{
157    assert (numberBranching_ == maximumBranching_);
158    maximumBranching_ = (3 * maximumBranching_ + 10) >> 1;
159    unsigned int * temp1 = CoinCopyOfArrayPartial(branched_, maximumBranching_, numberBranching_);
160    delete [] branched_;
161    branched_ = temp1;
162    int * temp2 = CoinCopyOfArrayPartial(newBound_, maximumBranching_, numberBranching_);
163    delete [] newBound_;
164    newBound_ = temp2;
165}
166// Clone
167CbcTree *
168CbcTree::clone() const
169{
170    return new CbcTree(*this);
171}
172//#define CBC_DEBUG_HEAP
173#ifndef CBC_DUBIOUS_HEAP
174// Set comparison function and resort heap
175void
176CbcTree::setComparison(CbcCompareBase  &compare)
177{
178    comparison_.test_ = &compare;
179    CbcCompareDefault * compareD = dynamic_cast<CbcCompareDefault *>
180                                   (&compare);
181    if (compareD) {
182        // clean up diving
183        compareD->cleanDive();
184    }
185    std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
186}
187
188// Return the top node of the heap
189CbcNode *
190CbcTree::top() const
191{
192    return nodes_.front();
193}
194
195// Add a node to the heap
196void
197CbcTree::push(CbcNode * x)
198{
199    x->setNodeNumber(maximumNodeNumber_);
200    maximumNodeNumber_++;
201    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
202       x->objectiveValue(),x->nodeInfo()->decrement(0),
203       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
204    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
205    x->setOnTree(true);
206    nodes_.push_back(x);
207    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
208}
209
210// Remove the top node from the heap
211void
212CbcTree::pop()
213{
214    nodes_.front()->setOnTree(false);
215    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
216    nodes_.pop_back();
217}
218
219// Test if empty *** note may be overridden
220bool
221CbcTree::empty()
222{
223    return nodes_.empty();
224}
225// Gets best node and takes off heap
226CbcNode *
227CbcTree::bestNode(double cutoff)
228{
229    CbcNode * best = NULL;
230    while (!best && nodes_.size()) {
231        best = nodes_.front();
232        if (best)
233            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
234        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
235            assert (best->nodeInfo()->numberBranchesLeft());
236        if (best && best->objectiveValue() >= cutoff) {
237            // double check in case node can change its mind!
238            best->checkIsCutoff(cutoff);
239        }
240        if (!best || best->objectiveValue() >= cutoff) {
241#if 0
242            // take off
243            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
244            nodes_.pop_back();
245            delete best;
246            best = NULL;
247#else
248            // let code get rid of it
249            assert (best);
250#endif
251        }
252    }
253    // switched off for now
254    if (best && comparison_.test_->fullScan() && false) {
255        CbcNode * saveBest = best;
256        int n = nodes_.size();
257        int iBest = -1;
258        for (int i = 0; i < n; i++) {
259            // temp
260            assert (nodes_[i]);
261            assert (nodes_[i]->nodeInfo());
262            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
263                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
264            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
265                    && comparison_.alternateTest(best, nodes_[i])) {
266                best = nodes_[i];
267                iBest = i;
268            }
269        }
270        if (best == saveBest) {
271            // can pop
272            // take off
273            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
274            nodes_.pop_back();
275        } else {
276            // make impossible
277            nodes_[iBest] = NULL;
278        }
279    } else if (best) {
280        // take off
281        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
282        nodes_.pop_back();
283    }
284#ifdef DEBUG_CBC_HEAP
285    if (best) {
286        int n = nodes_.size();
287        bool good = true;
288        for (int i = 0; i < n; i++) {
289            // temp
290            assert (nodes_[i]);
291            if (!comparison_.compareNodes(nodes_[i], best)) {
292                good = false;
293                CbcNode * x = nodes_[i];
294                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
295                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
296                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
297            }
298        }
299        if (!good) {
300            // compare best to all
301            int i;
302            for (i = 0; i < n; i++) {
303                CbcNode * x = nodes_[i];
304                printf("i=%d x is nun %d depth %d obj %g", i,
305                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
306                if (!comparison_.compareNodes(x, best)) {
307                    printf(" - best is worse!\n");
308                } else {
309                    printf("\n");
310                }
311            }
312            // Now compare amongst rest
313            for (i = 0; i < n; i++) {
314                CbcNode * x = nodes_[i];
315                printf("For i=%d ", i);
316                for (int j = i + 1; j < n; j++) {
317                    CbcNode * y = nodes_[j];
318                    if (!comparison_.compareNodes(x, y)) {
319                        printf(" b %d", j);
320                    } else {
321                        printf(" w %d", j);
322                    }
323                }
324                printf("\n");
325            }
326            assert(good);
327        }
328    }
329#endif
330    if (best)
331        best->setOnTree(false);
332    return best;
333}
334
335double
336CbcTree::getBestPossibleObjective()
337{
338    double r_val = 1e100;
339    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
340        if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
341            r_val = nodes_[i]->objectiveValue();
342        }
343    }
344    return r_val;
345}
346/*! \brief Prune the tree using an objective function cutoff
347
348  This routine removes all nodes with objective worst than the
349  specified cutoff value.
350*/
351
352void
353CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
354{
355    int j;
356    int nNodes = size();
357    CbcNode ** nodeArray = new CbcNode * [nNodes];
358    int * depth = new int [nNodes];
359    int k = 0;
360    int kDelete = nNodes;
361    bestPossibleObjective = 1.0e100 ;
362    /*
363        Destructively scan the heap. Nodes to be retained go into the front of
364        nodeArray, nodes to be deleted into the back. Store the depth in a
365        correlated array for nodes to be deleted.
366    */
367    for (j = 0; j < nNodes; j++) {
368        CbcNode * node = top();
369        pop();
370        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
371        if (node && value >= cutoff) {
372            // double check in case node can change its mind!
373            value = node->checkIsCutoff(cutoff);
374        }
375        if (value >= cutoff || !node->active()) {
376            if (node) {
377                nodeArray[--kDelete] = node;
378                depth[kDelete] = node->depth();
379            }
380        } else {
381            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
382            nodeArray[k++] = node;
383        }
384    }
385    /*
386      Rebuild the heap using the retained nodes.
387    */
388    for (j = 0; j < k; j++) {
389        push(nodeArray[j]);
390    }
391    /*
392      Sort the list of nodes to be deleted, nondecreasing.
393    */
394    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
395    /*
396      Work back from deepest to shallowest. In spite of the name, addCuts1 is
397      just a preparatory step. When it returns, the following will be true:
398        * all cuts are removed from the solver's copy of the constraint system;
399        * lastws will be a basis appropriate for the specified node;
400        * variable bounds will be adjusted to be appropriate for the specified
401          node;
402        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
403          should be added to the constraint system at this node (but they have
404          not actually been added).
405      Then we scan the cut list for the node. Decrement the reference count
406      for the cut, and if it's gone to 0, really delete it.
407
408      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
409      are necessary. When reconstructing a node, these checks are used to skip
410      over loose cuts, excluding them from the reconstituted basis. But here
411      we're just interested in correcting the reference count. Tight/loose should
412      make no difference.
413
414      Arguably a separate routine should be used in place of addCuts1. It's doing
415      more work than needed, modifying the model to match a subproblem at a node
416      that will be discarded.  Then again, we seem to need the basis.
417    */
418    for (j = nNodes - 1; j >= kDelete; j--) {
419        CbcNode * node = nodeArray[j];
420        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
421
422        model->addCuts1(node, lastws);
423        // Decrement cut counts
424        assert (node);
425        //assert (node->nodeInfo());
426        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
427        int i;
428        for (i = 0; i < model->currentNumberCuts(); i++) {
429            // take off node
430            CoinWarmStartBasis::Status status =
431                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
432            if (status != CoinWarmStartBasis::basic &&
433                    model->addedCuts()[i]) {
434                if (!model->addedCuts()[i]->decrement(numberLeft))
435                    delete model->addedCuts()[i];
436            }
437        }
438        // node should not have anything pointing to it
439        if (node->nodeInfo())
440            node->nodeInfo()->throwAway();
441        delete node ;
442        delete lastws ;
443    }
444    delete [] nodeArray;
445    delete [] depth;
446}
447
448// Return the best node of the heap using alternate criterion
449CbcNode *
450CbcTree::bestAlternate()
451{
452    int n = nodes_.size();
453    CbcNode * best = NULL;
454    if (n) {
455        best = nodes_[0];
456        for (int i = 1; i < n; i++) {
457            if (comparison_.alternateTest(best, nodes_[i])) {
458                best = nodes_[i];
459            }
460        }
461    }
462    return best;
463}
464
465#if 0 // not used, referenced removed in CbcModel.cpp
466CbcTreeArray::CbcTreeArray()
467        : CbcTree(),
468        lastNode_(NULL),
469        lastNodePopped_(NULL),
470        switches_(0)
471{
472}
473CbcTreeArray::~CbcTreeArray()
474{
475}
476// Copy constructor
477CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
478        : CbcTree(rhs),
479        lastNode_(rhs.lastNode_),
480        lastNodePopped_(rhs.lastNodePopped_),
481        switches_(rhs.switches_)
482{
483}
484// Assignment operator
485CbcTreeArray &
486CbcTreeArray::operator=(const CbcTreeArray & rhs)
487{
488    if (this != &rhs) {
489        CbcTree::operator=(rhs);
490        lastNode_ = rhs.lastNode_;
491        lastNodePopped_ = rhs.lastNodePopped_;
492        switches_ = rhs.switches_;
493    }
494    return *this;
495}
496// Clone
497CbcTree *
498CbcTreeArray::clone() const
499{
500    return new CbcTreeArray(*this);
501}
502// Set comparison function and resort heap
503void
504CbcTreeArray::setComparison(CbcCompareBase  &compare)
505{
506    comparison_.test_ = &compare;
507    std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
508}
509
510// Add a node to the heap
511void
512CbcTreeArray::push(CbcNode * x)
513{
514    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
515       x->objectiveValue(),x->nodeInfo()->decrement(0),
516       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
517    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
518    x->setOnTree(true);
519    if (lastNode_) {
520        if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
521            // x is parent of lastNode_ so put x on heap
522            //#define CBCTREE_PRINT
523#ifdef CBCTREE_PRINT
524            printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
525                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
526                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
527#endif
528            nodes_.push_back(x);
529        } else {
530            x->setNodeNumber(maximumNodeNumber_);
531            maximumNodeNumber_++;
532#ifdef CBCTREE_PRINT
533            printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
534                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
535                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
536#endif
537            nodes_.push_back(lastNode_);
538            lastNode_ = x;
539        }
540        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
541    } else {
542        x->setNodeNumber(maximumNodeNumber_);
543        maximumNodeNumber_++;
544        if (x != lastNodePopped_) {
545            lastNode_ = x;
546#ifdef CBCTREE_PRINT
547            printf("pushNULL x %x (%x at depth %d n %d)\n",
548                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
549#endif
550        } else {
551            // means other way was infeasible
552#ifdef CBCTREE_PRINT
553            printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
554                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
555#endif
556            nodes_.push_back(x);
557            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
558        }
559    }
560}
561
562// Test if empty *** note may be overridden
563bool
564CbcTreeArray::empty()
565{
566    return nodes_.empty() && (lastNode_ == NULL);
567}
568// Gets best node and takes off heap
569CbcNode *
570CbcTreeArray::bestNode(double cutoff)
571{
572    CbcNode * best = NULL;
573    // See if we want last node or best on heap
574    if (lastNode_) {
575#ifdef CBCTREE_PRINT
576        printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
577               lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
578               lastNode_->nodeNumber(), lastNode_->objectiveValue());
579#endif
580        assert (lastNode_->onTree());
581        int nodeNumber = lastNode_->nodeNumber();
582        bool useLastNode = false;
583        if (nodeNumber + 1 == maximumNodeNumber_) {
584            // diving - look further
585            CbcCompareDefault * compareDefault
586            = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
587            assert (compareDefault);
588            double bestPossible = compareDefault->getBestPossible();
589            double cutoff = compareDefault->getCutoff();
590            double objValue = lastNode_->objectiveValue();
591            if (cutoff < 1.0e20) {
592                if (objValue - bestPossible < 0.999*(cutoff - bestPossible))
593                    useLastNode = true;
594            } else {
595                useLastNode = true;
596            }
597        }
598        if (useLastNode) {
599            lastNode_->setOnTree(false);
600            best = lastNode_;
601            lastNode_ = NULL;
602            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
603            if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
604                assert (best->nodeInfo()->numberBranchesLeft());
605            if (best->objectiveValue() >= cutoff) {
606                // double check in case node can change its mind!
607                best->checkIsCutoff(cutoff);
608            }
609            lastNodePopped_ = best;
610            return best;
611        } else {
612            // put on tree
613            nodes_.push_back(lastNode_);
614            lastNode_->setNodeNumber(maximumNodeNumber_);
615            maximumNodeNumber_++;
616            lastNode_ = NULL;
617            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
618        }
619    }
620    while (!best && nodes_.size()) {
621        best = nodes_.front();
622        if (best)
623            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
624        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
625            assert (best->nodeInfo()->numberBranchesLeft());
626        if (best && best->objectiveValue() >= cutoff) {
627            // double check in case node can change its mind!
628            best->checkIsCutoff(cutoff);
629        }
630        if (!best || best->objectiveValue() >= cutoff) {
631            // let code get rid of it
632            assert (best);
633        }
634    }
635    lastNodePopped_ = best;
636#ifdef CBCTREE_PRINT
637    if (best)
638        printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
639               best, best->nodeInfo(), best->depth(),
640               best->nodeNumber(), best->objectiveValue());
641    else
642        printf("Heap returning Null\n");
643#endif
644    if (best) {
645        // take off
646        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
647        nodes_.pop_back();
648    }
649#ifdef DEBUG_CBC_HEAP
650    if (best) {
651        int n = nodes_.size();
652        bool good = true;
653        for (int i = 0; i < n; i++) {
654            // temp
655            assert (nodes_[i]);
656            if (!comparison_.compareNodes(nodes_[i], best)) {
657                good = false;
658                CbcNode * x = nodes_[i];
659                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
660                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
661                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
662            }
663        }
664        if (!good) {
665            // compare best to all
666            int i;
667            for (i = 0; i < n; i++) {
668                CbcNode * x = nodes_[i];
669                printf("i=%d x is nun %d depth %d obj %g", i,
670                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
671                if (!comparison_.compareNodes(x, best)) {
672                    printf(" - best is worse!\n");
673                } else {
674                    printf("\n");
675                }
676            }
677            // Now compare amongst rest
678            for (i = 0; i < n; i++) {
679                CbcNode * x = nodes_[i];
680                printf("For i=%d ", i);
681                for (int j = i + 1; j < n; j++) {
682                    CbcNode * y = nodes_[j];
683                    if (!comparison_.compareNodes(x, y)) {
684                        printf(" b %d", j);
685                    } else {
686                        printf(" w %d", j);
687                    }
688                }
689                printf("\n");
690            }
691            assert(good);
692        }
693    }
694#endif
695    if (best)
696        best->setOnTree(false);
697    return best;
698}
699
700double
701CbcTreeArray::getBestPossibleObjective()
702{
703    double bestPossibleObjective = 1e100;
704    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
705        if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
706            bestPossibleObjective = nodes_[i]->objectiveValue();
707        }
708    }
709    if (lastNode_) {
710        bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
711    }
712    CbcCompareDefault * compareDefault
713    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
714    assert (compareDefault);
715    compareDefault->setBestPossible(bestPossibleObjective);
716    return bestPossibleObjective;
717}
718/*! \brief Prune the tree using an objective function cutoff
719
720  This routine removes all nodes with objective worst than the
721  specified cutoff value.
722*/
723
724void
725CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
726{
727    int j;
728    int nNodes = size();
729    int lastNode = nNodes + 1;
730    CbcNode ** nodeArray = new CbcNode * [lastNode];
731    int * depth = new int [lastNode];
732    int k = 0;
733    int kDelete = lastNode;
734    bestPossibleObjective = 1.0e100 ;
735    /*
736        Destructively scan the heap. Nodes to be retained go into the front of
737        nodeArray, nodes to be deleted into the back. Store the depth in a
738        correlated array for nodes to be deleted.
739    */
740    for (j = 0; j < nNodes; j++) {
741        CbcNode * node = nodes_.front();
742        nodes_.front()->setOnTree(false);
743        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
744        nodes_.pop_back();
745        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
746        if (node && value >= cutoff) {
747            // double check in case node can change its mind!
748            value = node->checkIsCutoff(cutoff);
749        }
750        if (value >= cutoff || !node->active()) {
751            if (node) {
752                nodeArray[--kDelete] = node;
753                depth[kDelete] = node->depth();
754            }
755        } else {
756            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
757            nodeArray[k++] = node;
758        }
759    }
760    if (lastNode_) {
761        double value = lastNode_->objectiveValue();
762        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
763        if (value >= cutoff || !lastNode_->active()) {
764            nodeArray[--kDelete] = lastNode_;
765            depth[kDelete] = lastNode_->depth();
766            lastNode_ = NULL;
767        }
768    }
769    CbcCompareDefault * compareDefault
770    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
771    assert (compareDefault);
772    compareDefault->setBestPossible(bestPossibleObjective);
773    compareDefault->setCutoff(cutoff);
774    /*
775      Rebuild the heap using the retained nodes.
776    */
777    for (j = 0; j < k; j++) {
778        CbcNode * node = nodeArray[j];
779        node->setOnTree(true);
780        nodes_.push_back(node);
781        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
782    }
783    /*
784      Sort the list of nodes to be deleted, nondecreasing.
785    */
786    CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
787    /*
788      Work back from deepest to shallowest. In spite of the name, addCuts1 is
789      just a preparatory step. When it returns, the following will be true:
790        * all cuts are removed from the solver's copy of the constraint system;
791        * lastws will be a basis appropriate for the specified node;
792        * variable bounds will be adjusted to be appropriate for the specified
793          node;
794        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
795          should be added to the constraint system at this node (but they have
796          not actually been added).
797      Then we scan the cut list for the node. Decrement the reference count
798      for the cut, and if it's gone to 0, really delete it.
799
800      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
801      are necessary. When reconstructing a node, these checks are used to skip
802      over loose cuts, excluding them from the reconstituted basis. But here
803      we're just interested in correcting the reference count. Tight/loose should
804      make no difference.
805
806      Arguably a separate routine should be used in place of addCuts1. It's doing
807      more work than needed, modifying the model to match a subproblem at a node
808      that will be discarded.  Then again, we seem to need the basis.
809    */
810    for (j = lastNode - 1; j >= kDelete; j--) {
811        CbcNode * node = nodeArray[j];
812        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
813
814        model->addCuts1(node, lastws);
815        // Decrement cut counts
816        assert (node);
817        //assert (node->nodeInfo());
818        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
819        int i;
820        for (i = 0; i < model->currentNumberCuts(); i++) {
821            // take off node
822            CoinWarmStartBasis::Status status =
823                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
824            if (status != CoinWarmStartBasis::basic &&
825                    model->addedCuts()[i]) {
826                if (!model->addedCuts()[i]->decrement(numberLeft))
827                    delete model->addedCuts()[i];
828            }
829        }
830        // node should not have anything pointing to it
831        if (node->nodeInfo())
832            node->nodeInfo()->throwAway();
833        delete node ;
834        delete lastws ;
835    }
836    delete [] nodeArray;
837    delete [] depth;
838}
839#endif
840#else
841// Set comparison function and resort heap
842void
843CbcTree::setComparison(CbcCompareBase  &compare)
844{
845    comparison_.test_ = &compare;
846    std::vector <CbcNode *> newNodes = nodes_;
847    nodes_.resize(0);
848    while (newNodes.size() > 0) {
849        push( newNodes.back());
850        newNodes.pop_back();
851    }
852}
853
854// Return the top node of the heap
855CbcNode *
856CbcTree::top() const
857{
858    return nodes_.front();
859}
860
861// Add a node to the heap
862void
863CbcTree::push(CbcNode * x)
864{
865    x->setNodeNumber(maximumNodeNumber_);
866    maximumNodeNumber_++;
867    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
868       x->objectiveValue(),x->nodeInfo()->decrement(0),
869       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
870    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
871#if 0
872    nodes_.push_back(x);
873    push_heap(nodes_.begin(), nodes_.end(), comparison_);
874#else
875realpush(x);
876#endif
877}
878
879// Remove the top node from the heap
880void
881CbcTree::pop()
882{
883#if 0
884    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
885    nodes_.pop_back();
886#else
887if (nodes_.size()) {
888    //CbcNode* s = nodes_.front();
889    realpop();
890    //delete s;
891}
892assert (nodes_.size() >= 0);
893#endif
894}
895
896// Test if empty *** note may be overridden
897bool
898CbcTree::empty()
899{
900    return nodes_.empty();
901}
902// Gets best node and takes off heap
903CbcNode *
904CbcTree::bestNode(double cutoff)
905{
906    CbcNode * best = NULL;
907    while (!best && nodes_.size()) {
908        best = nodes_.front();
909        if (best)
910            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
911        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
912            assert (best->nodeInfo()->numberBranchesLeft());
913        if (best && best->objectiveValue() >= cutoff) {
914            // double check in case node can change its mind!
915            best->checkIsCutoff(cutoff);
916        }
917        if (!best || best->objectiveValue() >= cutoff) {
918#if 0
919            // take off
920            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
921            nodes_.pop_back();
922            delete best;
923            best = NULL;
924#else
925// let code get rid of it
926assert (best);
927#endif
928        }
929    }
930    // switched off for now
931    if (best && comparison_.test_->fullScan() && false) {
932        CbcNode * saveBest = best;
933        int n = nodes_.size();
934        int iBest = -1;
935        for (int i = 0; i < n; i++) {
936            // temp
937            assert (nodes_[i]);
938            assert (nodes_[i]->nodeInfo());
939            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
940                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
941            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
942                    && comparison_.alternateTest(best, nodes_[i])) {
943                best = nodes_[i];
944                iBest = i;
945            }
946        }
947        if (best == saveBest) {
948            // can pop
949            // take off
950            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
951            nodes_.pop_back();
952        } else {
953            // make impossible
954            nodes_[iBest] = NULL;
955        }
956    } else if (best) {
957        // take off
958#if 0
959        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
960        nodes_.pop_back();
961#else
962realpop();
963#endif
964    }
965#ifdef DEBUG_CBC_HEAP
966    if (best) {
967        int n = nodes_.size();
968        bool good = true;
969        for (int i = 0; i < n; i++) {
970            // temp
971            assert (nodes_[i]);
972            if (!comparison_.compareNodes(nodes_[i], best)) {
973                good = false;
974                CbcNode * x = nodes_[i];
975                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
976                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
977                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
978            }
979        }
980        if (!good) {
981            // compare best to all
982            int i;
983            for (i = 0; i < n; i++) {
984                CbcNode * x = nodes_[i];
985                printf("i=%d x is nun %d depth %d obj %g", i,
986                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
987                if (!comparison_.compareNodes(x, best)) {
988                    printf(" - best is worse!\n");
989                } else {
990                    printf("\n");
991                }
992            }
993            // Now compare amongst rest
994            for (i = 0; i < n; i++) {
995                CbcNode * x = nodes_[i];
996                printf("For i=%d ", i);
997                for (int j = i + 1; j < n; j++) {
998                    CbcNode * y = nodes_[j];
999                    if (!comparison_.compareNodes(x, y)) {
1000                        printf(" b %d", j);
1001                    } else {
1002                        printf(" w %d", j);
1003                    }
1004                }
1005                printf("\n");
1006            }
1007            assert(good);
1008        }
1009    }
1010#endif
1011    if (best)
1012        best->setOnTree(false);
1013    return best;
1014}
1015
1016/*! \brief Prune the tree using an objective function cutoff
1017
1018  This routine removes all nodes with objective worst than the
1019  specified cutoff value.
1020*/
1021
1022void
1023CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1024{
1025    int j;
1026    int nNodes = nodes_.size();
1027    CbcNode ** nodeArray = new CbcNode * [nNodes];
1028    int * depth = new int [nNodes];
1029    int k = 0;
1030    int kDelete = nNodes;
1031    bestPossibleObjective = 1.0e100 ;
1032    /*
1033        Destructively scan the heap. Nodes to be retained go into the front of
1034        nodeArray, nodes to be deleted into the back. Store the depth in a
1035        correlated array for nodes to be deleted.
1036    */
1037    for (j = 0; j < nNodes; j++) {
1038        CbcNode * node = top();
1039        pop();
1040        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1041        if (node && value >= cutoff) {
1042            // double check in case node can change its mind!
1043            value = node->checkIsCutoff(cutoff);
1044        }
1045        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1046        if (value >= cutoff) {
1047            if (node) {
1048                nodeArray[--kDelete] = node;
1049                depth[kDelete] = node->depth();
1050            }
1051        } else {
1052            nodeArray[k++] = node;
1053        }
1054    }
1055    /*
1056      Rebuild the heap using the retained nodes.
1057    */
1058    for (j = 0; j < k; j++) {
1059        push(nodeArray[j]);
1060    }
1061    /*
1062      Sort the list of nodes to be deleted, nondecreasing.
1063    */
1064    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1065    /*
1066      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1067      just a preparatory step. When it returns, the following will be true:
1068        * all cuts are removed from the solver's copy of the constraint system;
1069        * lastws will be a basis appropriate for the specified node;
1070        * variable bounds will be adjusted to be appropriate for the specified
1071          node;
1072        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1073          should be added to the constraint system at this node (but they have
1074          not actually been added).
1075      Then we scan the cut list for the node. Decrement the reference count
1076      for the cut, and if it's gone to 0, really delete it.
1077
1078      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1079      are necessary. When reconstructing a node, these checks are used to skip
1080      over loose cuts, excluding them from the reconstituted basis. But here
1081      we're just interested in correcting the reference count. Tight/loose should
1082      make no difference.
1083
1084      Arguably a separate routine should be used in place of addCuts1. It's doing
1085      more work than needed, modifying the model to match a subproblem at a node
1086      that will be discarded.  Then again, we seem to need the basis.
1087    */
1088    for (j = nNodes - 1; j >= kDelete; j--) {
1089        CbcNode * node = nodeArray[j];
1090        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1091
1092        model->addCuts1(node, lastws);
1093        // Decrement cut counts
1094        assert (node);
1095        //assert (node->nodeInfo());
1096        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1097        int i;
1098        for (i = 0; i < model->currentNumberCuts(); i++) {
1099            // take off node
1100            CoinWarmStartBasis::Status status =
1101                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1102            if (status != CoinWarmStartBasis::basic &&
1103                    model->addedCuts()[i]) {
1104                if (!model->addedCuts()[i]->decrement(numberLeft))
1105                    delete model->addedCuts()[i];
1106            }
1107        }
1108        // node should not have anything pointing to it
1109        if (node->nodeInfo())
1110            node->nodeInfo()->throwAway();
1111        delete node ;
1112        delete lastws ;
1113    }
1114    delete [] nodeArray;
1115    delete [] depth;
1116}
1117
1118// Return the best node of the heap using alternate criterion
1119CbcNode *
1120CbcTree::bestAlternate()
1121{
1122    int n = nodes_.size();
1123    CbcNode * best = NULL;
1124    if (n) {
1125        best = nodes_[0];
1126        for (int i = 1; i < n; i++) {
1127            if (comparison_.alternateTest(best, nodes_[i])) {
1128                best = nodes_[i];
1129            }
1130        }
1131    }
1132    return best;
1133}
1134void
1135CbcTree::realpop()
1136{
1137    if (nodes_.size() > 0) {
1138        nodes_[0] = nodes_.back();
1139        nodes_.pop_back();
1140        fixTop();
1141    }
1142    assert (nodes_.size() >= 0);
1143}
1144/* After changing data in the top node, fix the heap */
1145void
1146CbcTree::fixTop()
1147{
1148    const int size = nodes_.size();
1149    if (size > 1) {
1150        CbcNode** candidates = &nodes_[0];
1151        CbcNode* s = candidates[0];
1152        --candidates;
1153        int pos = 1;
1154        int ch;
1155        for (ch = 2; ch < size; pos = ch, ch *= 2) {
1156            if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1157                ++ch;
1158            if (!comparison_.compareNodes(s, candidates[ch]))
1159                break;
1160            candidates[pos] = candidates[ch];
1161        }
1162        if (ch == size) {
1163            if (!comparison_.compareNodes(candidates[ch], s)) {
1164                candidates[pos] = candidates[ch];
1165                pos = ch;
1166            }
1167        }
1168        candidates[pos] = s;
1169    }
1170}
1171void
1172CbcTree::realpush(CbcNode * node)
1173{
1174    node->setOnTree(true);
1175    nodes_.push_back(node);
1176    CbcNode** candidates = &nodes_[0];
1177    --candidates;
1178    int pos = nodes_.size();
1179    int ch;
1180    for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1181        if (!comparison_.compareNodes(candidates[ch], node))
1182            break;
1183        candidates[pos] = candidates[ch];
1184    }
1185    candidates[pos] = node;
1186}
1187#endif
Note: See TracBrowser for help on using the repository browser.