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

Last change on this file since 1315 was 1315, checked in by forrest, 10 years ago

final changes before cleaning

  • 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 1315 2009-11-28 11:09:56Z forrest $ */
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}
464CbcTreeArray::CbcTreeArray()
465        : CbcTree(),
466        lastNode_(NULL),
467        lastNodePopped_(NULL),
468        switches_(0)
469{
470}
471CbcTreeArray::~CbcTreeArray()
472{
473}
474// Copy constructor
475CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
476        : CbcTree(rhs),
477        lastNode_(rhs.lastNode_),
478        lastNodePopped_(rhs.lastNodePopped_),
479        switches_(rhs.switches_)
480{
481}
482// Assignment operator
483CbcTreeArray &
484CbcTreeArray::operator=(const CbcTreeArray & rhs)
485{
486    if (this != &rhs) {
487        CbcTree::operator=(rhs);
488        lastNode_ = rhs.lastNode_;
489        lastNodePopped_ = rhs.lastNodePopped_;
490        switches_ = rhs.switches_;
491    }
492    return *this;
493}
494// Clone
495CbcTree *
496CbcTreeArray::clone() const
497{
498    return new CbcTreeArray(*this);
499}
500// Set comparison function and resort heap
501void
502CbcTreeArray::setComparison(CbcCompareBase  &compare)
503{
504    comparison_.test_ = &compare;
505    std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
506}
507
508// Add a node to the heap
509void
510CbcTreeArray::push(CbcNode * x)
511{
512    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
513       x->objectiveValue(),x->nodeInfo()->decrement(0),
514       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
515    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
516    x->setOnTree(true);
517    if (lastNode_) {
518        if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
519            // x is parent of lastNode_ so put x on heap
520            //#define CBCTREE_PRINT
521#ifdef CBCTREE_PRINT
522            printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
523                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
524                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
525#endif
526            nodes_.push_back(x);
527        } else {
528            x->setNodeNumber(maximumNodeNumber_);
529            maximumNodeNumber_++;
530#ifdef CBCTREE_PRINT
531            printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
532                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
533                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
534#endif
535            nodes_.push_back(lastNode_);
536            lastNode_ = x;
537        }
538        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
539    } else {
540        x->setNodeNumber(maximumNodeNumber_);
541        maximumNodeNumber_++;
542        if (x != lastNodePopped_) {
543            lastNode_ = x;
544#ifdef CBCTREE_PRINT
545            printf("pushNULL x %x (%x at depth %d n %d)\n",
546                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
547#endif
548        } else {
549            // means other way was infeasible
550#ifdef CBCTREE_PRINT
551            printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
552                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
553#endif
554            nodes_.push_back(x);
555            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
556        }
557    }
558}
559
560// Test if empty *** note may be overridden
561bool
562CbcTreeArray::empty()
563{
564    return nodes_.empty() && (lastNode_ == NULL);
565}
566// Gets best node and takes off heap
567CbcNode *
568CbcTreeArray::bestNode(double cutoff)
569{
570    CbcNode * best = NULL;
571    // See if we want last node or best on heap
572    if (lastNode_) {
573#ifdef CBCTREE_PRINT
574        printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
575               lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
576               lastNode_->nodeNumber(), lastNode_->objectiveValue());
577#endif
578        assert (lastNode_->onTree());
579        int nodeNumber = lastNode_->nodeNumber();
580        bool useLastNode = false;
581        if (nodeNumber + 1 == maximumNodeNumber_) {
582            // diving - look further
583            CbcCompareDefault * compareDefault
584            = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
585            assert (compareDefault);
586            double bestPossible = compareDefault->getBestPossible();
587            double cutoff = compareDefault->getCutoff();
588            double objValue = lastNode_->objectiveValue();
589            if (cutoff < 1.0e20) {
590                if (objValue - bestPossible < 0.999*(cutoff - bestPossible))
591                    useLastNode = true;
592            } else {
593                useLastNode = true;
594            }
595        }
596        if (useLastNode) {
597            lastNode_->setOnTree(false);
598            best = lastNode_;
599            lastNode_ = NULL;
600            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
601            if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
602                assert (best->nodeInfo()->numberBranchesLeft());
603            if (best->objectiveValue() >= cutoff) {
604                // double check in case node can change its mind!
605                best->checkIsCutoff(cutoff);
606            }
607            lastNodePopped_ = best;
608            return best;
609        } else {
610            // put on tree
611            nodes_.push_back(lastNode_);
612            lastNode_->setNodeNumber(maximumNodeNumber_);
613            maximumNodeNumber_++;
614            lastNode_ = NULL;
615            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
616        }
617    }
618    while (!best && nodes_.size()) {
619        best = nodes_.front();
620        if (best)
621            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
622        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
623            assert (best->nodeInfo()->numberBranchesLeft());
624        if (best && best->objectiveValue() >= cutoff) {
625            // double check in case node can change its mind!
626            best->checkIsCutoff(cutoff);
627        }
628        if (!best || best->objectiveValue() >= cutoff) {
629            // let code get rid of it
630            assert (best);
631        }
632    }
633    lastNodePopped_ = best;
634#ifdef CBCTREE_PRINT
635    if (best)
636        printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
637               best, best->nodeInfo(), best->depth(),
638               best->nodeNumber(), best->objectiveValue());
639    else
640        printf("Heap returning Null\n");
641#endif
642    if (best) {
643        // take off
644        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
645        nodes_.pop_back();
646    }
647#ifdef DEBUG_CBC_HEAP
648    if (best) {
649        int n = nodes_.size();
650        bool good = true;
651        for (int i = 0; i < n; i++) {
652            // temp
653            assert (nodes_[i]);
654            if (!comparison_.compareNodes(nodes_[i], best)) {
655                good = false;
656                CbcNode * x = nodes_[i];
657                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
658                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
659                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
660            }
661        }
662        if (!good) {
663            // compare best to all
664            int i;
665            for (i = 0; i < n; i++) {
666                CbcNode * x = nodes_[i];
667                printf("i=%d x is nun %d depth %d obj %g", i,
668                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
669                if (!comparison_.compareNodes(x, best)) {
670                    printf(" - best is worse!\n");
671                } else {
672                    printf("\n");
673                }
674            }
675            // Now compare amongst rest
676            for (i = 0; i < n; i++) {
677                CbcNode * x = nodes_[i];
678                printf("For i=%d ", i);
679                for (int j = i + 1; j < n; j++) {
680                    CbcNode * y = nodes_[j];
681                    if (!comparison_.compareNodes(x, y)) {
682                        printf(" b %d", j);
683                    } else {
684                        printf(" w %d", j);
685                    }
686                }
687                printf("\n");
688            }
689            assert(good);
690        }
691    }
692#endif
693    if (best)
694        best->setOnTree(false);
695    return best;
696}
697
698double
699CbcTreeArray::getBestPossibleObjective()
700{
701    double bestPossibleObjective = 1e100;
702    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
703        if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
704            bestPossibleObjective = nodes_[i]->objectiveValue();
705        }
706    }
707    if (lastNode_) {
708        bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
709    }
710    CbcCompareDefault * compareDefault
711    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
712    assert (compareDefault);
713    compareDefault->setBestPossible(bestPossibleObjective);
714    return bestPossibleObjective;
715}
716/*! \brief Prune the tree using an objective function cutoff
717
718  This routine removes all nodes with objective worst than the
719  specified cutoff value.
720*/
721
722void
723CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
724{
725    int j;
726    int nNodes = size();
727    int lastNode = nNodes + 1;
728    CbcNode ** nodeArray = new CbcNode * [lastNode];
729    int * depth = new int [lastNode];
730    int k = 0;
731    int kDelete = lastNode;
732    bestPossibleObjective = 1.0e100 ;
733    /*
734        Destructively scan the heap. Nodes to be retained go into the front of
735        nodeArray, nodes to be deleted into the back. Store the depth in a
736        correlated array for nodes to be deleted.
737    */
738    for (j = 0; j < nNodes; j++) {
739        CbcNode * node = nodes_.front();
740        nodes_.front()->setOnTree(false);
741        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
742        nodes_.pop_back();
743        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
744        if (node && value >= cutoff) {
745            // double check in case node can change its mind!
746            value = node->checkIsCutoff(cutoff);
747        }
748        if (value >= cutoff || !node->active()) {
749            if (node) {
750                nodeArray[--kDelete] = node;
751                depth[kDelete] = node->depth();
752            }
753        } else {
754            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
755            nodeArray[k++] = node;
756        }
757    }
758    if (lastNode_) {
759        double value = lastNode_->objectiveValue();
760        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
761        if (value >= cutoff || !lastNode_->active()) {
762            nodeArray[--kDelete] = lastNode_;
763            depth[kDelete] = lastNode_->depth();
764            lastNode_ = NULL;
765        }
766    }
767    CbcCompareDefault * compareDefault
768    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
769    assert (compareDefault);
770    compareDefault->setBestPossible(bestPossibleObjective);
771    compareDefault->setCutoff(cutoff);
772    /*
773      Rebuild the heap using the retained nodes.
774    */
775    for (j = 0; j < k; j++) {
776        CbcNode * node = nodeArray[j];
777        node->setOnTree(true);
778        nodes_.push_back(node);
779        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
780    }
781    /*
782      Sort the list of nodes to be deleted, nondecreasing.
783    */
784    CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
785    /*
786      Work back from deepest to shallowest. In spite of the name, addCuts1 is
787      just a preparatory step. When it returns, the following will be true:
788        * all cuts are removed from the solver's copy of the constraint system;
789        * lastws will be a basis appropriate for the specified node;
790        * variable bounds will be adjusted to be appropriate for the specified
791          node;
792        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
793          should be added to the constraint system at this node (but they have
794          not actually been added).
795      Then we scan the cut list for the node. Decrement the reference count
796      for the cut, and if it's gone to 0, really delete it.
797
798      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
799      are necessary. When reconstructing a node, these checks are used to skip
800      over loose cuts, excluding them from the reconstituted basis. But here
801      we're just interested in correcting the reference count. Tight/loose should
802      make no difference.
803
804      Arguably a separate routine should be used in place of addCuts1. It's doing
805      more work than needed, modifying the model to match a subproblem at a node
806      that will be discarded.  Then again, we seem to need the basis.
807    */
808    for (j = lastNode - 1; j >= kDelete; j--) {
809        CbcNode * node = nodeArray[j];
810        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
811
812        model->addCuts1(node, lastws);
813        // Decrement cut counts
814        assert (node);
815        //assert (node->nodeInfo());
816        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
817        int i;
818        for (i = 0; i < model->currentNumberCuts(); i++) {
819            // take off node
820            CoinWarmStartBasis::Status status =
821                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
822            if (status != CoinWarmStartBasis::basic &&
823                    model->addedCuts()[i]) {
824                if (!model->addedCuts()[i]->decrement(numberLeft))
825                    delete model->addedCuts()[i];
826            }
827        }
828        // node should not have anything pointing to it
829        if (node->nodeInfo())
830            node->nodeInfo()->throwAway();
831        delete node ;
832        delete lastws ;
833    }
834    delete [] nodeArray;
835    delete [] depth;
836}
837#else
838// Set comparison function and resort heap
839void
840CbcTree::setComparison(CbcCompareBase  &compare)
841{
842    comparison_.test_ = &compare;
843    std::vector <CbcNode *> newNodes = nodes_;
844    nodes_.resize(0);
845    while (newNodes.size() > 0) {
846        push( newNodes.back());
847        newNodes.pop_back();
848    }
849}
850
851// Return the top node of the heap
852CbcNode *
853CbcTree::top() const
854{
855    return nodes_.front();
856}
857
858// Add a node to the heap
859void
860CbcTree::push(CbcNode * x)
861{
862    x->setNodeNumber(maximumNodeNumber_);
863    maximumNodeNumber_++;
864    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
865       x->objectiveValue(),x->nodeInfo()->decrement(0),
866       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
867    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
868#if 0
869    nodes_.push_back(x);
870    push_heap(nodes_.begin(), nodes_.end(), comparison_);
871#else
872realpush(x);
873#endif
874}
875
876// Remove the top node from the heap
877void
878CbcTree::pop()
879{
880#if 0
881    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
882    nodes_.pop_back();
883#else
884if (nodes_.size()) {
885    //CbcNode* s = nodes_.front();
886    realpop();
887    //delete s;
888}
889assert (nodes_.size() >= 0);
890#endif
891}
892
893// Test if empty *** note may be overridden
894bool
895CbcTree::empty()
896{
897    return nodes_.empty();
898}
899// Gets best node and takes off heap
900CbcNode *
901CbcTree::bestNode(double cutoff)
902{
903    CbcNode * best = NULL;
904    while (!best && nodes_.size()) {
905        best = nodes_.front();
906        if (best)
907            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
908        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
909            assert (best->nodeInfo()->numberBranchesLeft());
910        if (best && best->objectiveValue() >= cutoff) {
911            // double check in case node can change its mind!
912            best->checkIsCutoff(cutoff);
913        }
914        if (!best || best->objectiveValue() >= cutoff) {
915#if 0
916            // take off
917            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
918            nodes_.pop_back();
919            delete best;
920            best = NULL;
921#else
922// let code get rid of it
923assert (best);
924#endif
925        }
926    }
927    // switched off for now
928    if (best && comparison_.test_->fullScan() && false) {
929        CbcNode * saveBest = best;
930        int n = nodes_.size();
931        int iBest = -1;
932        for (int i = 0; i < n; i++) {
933            // temp
934            assert (nodes_[i]);
935            assert (nodes_[i]->nodeInfo());
936            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
937                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
938            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
939                    && comparison_.alternateTest(best, nodes_[i])) {
940                best = nodes_[i];
941                iBest = i;
942            }
943        }
944        if (best == saveBest) {
945            // can pop
946            // take off
947            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
948            nodes_.pop_back();
949        } else {
950            // make impossible
951            nodes_[iBest] = NULL;
952        }
953    } else if (best) {
954        // take off
955#if 0
956        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
957        nodes_.pop_back();
958#else
959realpop();
960#endif
961    }
962#ifdef DEBUG_CBC_HEAP
963    if (best) {
964        int n = nodes_.size();
965        bool good = true;
966        for (int i = 0; i < n; i++) {
967            // temp
968            assert (nodes_[i]);
969            if (!comparison_.compareNodes(nodes_[i], best)) {
970                good = false;
971                CbcNode * x = nodes_[i];
972                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
973                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
974                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
975            }
976        }
977        if (!good) {
978            // compare best to all
979            int i;
980            for (i = 0; i < n; i++) {
981                CbcNode * x = nodes_[i];
982                printf("i=%d x is nun %d depth %d obj %g", i,
983                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
984                if (!comparison_.compareNodes(x, best)) {
985                    printf(" - best is worse!\n");
986                } else {
987                    printf("\n");
988                }
989            }
990            // Now compare amongst rest
991            for (i = 0; i < n; i++) {
992                CbcNode * x = nodes_[i];
993                printf("For i=%d ", i);
994                for (int j = i + 1; j < n; j++) {
995                    CbcNode * y = nodes_[j];
996                    if (!comparison_.compareNodes(x, y)) {
997                        printf(" b %d", j);
998                    } else {
999                        printf(" w %d", j);
1000                    }
1001                }
1002                printf("\n");
1003            }
1004            assert(good);
1005        }
1006    }
1007#endif
1008    if (best)
1009        best->setOnTree(false);
1010    return best;
1011}
1012
1013/*! \brief Prune the tree using an objective function cutoff
1014
1015  This routine removes all nodes with objective worst than the
1016  specified cutoff value.
1017*/
1018
1019void
1020CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1021{
1022    int j;
1023    int nNodes = nodes_.size();
1024    CbcNode ** nodeArray = new CbcNode * [nNodes];
1025    int * depth = new int [nNodes];
1026    int k = 0;
1027    int kDelete = nNodes;
1028    bestPossibleObjective = 1.0e100 ;
1029    /*
1030        Destructively scan the heap. Nodes to be retained go into the front of
1031        nodeArray, nodes to be deleted into the back. Store the depth in a
1032        correlated array for nodes to be deleted.
1033    */
1034    for (j = 0; j < nNodes; j++) {
1035        CbcNode * node = top();
1036        pop();
1037        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1038        if (node && value >= cutoff) {
1039            // double check in case node can change its mind!
1040            value = node->checkIsCutoff(cutoff);
1041        }
1042        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1043        if (value >= cutoff) {
1044            if (node) {
1045                nodeArray[--kDelete] = node;
1046                depth[kDelete] = node->depth();
1047            }
1048        } else {
1049            nodeArray[k++] = node;
1050        }
1051    }
1052    /*
1053      Rebuild the heap using the retained nodes.
1054    */
1055    for (j = 0; j < k; j++) {
1056        push(nodeArray[j]);
1057    }
1058    /*
1059      Sort the list of nodes to be deleted, nondecreasing.
1060    */
1061    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1062    /*
1063      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1064      just a preparatory step. When it returns, the following will be true:
1065        * all cuts are removed from the solver's copy of the constraint system;
1066        * lastws will be a basis appropriate for the specified node;
1067        * variable bounds will be adjusted to be appropriate for the specified
1068          node;
1069        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1070          should be added to the constraint system at this node (but they have
1071          not actually been added).
1072      Then we scan the cut list for the node. Decrement the reference count
1073      for the cut, and if it's gone to 0, really delete it.
1074
1075      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1076      are necessary. When reconstructing a node, these checks are used to skip
1077      over loose cuts, excluding them from the reconstituted basis. But here
1078      we're just interested in correcting the reference count. Tight/loose should
1079      make no difference.
1080
1081      Arguably a separate routine should be used in place of addCuts1. It's doing
1082      more work than needed, modifying the model to match a subproblem at a node
1083      that will be discarded.  Then again, we seem to need the basis.
1084    */
1085    for (j = nNodes - 1; j >= kDelete; j--) {
1086        CbcNode * node = nodeArray[j];
1087        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1088
1089        model->addCuts1(node, lastws);
1090        // Decrement cut counts
1091        assert (node);
1092        //assert (node->nodeInfo());
1093        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1094        int i;
1095        for (i = 0; i < model->currentNumberCuts(); i++) {
1096            // take off node
1097            CoinWarmStartBasis::Status status =
1098                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1099            if (status != CoinWarmStartBasis::basic &&
1100                    model->addedCuts()[i]) {
1101                if (!model->addedCuts()[i]->decrement(numberLeft))
1102                    delete model->addedCuts()[i];
1103            }
1104        }
1105        // node should not have anything pointing to it
1106        if (node->nodeInfo())
1107            node->nodeInfo()->throwAway();
1108        delete node ;
1109        delete lastws ;
1110    }
1111    delete [] nodeArray;
1112    delete [] depth;
1113}
1114
1115// Return the best node of the heap using alternate criterion
1116CbcNode *
1117CbcTree::bestAlternate()
1118{
1119    int n = nodes_.size();
1120    CbcNode * best = NULL;
1121    if (n) {
1122        best = nodes_[0];
1123        for (int i = 1; i < n; i++) {
1124            if (comparison_.alternateTest(best, nodes_[i])) {
1125                best = nodes_[i];
1126            }
1127        }
1128    }
1129    return best;
1130}
1131void
1132CbcTree::realpop()
1133{
1134    if (nodes_.size() > 0) {
1135        nodes_[0] = nodes_.back();
1136        nodes_.pop_back();
1137        fixTop();
1138    }
1139    assert (nodes_.size() >= 0);
1140}
1141/* After changing data in the top node, fix the heap */
1142void
1143CbcTree::fixTop()
1144{
1145    const int size = nodes_.size();
1146    if (size > 1) {
1147        CbcNode** candidates = &nodes_[0];
1148        CbcNode* s = candidates[0];
1149        --candidates;
1150        int pos = 1;
1151        int ch;
1152        for (ch = 2; ch < size; pos = ch, ch *= 2) {
1153            if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1154                ++ch;
1155            if (!comparison_.compareNodes(s, candidates[ch]))
1156                break;
1157            candidates[pos] = candidates[ch];
1158        }
1159        if (ch == size) {
1160            if (!comparison_.compareNodes(candidates[ch], s)) {
1161                candidates[pos] = candidates[ch];
1162                pos = ch;
1163            }
1164        }
1165        candidates[pos] = s;
1166    }
1167}
1168void
1169CbcTree::realpush(CbcNode * node)
1170{
1171    node->setOnTree(true);
1172    nodes_.push_back(node);
1173    CbcNode** candidates = &nodes_[0];
1174    --candidates;
1175    int pos = nodes_.size();
1176    int ch;
1177    for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1178        if (!comparison_.compareNodes(candidates[ch], node))
1179            break;
1180        candidates[pos] = candidates[ch];
1181    }
1182    candidates[pos] = node;
1183}
1184#endif
Note: See TracBrowser for help on using the repository browser.