Changeset 985
 Timestamp:
 Jun 19, 2008 2:31:42 PM (11 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/dynamicbranching/dynamicbranching.cpp
r981 r985 43 43 #include "OsiClpSolverInterface.hpp" 44 44 45 //#define DEBUG_DYNAMIC_BRANCHING 45 #define DEBUG_DYNAMIC_BRANCHING 100 46 46 47 47 // below needed for pathetic branch and bound code … … 56 56 public: 57 57 enum DBNodeWay { 58 WAY_UNSET=0x00, 58 59 WAY_DOWN_UP__NOTHING_DONE=0x10, 59 60 WAY_DOWN_UP__DOWN_DONE=0x11, … … 68 69 WAY_BOTH_DONE=0x03, 69 70 70 WAY_UNSET71 71 }; 72 72 … … 107 107 return (way_ & WAY_BOTH_DONE) == WAY_BOTH_DONE; 108 108 } 109 109 inline bool workingOnDownChild() const { 110 return (way_ == WAY_DOWN_UP__DOWN_DONE  way_ == WAY_UP_DOWN__BOTH_DONE); 111 } 112 /* Return whether the child that will be now processed is the down branch or 113 not. */ 114 inline bool advanceWay() { 115 switch (way_) { 116 case WAY_UNSET: 117 case WAY_DOWN_UP__BOTH_DONE: 118 case WAY_UP_DOWN__BOTH_DONE: 119 abort(); 120 case WAY_DOWN_UP__NOTHING_DONE: 121 way_ = WAY_DOWN_UP__DOWN_DONE; 122 return true; 123 case WAY_DOWN_UP__DOWN_DONE: 124 way_ = WAY_DOWN_UP__BOTH_DONE; 125 return false; 126 case WAY_UP_DOWN__NOTHING_DONE: 127 way_ = WAY_UP_DOWN__UP_DONE; 128 return false; 129 case WAY_UP_DOWN__UP_DONE: 130 way_ = WAY_UP_DOWN__BOTH_DONE; 131 return true; 132 } 133 return true; // to placate some compilers... 134 } 135 136 110 137 // Public data 111 138 // The id of the node … … 811 838 const DBNodeSimple& grandparent = branchingTree.nodes_[grandparent_id]; 812 839 840 // THINK: these are not going to happen (hopefully), but if they do, what 841 // should we do??? 842 if (model.isAbandoned()) { 843 printf("WARNING: model.isAbandoned() true!\n"); 844 return false; 845 } 813 846 if (model.isProvenDualInfeasible()) { 814 // THINK: this is not going to happen, but if it does, what should we do??? 847 printf("WARNING: model.isProvenDualInfeasible() true!\n"); 848 return false; 849 } 850 if (model.isPrimalObjectiveLimitReached()) { 851 printf("WARNING: model.isPrimalObjectiveLimitReached() true!\n"); 815 852 return false; 816 853 } … … 827 864 const bool parent_is_down_child = parent_id == grandparent.child_down_; 828 865 829 if (model.isProvenPrimalInfeasible()) { 866 if (model.isProvenOptimal()  867 model.isDualObjectiveLimitReached()  868 model.isIterationLimitReached()) { 869 // Dual feasible, and in this case we don't care how we have 870 // stopped (iteration limit, obj val limit, time limit, optimal solution, 871 // etc.), we can just look at the reduced costs to figure out if the 872 // grandparent is irrelevant. Remember, we are using dual simplex! 873 double djValue = model.getReducedCost()[GP_brvar_fullid]*direction; 874 if (djValue > 1.0e6) { 875 // wants to go down 876 if (parent_is_down_child) { 877 return true; 878 } 879 if (model.getColLower()[GP_brvar_fullid] > std::ceil(grandparent.value_)) { 880 return true; 881 } 882 } else if (djValue < 1.0e6) { 883 // wants to go up 884 if (! parent_is_down_child) { 885 return true; 886 } 887 if (model.getColUpper()[GP_brvar_fullid] < std::floor(grandparent.value_)) { 888 return true; 889 } 890 } 891 return false; 892 } else { 893 assert(model.isProvenPrimalInfeasible()); 830 894 const int greatgrandparent_id = grandparent.parent_; 831 895 const int x = GP_brvar_fullid; // for easier reference... we'll use s_x … … 841 905 const double* obj = model.getObjCoefficients(); 842 906 const double yA_x = dj[x]  obj[x]; 843 bool canSwitch = true;844 907 845 908 if (direction > 0) { // minimization problem 846 909 if (parent_is_down_child) { 847 910 const double s_x = CoinMax(yA_x, 1e8); 848 if (s_x > 1e6) { // if 0 then canSwitch can stay true849 const double yb_plus_rl_minus_su = compute_val_for_ray(model);850 if (yb_plus_rl_minus_su < 1e8) {851 printf("WARNING: yb_plus_rl_minus_su is not positive!\n");852 canSwitch = false;853 } else {854 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x];855 const double u_x_without_GP = greatgrandparent_id >= 0 ?856 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] :857 original_upper[GP_brvar];858 canSwitch = max_u_x > u_x_without_GP  1e8;859 }860 }911 if (s_x < 1e6) { 912 return true; 913 } 914 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 915 if (yb_plus_rl_minus_su < 1e8) { 916 printf("WARNING: yb_plus_rl_minus_su is not positive!\n"); 917 return false; 918 } 919 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x]; 920 const double u_x_without_GP = greatgrandparent_id >= 0 ? 921 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] : 922 original_upper[GP_brvar]; 923 return max_u_x > u_x_without_GP  1e8; 861 924 } else { 862 925 const double r_x = CoinMax(yA_x, 1e8); 863 if (r_x > 1e6) { // if 0 then canSwitch can stay true864 const double yb_plus_rl_minus_su = compute_val_for_ray(model);865 if (yb_plus_rl_minus_su < 1e8) {866 printf("WARNING: yb_plus_rl_minus_su is not positive!\n");867 canSwitch = false;868 } else {869 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x];870 const double l_x_without_GP = greatgrandparent_id >= 0 ?871 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] :872 original_lower[GP_brvar];873 canSwitch = min_l_x < l_x_without_GP + 1e8;874 }875 }926 if (r_x < 1e6) { 927 return true; 928 } 929 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 930 if (yb_plus_rl_minus_su < 1e8) { 931 printf("WARNING: yb_plus_rl_minus_su is not positive!\n"); 932 return false; 933 } 934 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x]; 935 const double l_x_without_GP = greatgrandparent_id >= 0 ? 936 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] : 937 original_lower[GP_brvar]; 938 return min_l_x < l_x_without_GP + 1e8; 876 939 } 877 940 } else { // maximization problem 878 941 if (parent_is_down_child) { 879 942 const double s_x = CoinMin(yA_x, 1e8); 880 if (s_x < 1e6) { // if 0 then canSwitch can stay true881 const double yb_plus_rl_minus_su = compute_val_for_ray(model);882 if (yb_plus_rl_minus_su > 1e8) {883 printf("WARNING: yb_plus_rl_minus_su is not negative!\n");884 canSwitch = false;885 } else {886 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x];887 const double u_x_without_GP = greatgrandparent_id >= 0 ?888 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] :889 original_upper[GP_brvar];890 canSwitch = max_u_x > u_x_without_GP  1e8;891 }892 }943 if (s_x > 1e6) { 944 return true; 945 } 946 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 947 if (yb_plus_rl_minus_su > 1e8) { 948 printf("WARNING: yb_plus_rl_minus_su is not negative!\n"); 949 return false; 950 } 951 const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x]; 952 const double u_x_without_GP = greatgrandparent_id >= 0 ? 953 branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] : 954 original_upper[GP_brvar]; 955 return max_u_x > u_x_without_GP  1e8; 893 956 } else { 894 957 const double r_x = CoinMin(yA_x, 1e8); 895 if (r_x > 1e6) { // if 0 then canSwitch can stay true 896 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 897 if (yb_plus_rl_minus_su > 1e8) { 898 printf("WARNING: yb_plus_rl_minus_su is not negative!\n"); 899 canSwitch = false; 900 } else { 901 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x]; 902 const double l_x_without_GP = greatgrandparent_id >= 0 ? 903 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] : 904 original_lower[GP_brvar]; 905 canSwitch = min_l_x < l_x_without_GP + 1e8; 906 } 907 } 908 } 909 } 910 911 return canSwitch; 912 } 913 // Both primal and dual feasible, and in this case we don't care how we have 914 // stopped (iteration limit, obj val limit, time limit, optimal solution, 915 // etc.), we can just look at the reduced costs to figure out if the 916 // grandparent is irrelevant. Remember, we are using dual simplex! 917 double djValue = model.getReducedCost()[GP_brvar_fullid]*direction; 918 if (djValue > 1.0e6) { 919 // wants to go down 920 if (parent_is_down_child) { 921 return true; 922 } 923 if (model.getColLower()[GP_brvar_fullid] > std::ceil(grandparent.value_)) { 924 return true; 925 } 926 return false; 927 } else if (djValue < 1.0e6) { 928 // wants to go up 929 if (! parent_is_down_child) { 930 return true; 931 } 932 if (model.getColUpper()[GP_brvar_fullid] < std::floor(grandparent.value_)) { 933 return true; 934 } 935 return false; 936 } 937 return false; 958 if (r_x < 1e6) { 959 return true; 960 } 961 const double yb_plus_rl_minus_su = compute_val_for_ray(model); 962 if (yb_plus_rl_minus_su > 1e8) { 963 printf("WARNING: yb_plus_rl_minus_su is not negative!\n"); 964 return false; 965 } 966 const double min_l_x =  yb_plus_rl_minus_su / r_x + model.getColLower()[x]; 967 const double l_x_without_GP = greatgrandparent_id >= 0 ? 968 branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] : 969 original_lower[GP_brvar]; 970 return min_l_x < l_x_without_GP + 1e8; 971 } 972 } 973 } 974 975 return true; // to placate some compilers 938 976 } 939 977 … … 947 985 variable names respecting the truth. 948 986 */ 987 const bool childWasInfeasible = model.isProvenPrimalInfeasible(); 949 988 const int parent_id = node.node_id_; 950 989 DBNodeSimple& parent = nodes_[parent_id]; … … 956 995 const bool parent_is_down_child = parent_id == grandparent.child_down_; 957 996 958 #if defined(DEBUG_DYNAMIC_BRANCHING) 997 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 959 998 printf("entered moveNodeUp\n"); 960 999 printf("parent_id %d grandparent_id %d greatgrandparent_id %d\n", … … 967 1006 parent.parent_ = greatgrandparent_id; 968 1007 grandparent.parent_ = parent_id; 969 const bool down_child_stays_with_parent = parent.w ay_ & DBNodeSimple::WAY_DOWN_CURRENT;1008 const bool down_child_stays_with_parent = parent.workingOnDownChild(); 970 1009 int& child_to_move = 971 1010 down_child_stays_with_parent ? parent.child_up_ : parent.child_down_; 972 973 #if defined(DEBUG_DYNAMIC_BRANCHING) 1011 const bool child_to_move_is_processed = parent.bothChildDone(); 1012 1013 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 974 1014 printf("parent_is_down_child %d down_child_stays_with_parent %d child_to_move %d\n", parent_is_down_child, down_child_stays_with_parent, child_to_move); 975 1015 #endif … … 993 1033 } 994 1034 995 #if defined(DEBUG_DYNAMIC_BRANCHING) 1035 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 996 1036 printf("after exchange\n"); 997 1037 printf("parent.parent_ %d parent.child_down_ %d parent.child_up_ %d\n", … … 1015 1055 } 1016 1056 if (grandparent.bothChildDone()) { 1017 if ( child_to_move == 1) {1057 if (! child_to_move_is_processed) { 1018 1058 grandparent.way_ = parent_is_down_child ? 1019 1059 DBNodeSimple::WAY_UP_DOWN__UP_DONE : … … 1022 1062 } 1023 1063 } else { // only parent is processed from the two children of grandparent 1024 if ( child_to_move == 1) {1064 if (! child_to_move_is_processed) { 1025 1065 grandparent.way_ = parent_is_down_child ? 1026 1066 DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE : … … 1038 1078 } 1039 1079 if (grandparent.bothChildDone()) { 1040 if ( child_to_move == 1) {1080 if (! child_to_move_is_processed) { 1041 1081 grandparent.way_ = parent_is_down_child ? 1042 1082 DBNodeSimple::WAY_UP_DOWN__UP_DONE : … … 1045 1085 } 1046 1086 } else { // only parent is processed from the two children of grandparent 1047 if ( child_to_move == 1) {1087 if (! child_to_move_is_processed) { 1048 1088 grandparent.way_ = parent_is_down_child ? 1049 1089 DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE : … … 1064 1104 const int GP_brvar = grandparent.variable_; 1065 1105 if (parent_is_down_child) { 1066 const int old_upper = greatgrandparent_id >= 0 ? 1067 nodes_[greatgrandparent_id].upper_[GP_brvar] : 1068 grandparent.upper_[GP_brvar]; 1106 const int old_upper = grandparent.upper_[GP_brvar]; 1069 1107 parent.upper_[GP_brvar] = old_upper; 1070 1108 model.setColUpper(which[GP_brvar], old_upper); 1071 1109 } else { 1072 const int old_lower = greatgrandparent_id >= 0 ? 1073 nodes_[greatgrandparent_id].lower_[GP_brvar] : 1074 grandparent.lower_[GP_brvar]; 1110 const int old_lower = grandparent.lower_[GP_brvar]; 1075 1111 parent.lower_[GP_brvar] = old_lower; 1076 1112 model.setColLower(which[GP_brvar], old_lower); 1077 1113 } 1114 #if 0 1078 1115 // THINK: this might not be necessary 1079 1116 model.resolve(); 1117 #endif 1080 1118 1081 1119 // Now add the branching var bound change of P to GP and all of its … … 1099 1137 false /*lower bd*/, P_brvar, new_bd); 1100 1138 } 1139 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 1140 if (childWasInfeasible) { 1141 model.resolve(); 1142 assert(model.isProvenPrimalInfeasible()); 1143 } 1144 #endif 1101 1145 } 1102 1146 … … 1182 1226 // while until nothing on stack 1183 1227 while (branchingTree.size()) { 1184 #if defined(DEBUG_DYNAMIC_BRANCHING) 1228 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 1185 1229 printf("branchingTree.size = %d %d\n",branchingTree.size(),branchingTree.size_); 1186 1230 printf("i node_id parent child_down child_up\n"); … … 1195 1239 int kNode = branchingTree.chosen_; 1196 1240 branchingTree.pop_back(); 1197 #if defined(DEBUG_DYNAMIC_BRANCHING) 1241 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 1198 1242 printf("Deleted current parent %d %d\n",branchingTree.size(),branchingTree.size_); 1199 1243 #endif … … 1224 1268 model.setWarmStart(node.basis_); 1225 1269 // do branching variable 1226 bool down_branch = true; 1227 switch (node.way_) { 1228 case DBNodeSimple::WAY_UNSET: 1229 case DBNodeSimple::WAY_DOWN_UP__BOTH_DONE: 1230 case DBNodeSimple::WAY_UP_DOWN__BOTH_DONE: 1231 abort(); 1232 case DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE: 1233 node.way_ = DBNodeSimple::WAY_DOWN_UP__DOWN_DONE; 1234 break; 1235 case DBNodeSimple::WAY_DOWN_UP__DOWN_DONE: 1236 node.way_ = DBNodeSimple::WAY_DOWN_UP__BOTH_DONE; 1237 down_branch = false; 1238 break; 1239 case DBNodeSimple::WAY_UP_DOWN__NOTHING_DONE: 1240 node.way_ = DBNodeSimple::WAY_UP_DOWN__UP_DONE; 1241 down_branch = false; 1242 break; 1243 case DBNodeSimple::WAY_UP_DOWN__UP_DONE: 1244 node.way_ = DBNodeSimple::WAY_UP_DOWN__BOTH_DONE; 1245 break; 1246 } 1270 const bool down_branch = node.advanceWay(); 1247 1271 if (down_branch) { 1248 1272 model.setColUpper(which[node.variable_],floor(node.value_)); … … 1253 1277 // to be done. We want the whole tree all the time. 1254 1278 branchingTree.push_back(node); 1255 #if defined(DEBUG_DYNAMIC_BRANCHING) 1279 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 1256 1280 printf("Added current parent %d %d\n",branchingTree.size(),branchingTree.size_); 1257 1281 #endif … … 1307 1331 } 1308 1332 1309 while (node.canSwitchParentWithGrandparent(which, model, 1310 originalLower, 1311 originalUpper, 1312 branchingTree)) { 1313 branchingTree.moveNodeUp(which, model, node); 1314 #if defined(DEBUG_DYNAMIC_BRANCHING) 1315 printf("It moved a node up. The current state is:\n"); 1316 printf("i node_id parent child_down child_up\n"); 1333 bool canSwitch = node.canSwitchParentWithGrandparent(which, model, 1334 originalLower, 1335 originalUpper, 1336 branchingTree); 1337 int cnt = 0; 1338 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 100 1339 std::string tree0; 1340 char line[1000]; 1341 if (canSwitch) { 1317 1342 for(int k=0; k<branchingTree.size_; k++) { 1318 1343 DBNodeSimple& node = branchingTree.nodes_[k]; 1319 printf("%d %d %d %d %d\n",k, node.node_id_, node.parent_, 1320 node.child_down_, node.child_up_); 1344 sprintf(line, "%d %d %d 0x%x %d %d\n", 1345 k, node.node_id_, node.parent_, node.way_, 1346 node.child_down_, node.child_up_); 1347 tree0 += line; 1321 1348 } 1349 } 1322 1350 #endif 1323 } 1351 1352 while (canSwitch) { 1353 branchingTree.moveNodeUp(which, model, node); 1354 canSwitch = node.canSwitchParentWithGrandparent(which, model, 1355 originalLower, 1356 originalUpper, 1357 branchingTree); 1358 ++cnt; 1359 } 1360 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 100 1361 if (cnt > 0) { 1362 std::string tree1; 1363 for(int k=0; k<branchingTree.size_; k++) { 1364 DBNodeSimple& node = branchingTree.nodes_[k]; 1365 sprintf(line, "%d %d %d 0x%x %d %d\n", 1366 k, node.node_id_, node.parent_, node.way_, 1367 node.child_down_, node.child_up_); 1368 tree1 += line; 1369 } 1370 printf("=====================================\n"); 1371 printf("It can move node %i up. way_: 0x%x brvar: %i\n", 1372 node.node_id_, node.way_, node.variable_); 1373 printf("i node_id parent child_down child_up\n"); 1374 size_t pos = tree0.size(); 1375 for (int ii = cnt + 10; ii >= 0; ii) { 1376 pos = tree0.rfind('\n', pos1); 1377 if (pos == std::string::npos) { 1378 pos = 0; 1379 break; 1380 } 1381 } 1382 printf("%s", tree0.c_str() + (pos+1)); 1383 printf("=====================================\n"); 1384 printf("Finished moving the node up by %i levels.\n", cnt); 1385 pos = tree1.size(); 1386 for (int ii = cnt + 10; ii >= 0; ii) { 1387 pos = tree1.rfind('\n', pos1); 1388 if (pos == std::string::npos) { 1389 pos = 0; 1390 break; 1391 } 1392 } 1393 printf("%s", tree1.c_str() + (pos+1)); 1394 printf("=====================================\n"); 1395 } 1396 #endif 1324 1397 if ((numberNodes%1000)==0) 1325 1398 printf("%d nodes, tree size %d\n", … … 1342 1415 // push on stack 1343 1416 branchingTree.push_back(newNode); 1344 #if defined(DEBUG_DYNAMIC_BRANCHING) 1345 1417 #if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000 1418 printf("Added current child %d %d\n",branchingTree.size(),branchingTree.size_); 1346 1419 #endif 1347 if (branchingTree.nodes_[kNode].way_ & DBNodeSimple::WAY_DOWN_CURRENT)1420 if (branchingTree.nodes_[kNode].workingOnDownChild()) { 1348 1421 branchingTree.nodes_[kNode].child_down_ = branchingTree.last_; 1349 else1422 } else { 1350 1423 branchingTree.nodes_[kNode].child_up_ = branchingTree.last_; 1424 } 1351 1425 if (newNode.variable_>=0) { 1352 1426 assert (fabs(newNode.value_floor(newNode.value_+0.5))>1.0e6);
Note: See TracChangeset
for help on using the changeset viewer.