Ignore:
Timestamp:
Jan 4, 2011 8:12:36 PM (8 years ago)
Author:
lou
Message:

Change to EPL license notice.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcTree.cpp

    r1506 r1573  
    22// Copyright (C) 2004, International Business Machines
    33// Corporation and others.  All Rights Reserved.
    4 
     4// This code is licensed under the terms of the Eclipse Public License (EPL).
    55
    66#include "CbcModel.hpp"
     
    1818
    1919/*
    20   The next few methods test that the heap property (parent equal or better than either
    21   child) is maintained in the heap. Originally created to sort out why `cbc -unitTest'
    22   triggered an `Invalid heap' error in a MSVS debug build.
     20  The next few methods test that the heap property (parent equal or better
     21  than either child) is maintained in the heap. Originally created to sort out
     22  why `cbc -unitTest' triggered an `Invalid heap' error in a MSVS debug build.
    2323*/
    2424/*
    25   Predicate test. The parent should be better or equal to the child. Since the predicate
    26   comparison_(x,y) returns true if y (child) is strictly better, we want failure on the
    27   initial test. Clearly, success for comparison(x,y) and comparison(y,x) is also a failure.
     25  Predicate test. The parent should be better or equal to the child. Since the
     26  predicate comparison_(x,y) returns true if y (child) is strictly better,
     27  we want failure on the initial test. Clearly, success for comparison(x,y)
     28  and comparison(y,x) is also a failure.
    2829
    2930  Returns true if the predicate passes, false if it fails.
     
    4344
    4445/*
    45   Check for the heap property: the parent is better than or equal to either child.
    46  
    47   The heap is a binary tree, stored in the vector layer by layer. By advancing parent
    48   at half the rate of child (aka curNode), we check both children of a given parent.
    49   (Draw yourself a picture; it'll help.) An empty heap is trivially valid. A heap with
    50   no predicate is trivially invalid.
    51 
    52   TODO: The heap -> vector mapping assumed here is valid for the MSVS heap implementation.
    53         No guarantee it's valid elsewhere.
     46  Check for the heap property: the parent is better than or equal to
     47  either child.
     48
     49  The heap is a binary tree, stored in the vector layer by layer. By advancing
     50  parent at half the rate of child (aka curNode), we check both children
     51  of a given parent.  (Draw yourself a picture; it'll help.) An empty heap
     52  is trivially valid. A heap with no predicate is trivially invalid.
     53
     54  TODO: The heap -> vector mapping assumed here is valid for the MSVS heap
     55        implementation.  No guarantee it's valid elsewhere.
    5456*/
    5557
     
    8486    if (*curNode == 0) {
    8587      std::cout
    86         << " Invalid heap[" << curNdx << "] (left child null entry)!" << std::endl ;
     88        << " Invalid heap[" << curNdx << "] (left child null entry)!"
     89        << std::endl ;
    8790    } else {
    8891      if (!check_pred(*comparison_.test_,*parent,*child)) {
     
    9295        std::cout
    9396          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
    94           << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
    95           << ", obj " << node->objectiveValue() << "." << std::endl ;
     97          << ") unsat " << node->numberUnsatisfied() << ", depth "
     98          << node->depth() << ", obj " << node->objectiveValue() << "."
     99          << std::endl ;
    96100        node = *child ;
    97101        std::cout
    98102          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
    99           << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
    100           << ", obj " << node->objectiveValue() << "." << std::endl ;
     103          << ") unsat " << node->numberUnsatisfied() << ", depth "
     104          << node->depth() << ", obj " << node->objectiveValue() << "."
     105          << std::endl ;
    101106      }
    102107    }
     
    106111    if (*curNode == 0) {
    107112      std::cout
    108         << " Invalid heap[" << curNdx << "] (right child null entry)!" << std::endl ;
     113        << " Invalid heap[" << curNdx << "] (right child null entry)!"
     114        << std::endl ;
    109115    } else {
    110116      if (!check_pred(*comparison_.test_,*parent,*child)) {
     
    114120        std::cout
    115121          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
    116           << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
    117           << ", obj " << node->objectiveValue() << "." << std::endl ;
     122          << ") unsat " << node->numberUnsatisfied() << ", depth "
     123          << node->depth() << ", obj " << node->objectiveValue() << "."
     124          << std::endl ;
    118125        node = *child ;
    119126        std::cout
    120127          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
    121           << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
    122           << ", obj " << node->objectiveValue() << "." << std::endl ;
     128          << ") unsat " << node->numberUnsatisfied() << ", depth "
     129          << node->depth() << ", obj " << node->objectiveValue() << "."
     130          << std::endl ;
    123131      }
    124132    }
    125133  }
    126 return ;
     134  return ;
    127135}
    128136   
     
    612620      are necessary. When reconstructing a node, these checks are used to skip
    613621      over loose cuts, excluding them from the reconstituted basis. But here
    614       we're just interested in correcting the reference count. Tight/loose should
    615       make no difference.
    616 
    617       Arguably a separate routine should be used in place of addCuts1. It's doing
    618       more work than needed, modifying the model to match a subproblem at a node
    619       that will be discarded.  Then again, we seem to need the basis.
     622      we're just interested in correcting the reference count. Tight/loose
     623      should make no difference.
     624
     625      Arguably a separate routine should be used in place of addCuts1. It's
     626      doing more work than needed, modifying the model to match a subproblem
     627      at a node that will be discarded.  Then again, we seem to need the basis.
    620628    */
    621629    for (j = nNodes - 1; j >= kDelete; j--) {
     
    10041012      are necessary. When reconstructing a node, these checks are used to skip
    10051013      over loose cuts, excluding them from the reconstituted basis. But here
    1006       we're just interested in correcting the reference count. Tight/loose should
    1007       make no difference.
    1008 
    1009       Arguably a separate routine should be used in place of addCuts1. It's doing
    1010       more work than needed, modifying the model to match a subproblem at a node
    1011       that will be discarded.  Then again, we seem to need the basis.
     1014      we're just interested in correcting the reference count. Tight/loose
     1015      should make no difference.
     1016
     1017      Arguably a separate routine should be used in place of addCuts1. It's
     1018      doing more work than needed, modifying the model to match a subproblem
     1019      at a node that will be discarded.  Then again, we seem to need the basis.
    10121020    */
    10131021    for (j = lastNode - 1; j >= kDelete; j--) {
     
    12901298      are necessary. When reconstructing a node, these checks are used to skip
    12911299      over loose cuts, excluding them from the reconstituted basis. But here
    1292       we're just interested in correcting the reference count. Tight/loose should
    1293       make no difference.
    1294 
    1295       Arguably a separate routine should be used in place of addCuts1. It's doing
    1296       more work than needed, modifying the model to match a subproblem at a node
    1297       that will be discarded.  Then again, we seem to need the basis.
     1300      we're just interested in correcting the reference count. Tight/loose
     1301      should make no difference.
     1302
     1303      Arguably a separate routine should be used in place of addCuts1. It's
     1304      doing more work than needed, modifying the model to match a subproblem
     1305      at a node that will be discarded.  Then again, we seem to need the basis.
    12981306    */
    12991307    for (j = nNodes - 1; j >= kDelete; j--) {
Note: See TracChangeset for help on using the changeset viewer.