Changeset 1021 for branches


Ignore:
Timestamp:
Jul 24, 2008 5:05:25 PM (11 years ago)
Author:
jpgoncal
Message:

Added methods to delete nodes above the current node.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r1001 r1021  
    4545#define FUNNY_BRANCHING 1
    4646#define DEBUG_DYNAMIC_BRANCHING
     47//#define DELETE_NODES
    4748
    4849#ifdef DEBUG_DYNAMIC_BRANCHING
     
    243244                                      const int * original_upper,
    244245                                      DBVectorNode & branchingTree);
     246  // returns the node_id of the node that can be deleted. If -1, no node can be deleted
     247  int nodeToSwitchWithParent(const int* which,
     248                             LPresult& lpres,
     249                             const int * original_lower,
     250                             const int * original_upper,
     251                             DBVectorNode & branchingTree);
    245252  inline bool bothChildDone() const {
    246253    return (way_ & WAY_BOTH_DONE) == WAY_BOTH_DONE;
     
    723730  // Fix the bounds in the descendants of subroot
    724731  void adjustBounds(int subroot, int brvar, int brlb, int brub);
     732  // Delete the node that was selected for deletion
     733  void deleteSelectedNode(int node_to_delete_id, const int* which,
     734                          OsiSolverInterface& model, DBNodeSimple & node);
    725735
    726736  // Check that the bounds correspond to the branching decisions...
     
    926936}
    927937
     938int
     939DBNodeSimple::nodeToSwitchWithParent(const int* which,
     940                                     LPresult& lpres,
     941                                     const int * original_lower,
     942                                     const int * original_upper,
     943                                     DBVectorNode & branchingTree)
     944{
     945  /*
     946    The current node ('this') is really the parent (P) and the solution in the
     947    lpres represents the child. The grandparent (GP) is this.parent_. Let's have
     948    variable names respecting the truth.
     949  */
     950#if !defined(FUNNY_BRANCHING)
     951  return -1;
     952#endif
     953
     954  const int parent_id = node_id_;
     955  const DBNodeSimple& parent = branchingTree.nodes_[parent_id];
     956  const int grandparent_id = parent.parent_;
     957
     958  if (grandparent_id == -1) {
     959    // can't flip root higher up...
     960    return -1;
     961  }
     962  //  const DBNodeSimple& grandparent = branchingTree.nodes_[grandparent_id];
     963 
     964  // THINK: these are not going to happen (hopefully), but if they do, what
     965  // should we do???
     966  if (lpres.isAbandoned) {
     967    printf("WARNING: lpres.isAbandoned true!\n");
     968    return -1;
     969  }
     970  if (lpres.isProvenDualInfeasible) {
     971    printf("WARNING: lpres.isProvenDualInfeasible true!\n");
     972    return -1;
     973  }
     974  if (lpres.isPrimalObjectiveLimitReached) {
     975    printf("WARNING: lpres.isPrimalObjectiveLimitReached true!\n");
     976    return -1;
     977  }
     978
     979  if (parent.strong_branching_fixed_vars_ || parent.reduced_cost_fixed_vars_)
     980    return -1;
     981
     982  if (lpres.isIterationLimitReached) {
     983    // THINK: should we do anything?
     984    return -1;
     985  }
     986
     987  // make sure that the parent has only one branch
     988  if(parent.way_ != DBNodeSimple::WAY_UP_DOWN__UP_DONE &&
     989     parent.way_ != DBNodeSimple::WAY_DOWN_UP__DOWN_DONE)
     990    return -1;
     991 
     992  const double direction = lpres.getObjSense;
     993
     994
     995  int node_to_switch_id = -1;
     996  int node_to_check_id = grandparent_id;
     997  int child_of_node_to_check_id = parent_id;
     998
     999  while(node_to_check_id != -1) {
     1000
     1001    const DBNodeSimple& node_to_check = branchingTree.nodes_[node_to_check_id];
     1002
     1003    if (node_to_check.strong_branching_fixed_vars_ ||
     1004        node_to_check.reduced_cost_fixed_vars_) {
     1005      return node_to_switch_id;
     1006    }
     1007
     1008    // make sure that the node_to_check has only one branch
     1009    if(node_to_check.way_ != DBNodeSimple::WAY_UP_DOWN__UP_DONE &&
     1010       node_to_check.way_ != DBNodeSimple::WAY_DOWN_UP__DOWN_DONE)
     1011      return node_to_switch_id;
     1012
     1013    const int GP_brvar = node_to_check.variable_;
     1014    const int GP_brvar_fullid = which[GP_brvar];
     1015    const bool parent_is_down_child = child_of_node_to_check_id == node_to_check.child_down_;
     1016
     1017   
     1018    // At this point the only flags of interest are isProvenOptimal,
     1019    // isDualObjectiveLimitReached and isProvenPrimalInfeasible.
     1020    // Note that isDualObjectiveLimitReached can't be true alone (search for
     1021    // mustResolve).
     1022
     1023   
     1024    if (lpres.isProvenOptimal) {
     1025      // May or may not be over the dual obj limit. If the obj val of parent is
     1026      // higher than that of the node_to_check then we allow switching.
     1027      // NOTE: node_to_check's obj val can;t be 1e100 since then parent would not
     1028      // exist...
     1029      if (lpres.getObjValue > node_to_check.objectiveValue_ + 1e-8) {
     1030        double djValue = lpres.getReducedCost[GP_brvar_fullid]*direction;
     1031        bool should_switch = false;
     1032        if (djValue > 1.0e-6) {
     1033          // wants to go down
     1034          if (parent_is_down_child) {
     1035            should_switch = true;
     1036          }
     1037          else if (lpres.getColLower[GP_brvar_fullid] > std::ceil(node_to_check.value_)) {
     1038            should_switch = true;
     1039          }
     1040        } else if (djValue < -1.0e-6) {
     1041          // wants to go up
     1042          if (! parent_is_down_child) {
     1043            should_switch = true;
     1044          }
     1045          else if (lpres.getColUpper[GP_brvar_fullid] < std::floor(node_to_check.value_)) {
     1046            should_switch = true;
     1047          }
     1048        }
     1049        if(should_switch) {
     1050          node_to_switch_id = node_to_check_id;
     1051          child_of_node_to_check_id = node_to_check_id;
     1052          node_to_check_id = node_to_check.parent_;
     1053        }
     1054        else
     1055          node_to_check_id = -1;
     1056      }
     1057      else
     1058        node_to_check_id = -1;
     1059    }
     1060    else {
     1061      // Problem is really infeasible and has a dual ray.
     1062      assert(lpres.isProvenPrimalInfeasible);
     1063
     1064      return -1;
     1065    }
     1066
     1067  }
     1068
     1069  return node_to_switch_id;
     1070}
     1071
    9281072bool
    9291073DBNodeSimple::canSwitchParentWithGrandparent(const int* which,
     
    13171461    }
    13181462  }
     1463}
     1464
     1465void
     1466DBVectorNode::deleteSelectedNode(int node_to_delete_id, const int* which,
     1467                                 OsiSolverInterface& model, DBNodeSimple & node)
     1468{
     1469  // loop from the current node up until it finds the node_to_delete
     1470  int parent_id = node.node_id_;
     1471  DBNodeSimple& parent = nodes_[parent_id];
     1472  int grandparent_id = parent.parent_;
     1473  assert(grandparent_id != -1);
     1474
     1475  while(grandparent_id != node_to_delete_id) {
     1476    parent_id = grandparent_id;
     1477    grandparent_id = nodes_[parent_id].parent_;
     1478    assert(grandparent_id != -1);
     1479  }
     1480
     1481  DBNodeSimple& grandparent = nodes_[grandparent_id];
     1482  const int greatgrandparent_id = grandparent.parent_;
     1483
     1484  const bool parent_is_down_child = parent_id == grandparent.child_down_;
     1485
     1486  // First hang the nodes where they belong.
     1487  DBNodeSimple& parent_0 = nodes_[parent_id];
     1488  parent_0.parent_ = greatgrandparent_id;
     1489  if (greatgrandparent_id >= 0) {
     1490    DBNodeSimple& greatgrandparent = nodes_[greatgrandparent_id];
     1491    if (grandparent_id == greatgrandparent.child_down_) {
     1492      greatgrandparent.child_down_ = parent_id;
     1493    } else {
     1494      greatgrandparent.child_up_ = parent_id;
     1495    }
     1496  }
     1497
     1498  // Now modify bounds
     1499
     1500  // First, get rid of GP's bound change of its branching variable in the
     1501  // bound list of P. Note: If greatgrandparent_id is < 0 then GP is the root
     1502  // so its bounds are the original bounds.
     1503  const int GP_brvar = grandparent.variable_;
     1504  parent_id = node.node_id_;
     1505  DBNodeSimple& parent_1 = nodes_[parent_id];
     1506  if (parent_is_down_child) {
     1507    const int old_upper = grandparent.upper_[GP_brvar];
     1508    parent_1.upper_[GP_brvar] = old_upper;
     1509    if (GP_brvar != parent_1.variable_)
     1510      model.setColUpper(which[GP_brvar], old_upper);
     1511  } else {
     1512    const int old_lower = grandparent.lower_[GP_brvar];
     1513    parent_1.lower_[GP_brvar] = old_lower;
     1514    if (GP_brvar != parent_1.variable_)
     1515      model.setColLower(which[GP_brvar], old_lower);
     1516  }
     1517  parent_id = parent_1.parent_;
     1518  while(parent_id != greatgrandparent_id) {
     1519    DBNodeSimple& parent_2 = nodes_[parent_id];   
     1520    if (parent_is_down_child) {
     1521      const int old_upper = grandparent.upper_[GP_brvar];
     1522      parent_2.upper_[GP_brvar] = old_upper;
     1523    } else {
     1524      const int old_lower = grandparent.lower_[GP_brvar];
     1525      parent_2.lower_[GP_brvar] = old_lower;
     1526    }
     1527    parent_id = parent_2.parent_;
     1528  }   
     1529
     1530  // remove grandparent
     1531  removeNode(grandparent_id);
     1532  //  sizeDeferred_--; // this is not needed because the grandparent just had 1 branch
     1533
    13191534}
    13201535
     
    16221837            model.setDblParam(OsiDualObjectiveLimit, oldlimit);
    16231838          }
     1839#if defined(DELETE_NODES)
     1840          int node_to_delete = node.nodeToSwitchWithParent(which, lpres, originalLower,
     1841                                                           originalUpper, branchingTree);
     1842          bool canSwitch = false;
     1843          if(node_to_delete >= 0)
     1844            canSwitch = true;
     1845#else
    16241846          bool canSwitch =
    16251847            node.canSwitchParentWithGrandparent(which, lpres, originalLower,
    16261848                                                originalUpper, branchingTree);
     1849#endif
    16271850          int cnt = 0;
    16281851
     
    16431866
    16441867          while (canSwitch) {
     1868#if defined(DELETE_NODES)
     1869            branchingTree.deleteSelectedNode(node_to_delete, which, model, node);
     1870            node_to_delete = node.nodeToSwitchWithParent(which, lpres, originalLower,
     1871                                                         originalUpper, branchingTree);
     1872            canSwitch = false;
     1873            if(node_to_delete >= 0)
     1874              canSwitch = true;
     1875#else
    16451876            branchingTree.moveNodeUp(which, model, node);
    16461877            canSwitch = node.canSwitchParentWithGrandparent(which, lpres,
     
    16481879                                                            originalUpper,
    16491880                                                            branchingTree);
     1881#endif
    16501882#if defined(DEBUG_DYNAMIC_BRANCHING)
    16511883            if (dyn_debug >= 1) {
Note: See TracChangeset for help on using the changeset viewer.