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

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

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

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