Changeset 980


Ignore:
Timestamp:
Jun 15, 2008 11:55:47 PM (11 years ago)
Author:
ladanyi
Message:

works properly on p0033.mps, though does not save any nodes...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r976 r980  
    5555public:
    5656  enum DBNodeWay {
    57     DOWN_UP__NOTHING_DONE=0x11,
    58     DOWN_UP__DOWN_DONE=0x12,
    59     DOWN_UP__BOTH_DONE=0x14,
    60     DOWN_UP__=0x10,
    61     UP_DOWN__NOTHING_DONE=0x21,
    62     UP_DOWN__UP_DONE=0x24,
    63     UP_DOWN__BOTH_DONE=0x22,
    64     UP_DOWN__=0x20,
    65     DOWN_CURRENT=0x02,
    66     UP_CURRENT=0x04,
     57    WAY_DOWN_UP__NOTHING_DONE=0x10,
     58    WAY_DOWN_UP__DOWN_DONE=0x11,
     59    WAY_DOWN_UP__BOTH_DONE=0x13,
     60    WAY_DOWN_UP__=0x10,
     61    WAY_UP_DOWN__NOTHING_DONE=0x20,
     62    WAY_UP_DOWN__UP_DONE=0x22,
     63    WAY_UP_DOWN__BOTH_DONE=0x23,
     64    WAY_UP_DOWN__=0x20,
     65    WAY_DOWN_CURRENT=0x01,
     66    WAY_UP_CURRENT=0x02,
     67    WAY_BOTH_DONE=0x03,
     68   
    6769    WAY_UNSET
    6870  };
     
    9597                 const double * originalLower,
    9698                 const double * originalUpper) const;
    97   inline void incrementDescendants()
    98   { descendants_++;}
    9999  // Tests if we can switch this node (this is the parent) with its parent
    100100  bool canSwitchParentWithGrandparent(const int* which,
     
    103103                                      const int * original_upper,
    104104                                      DBVectorNode & branchingTree);
     105  inline bool bothChildDone() const {
     106    return (way_ & WAY_BOTH_DONE) == WAY_BOTH_DONE;
     107  }
    105108
    106109  // Public data
     
    119122  // Current value
    120123  double value_;
    121   // Number of descendant nodes (so 2 is in interior)
    122   int descendants_;
    123124  // Parent
    124125  int parent_;
     
    150151  numberIntegers_(0),
    151152  value_(0.5),
    152   descendants_(-1),
    153153  parent_(-1),
    154154  child_down_(-1),
     
    174174  basis_ = basis;
    175175  variable_=-1;
    176   way_=WAY_UNSET;
     176  way_ = WAY_UNSET;
    177177  numberIntegers_=numberIntegers;
    178178  value_=0.0;
    179   descendants_ = 0;
    180179  parent_ = -1;
    181180  child_down_ = -1;
     
    281280    value_=value;
    282281    if (value<=nearest)
    283       way_=UP_DOWN__NOTHING_DONE; // up
     282      way_ = WAY_UP_DOWN__NOTHING_DONE; // up
    284283    else
    285       way_=DOWN_UP__NOTHING_DONE; // down
     284      way_ = WAY_DOWN_UP__NOTHING_DONE; // down
    286285  } else if (numberStrong) {
    287286    // more than one - choose
     
    392391            value_=value;
    393392            if (upMovement[i]<=downMovement[i])
    394               way_=UP_DOWN__NOTHING_DONE; // up
     393              way_ = WAY_UP_DOWN__NOTHING_DONE; // up
    395394            else
    396               way_=DOWN_UP__NOTHING_DONE; // down
     395              way_ = WAY_DOWN_UP__NOTHING_DONE; // down
    397396          }
    398397        }
     
    423422      value_=value;
    424423      if (value<=nearest)
    425         way_=UP_DOWN__NOTHING_DONE; // up
     424        way_ = WAY_UP_DOWN__NOTHING_DONE; // up
    426425      else
    427         way_=DOWN_UP__NOTHING_DONE; // down
     426        way_ = WAY_DOWN_UP__NOTHING_DONE; // down
    428427    }
    429428  }
     
    443442  numberIntegers_=rhs.numberIntegers_;
    444443  value_=rhs.value_;
    445   descendants_ = rhs.descendants_;
    446444  parent_ = rhs.parent_;
    447445  child_down_ = rhs.child_down_;
     
    475473    numberIntegers_=rhs.numberIntegers_;
    476474    value_=rhs.value_;
    477     descendants_ = rhs.descendants_;
    478475    parent_ = rhs.parent_;
    479476    child_down_ = rhs.child_down_;
     
    532529
    533530#include <vector>
    534 // #define FUNNY_BRANCHING 1
     531#define FUNNY_BRANCHING 1
    535532
    536533// Must code up by hand
     
    688685  //best();
    689686  size_++;
    690   assert (node.descendants_<=2);
    691   if (node.descendants_==2)
     687  if (node.bothChildDone())
    692688    sizeDeferred_++;
    693689}
     
    700696  if (chosen_<0) {
    701697    chosen_=last_;
    702     while (nodes_[chosen_].descendants_==2) {
     698    while (nodes_[chosen_].bothChildDone()) {
    703699      chosen_ = nodes_[chosen_].previous_;
    704700      assert (chosen_>=0);
     
    720716  // Temporary until more sophisticated
    721717  //assert (last_==chosen_);
    722   if (nodes_[chosen_].descendants_==2)
     718  if (nodes_[chosen_].bothChildDone())
    723719    sizeDeferred_--;
    724720  int previous = nodes_[chosen_].previous_;
     
    962958  parent.parent_ = greatgrandparent_id;
    963959  grandparent.parent_ = parent_id;
    964   const bool down_child_stays_with_parent = parent.way_ & DBNodeSimple::DOWN_CURRENT;
     960  const bool down_child_stays_with_parent = parent.way_ & DBNodeSimple::WAY_DOWN_CURRENT;
    965961  int& child_to_move =
    966962    down_child_stays_with_parent ? parent.child_up_ : parent.child_down_;
     
    983979  }
    984980
     981  // Now make sure way_ is set properly
     982  if (down_child_stays_with_parent) {
     983    if (!parent.bothChildDone()) {
     984      parent.way_ = DBNodeSimple::WAY_UP_DOWN__BOTH_DONE;
     985      sizeDeferred_++;
     986    }
     987    if (grandparent.bothChildDone()) {
     988      if (child_to_move == -1) {
     989        grandparent.way_ = parent_is_down_child ?
     990          DBNodeSimple::WAY_UP_DOWN__UP_DONE :
     991          DBNodeSimple::WAY_DOWN_UP__DOWN_DONE;
     992        sizeDeferred_--;
     993      }
     994    } else { // only parent is processed from the two children of grandparent
     995      if (child_to_move == -1) {
     996        grandparent.way_ = parent_is_down_child ?
     997          DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE :
     998          DBNodeSimple::WAY_UP_DOWN__NOTHING_DONE;
     999      } else {
     1000        grandparent.way_ = parent_is_down_child ?
     1001          DBNodeSimple::WAY_DOWN_UP__DOWN_DONE :
     1002          DBNodeSimple::WAY_UP_DOWN__UP_DONE;
     1003      }
     1004    }
     1005  } else {
     1006    if (!parent.bothChildDone()) {
     1007      parent.way_ = DBNodeSimple::WAY_DOWN_UP__BOTH_DONE;
     1008      sizeDeferred_++;
     1009    }
     1010    if (grandparent.bothChildDone()) {
     1011      if (child_to_move == -1) {
     1012        grandparent.way_ = parent_is_down_child ?
     1013          DBNodeSimple::WAY_UP_DOWN__UP_DONE :
     1014          DBNodeSimple::WAY_DOWN_UP__DOWN_DONE;
     1015        sizeDeferred_--;
     1016      }
     1017    } else { // only parent is processed from the two children of grandparent
     1018      if (child_to_move == -1) {
     1019        grandparent.way_ = parent_is_down_child ?
     1020          DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE :
     1021          DBNodeSimple::WAY_UP_DOWN__NOTHING_DONE;
     1022      } else {
     1023        grandparent.way_ = parent_is_down_child ?
     1024          DBNodeSimple::WAY_DOWN_UP__DOWN_DONE :
     1025          DBNodeSimple::WAY_UP_DOWN__UP_DONE;
     1026      }
     1027    }
     1028  }
     1029 
     1030 
    9851031  // Now modify bounds
    9861032
     
    11121158      int kNode = branchingTree.chosen_;
    11131159      branchingTree.pop_back();
    1114       assert (node.descendants_<2);
     1160      assert (! node.bothChildDone());
    11151161      numberNodes++;
    1116       if (node.variable_>=0) {
     1162      if (node.variable_ < 0) {
     1163        // put back on tree and pretend both children are done. We want the
     1164        // whole tree all the time.
     1165        node.way_ = DBNodeSimple::WAY_UP_DOWN__BOTH_DONE;
     1166        branchingTree.push_back(node);
     1167        // Integer solution - save
     1168        bestNode = node;
     1169        // set cutoff (hard coded tolerance)
     1170        const double limit = (bestNode.objectiveValue_-1.0e-5)*direction;
     1171        model.setDblParam(OsiDualObjectiveLimit, limit);
     1172        std::cout<<"Integer solution of "
     1173                 <<bestNode.objectiveValue_
     1174                 <<" found after "<<numberIterations
     1175                 <<" iterations and "<<numberNodes<<" nodes"
     1176                 <<std::endl;
     1177      } else {
    11171178        // branch - do bounds
    11181179        for (i=0;i<numberIntegers;i++) {
     
    11231184        model.setWarmStart(node.basis_);
    11241185        // do branching variable
    1125         node.incrementDescendants();
    11261186        bool down_branch = true;
    11271187        switch (node.way_) {
    11281188        case DBNodeSimple::WAY_UNSET:
    1129         case DBNodeSimple::DOWN_UP__BOTH_DONE:
    1130         case DBNodeSimple::UP_DOWN__BOTH_DONE:
     1189        case DBNodeSimple::WAY_DOWN_UP__BOTH_DONE:
     1190        case DBNodeSimple::WAY_UP_DOWN__BOTH_DONE:
    11311191          abort();
    1132         case DBNodeSimple::DOWN_UP__NOTHING_DONE:
    1133           node.way_ = DBNodeSimple::DOWN_UP__DOWN_DONE;
     1192        case DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE:
     1193          node.way_ = DBNodeSimple::WAY_DOWN_UP__DOWN_DONE;
    11341194          break;
    1135         case DBNodeSimple::DOWN_UP__DOWN_DONE:
    1136           node.way_ = DBNodeSimple::DOWN_UP__BOTH_DONE;
     1195        case DBNodeSimple::WAY_DOWN_UP__DOWN_DONE:
     1196          node.way_ = DBNodeSimple::WAY_DOWN_UP__BOTH_DONE;
    11371197          down_branch = false;
    11381198          break;
    1139         case DBNodeSimple::UP_DOWN__NOTHING_DONE:
    1140           node.way_ = DBNodeSimple::UP_DOWN__UP_DONE;
     1199        case DBNodeSimple::WAY_UP_DOWN__NOTHING_DONE:
     1200          node.way_ = DBNodeSimple::WAY_UP_DOWN__UP_DONE;
    11411201          down_branch = false;
    11421202          break;
    1143         case DBNodeSimple::UP_DOWN__UP_DONE:
    1144           node.way_ = DBNodeSimple::UP_DOWN__BOTH_DONE;
     1203        case DBNodeSimple::WAY_UP_DOWN__UP_DONE:
     1204          node.way_ = DBNodeSimple::WAY_UP_DOWN__BOTH_DONE;
    11451205          break;
    11461206        }
     
    12301290          // push on stack
    12311291          branchingTree.push_back(newNode);
    1232           if(branchingTree.nodes_[kNode].child_down_ < 0)
     1292          if(branchingTree.nodes_[kNode].way_ & DBNodeSimple::WAY_DOWN_CURRENT)
    12331293            branchingTree.nodes_[kNode].child_down_ = branchingTree.last_;
    12341294          else
     
    12511311#endif
    12521312        }
    1253       } else {
    1254         // Integer solution - save
    1255         bestNode = node;
    1256         // set cutoff (hard coded tolerance)
    1257         model.setDblParam(OsiDualObjectiveLimit,(bestNode.objectiveValue_-1.0e-5)*direction);
    1258         std::cout<<"Integer solution of "
    1259                  <<bestNode.objectiveValue_
    1260                  <<" found after "<<numberIterations
    1261                  <<" iterations and "<<numberNodes<<" nodes"
    1262                  <<std::endl;
    12631313      }
    12641314    }
Note: See TracChangeset for help on using the changeset viewer.