Changeset 972


Ignore:
Timestamp:
Jun 9, 2008 6:19:42 PM (11 years ago)
Author:
ladanyi
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r971 r972  
    1212public:
    1313  enum DBNodeWay {
    14     DOWN_UP__NOTHING_DONE,
    15     DOWN_UP__DOWN_DONE,
    16     DOWN_UP__BOTH_DONE,
    17     UP_DOWN__NOTHING_DONE,
    18     UP_DOWN__UP_DONE,
    19     UP_DOWN__BOTH_DONE,
     14    DOWN_UP__NOTHING_DONE=0x11,
     15    DOWN_UP__DOWN_DONE=0x12,
     16    DOWN_UP__BOTH_DONE=0x14,
     17    DOWN_UP__=0x10,
     18    UP_DOWN__NOTHING_DONE=0x21,
     19    UP_DOWN__UP_DONE=0x24,
     20    UP_DOWN__BOTH_DONE=0x22,
     21    UP_DOWN__=0x20,
     22    DOWN_CURRENT=0x02,
     23    UP_CURRENT=0x04,
    2024    WAY_UNSET
    2125  };
     
    6872  int parent_;
    6973  // Left child
    70   int child0_;
     74  int child_down_;
    7175  // Right child
    72   int child1_;
     76  int child_up_;
    7377  // Previous in chain
    7478  int previous_;
     
    9195  descendants_(-1),
    9296  parent_(-1),
    93   child0_(-1),
    94   child1_(-1),
     97  child_down_(-1),
     98  child_up_(-1),
    9599  previous_(-1),
    96100  next_(-1),
     
    115119  descendants_ = 0;
    116120  parent_ = -1;
    117   child0_ = -1;
    118   child1_ = -1;
     121  child_down_ = -1;
     122  child_up_ = -1;
    119123  previous_ = -1;
    120124  next_ = -1;
     
    378382  descendants_ = rhs.descendants_;
    379383  parent_ = rhs.parent_;
    380   child0_ = rhs.child0_;
    381   child1_ = rhs.child1_;
     384  child_down_ = rhs.child_down_;
     385  child_up_ = rhs.child_up_;
    382386  previous_ = rhs.previous_;
    383387  next_ = rhs.next_;
     
    407411    descendants_ = rhs.descendants_;
    408412    parent_ = rhs.parent_;
    409     child0_ = rhs.child0_;
    410     child1_ = rhs.child1_;
     413    child_down_ = rhs.child_down_;
     414    child_up_ = rhs.child_up_;
    411415    previous_ = rhs.previous_;
    412416    next_ = rhs.next_;
     
    674678}
    675679#endif
     680
     681bool
     682DBNodeSimple::isGrandparentIrrelevant()
     683{
     684#if !defined(FUNNY_BRANCHING)
     685  return false;
     686#endif
     687
     688  if (parent_ == -1) {
     689    // can't flip root higher up...
     690    return false;
     691  }
     692 
     693  if (model.isProvenDualInfeasible()) {
     694    // THINK: this is not going to happen, but if it does, what should we do???
     695    return false;
     696  }
     697  if (model.isProvenPrimalInfeasible()) {
     698    ...;
     699  }
     700  // Both primal and dual feasible, and in this case we don't care how we have
     701  // stopped (iteration limit, obj val limit, time limit, optimal solution,
     702  // etc.), we can just look at the reduced costs to figure out if the
     703  // grandparent is irrelevant. Remember, we are using dual simplex!
     704  const DBNodeSimple& parent = branchingTree.nodes_[parent_];
     705  const int iColumn = which[parent.variable_];
     706  double djValue = model.getReducedCost()[iColumn]*direction;
     707  const bool down_child = branchingTree.nodeIndex(node) == parent.child_down_;
     708  if (djValue>1.0e-6) {
     709    // wants to go down
     710    if (down_child) {
     711      return true;
     712    }
     713    const double up_lower = std::floor(parent.value_);
     714    if (model.getColLower()[iColumn] > up_lower) {
     715      return true;
     716    }
     717    return false;
     718  } else {
     719    // wants to go up
     720    if (!down_child) {
     721      return true;
     722    }
     723    const double down_upper = std::ceil(parent.value_);
     724    if (model.getColUpper()[iColumn] < down_upper) {
     725      return true;
     726    }
     727    return false;
     728  }
     729  return false;
     730}
     731
     732void
     733DBVectorNode::moveNodeUp()
     734{
     735  assert(parent != -1);
     736  const int parent_id = node.parent_;
     737  const DBNodeSimple& parent = branchingTree.nodes_[parent_id];
     738  const int node_id = branchingTree.nodeIndex(node);
     739  const bool node_is_down_child = node_id == parent.child_down_;
     740  const int grandparent_id = parent.parent_;
     741
     742  // First hang the nodes where they belong.
     743  node.parent_ = grandparent_id;
     744  parent.parent_ = node_id;
     745#if 1
     746  int& child_to_move = (node.way_ & DOWN_CURRENT) ? node.child_up_ : node.child_down_;
     747  if (node_is_down_child) {
     748    parent.child_down_ = child_to_move;
     749  } else {
     750    parent.child_up_ = child_to_move;
     751  }
     752  if (child_to_move >= 0) {
     753    branchingTree.nodes_[child_to_move].parent_ = parent_id;
     754  }
     755  child_to_move = parent_id;
     756#else
     757  if (node.way_ & DOWN_CURRENT) {
     758    if (node_is_down_child) {
     759      parent.child_down_ = node.child_up_;
     760    } else {
     761      parent.child_up_ = node.child_up_;
     762    }
     763    if (node.child_up_ >= 0) {
     764      branchingTree.nodes_[node.child_up_].parent_ = parent_id;
     765    }
     766    node.child_up_ = parent_id;
     767  } else { // must be UP_CURRENT
     768    if (node_is_down_child) {
     769      parent.child_down_ = node.child_down_;
     770    } else {
     771      parent.child_up_ = node.child_down_;
     772    }
     773    if (node.child_down_ >= 0) {
     774      branchingTree.nodes_[node.child_down_].parent_ = parent_id;
     775    }
     776    node.child_down_ = parent_id;
     777  }
     778#endif
     779  if (grandparent_id >= 0) {
     780    if (parent_id == branchingTree.nodes_[grandparent_id].child_down_) {
     781      branchingTree.nodes_[grandparent_id].child_down_ = node_id;
     782    } else {
     783      branchingTree.nodes_[grandparent_id].child_up_ = node_id;
     784    }
     785  }
     786
     787  // Now modify bounds
     788
     789  // THINK: could be avoided if always start from original bounds and go back
     790  // to root to apply all branching decisions. On the other hand, reduced cost
     791  // fixing would be lost. And so would fixings by strong branching. Actually,
     792  // what we'd ideally need to do is to apply flipping when strong branching
     793  // fixes a variable.
     794}
     795
     796
     797
     798
    676799
    677800bool moveNodes(OsiSolverInterface & model,
     
    847970          //printf("%d fixed to lower, %d fixed to upper\n",nFixed0,nFixed1);
    848971        }
    849         if (!model.isIterationLimitReached()) {
     972        if (model.isAbandoned()) {
     973          // THINK: What the heck should we do???
     974          abort();
     975        }
     976        if (node.isGrandparentIrrelevant()) {
     977          branchingTree.moveNodeUp(node);
     978        }
     979
     980
     981
     982
     983        if (!model.isIterationLimitReached()) {
    850984          if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) {
    851985#if FUNNY_BRANCHING
     
    10571191              // push on stack
    10581192              branchingTree.push_back(newNode);
    1059               if(branchingTree.nodes_[kNode].child0_ < 0)
    1060                 branchingTree.nodes_[kNode].child0_ = branchingTree.last_;
     1193              if(branchingTree.nodes_[kNode].child_down_ < 0)
     1194                branchingTree.nodes_[kNode].child_down_ = branchingTree.last_;
    10611195              else
    1062                 branchingTree.nodes_[kNode].child1_ = branchingTree.last_;
     1196                branchingTree.nodes_[kNode].child_up_ = branchingTree.last_;
    10631197#if 0
    10641198              } else {
Note: See TracChangeset for help on using the changeset viewer.