Changeset 1021 for branches/dynamicbranching
- Timestamp:
- Jul 24, 2008 5:05:25 PM (13 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/dynamicbranching/dynamicbranching.cpp
r1001 r1021 45 45 #define FUNNY_BRANCHING 1 46 46 #define DEBUG_DYNAMIC_BRANCHING 47 //#define DELETE_NODES 47 48 48 49 #ifdef DEBUG_DYNAMIC_BRANCHING … … 243 244 const int * original_upper, 244 245 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); 245 252 inline bool bothChildDone() const { 246 253 return (way_ & WAY_BOTH_DONE) == WAY_BOTH_DONE; … … 723 730 // Fix the bounds in the descendants of subroot 724 731 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); 725 735 726 736 // Check that the bounds correspond to the branching decisions... … … 926 936 } 927 937 938 int 939 DBNodeSimple::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 928 1072 bool 929 1073 DBNodeSimple::canSwitchParentWithGrandparent(const int* which, … … 1317 1461 } 1318 1462 } 1463 } 1464 1465 void 1466 DBVectorNode::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 1319 1534 } 1320 1535 … … 1622 1837 model.setDblParam(OsiDualObjectiveLimit, oldlimit); 1623 1838 } 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 1624 1846 bool canSwitch = 1625 1847 node.canSwitchParentWithGrandparent(which, lpres, originalLower, 1626 1848 originalUpper, branchingTree); 1849 #endif 1627 1850 int cnt = 0; 1628 1851 … … 1643 1866 1644 1867 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 1645 1876 branchingTree.moveNodeUp(which, model, node); 1646 1877 canSwitch = node.canSwitchParentWithGrandparent(which, lpres, … … 1648 1879 originalUpper, 1649 1880 branchingTree); 1881 #endif 1650 1882 #if defined(DEBUG_DYNAMIC_BRANCHING) 1651 1883 if (dyn_debug >= 1) {
Note: See TracChangeset
for help on using the changeset viewer.