Changeset 985 for branches


Ignore:
Timestamp:
Jun 19, 2008 2:31:42 PM (11 years ago)
Author:
ladanyi
Message:

slowly debugging

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r981 r985  
    4343#include "OsiClpSolverInterface.hpp"
    4444
    45 //#define DEBUG_DYNAMIC_BRANCHING
     45#define DEBUG_DYNAMIC_BRANCHING 100
    4646
    4747// below needed for pathetic branch and bound code
     
    5656public:
    5757  enum DBNodeWay {
     58    WAY_UNSET=0x00,
    5859    WAY_DOWN_UP__NOTHING_DONE=0x10,
    5960    WAY_DOWN_UP__DOWN_DONE=0x11,
     
    6869    WAY_BOTH_DONE=0x03,
    6970   
    70     WAY_UNSET
    7171  };
    7272 
     
    107107    return (way_ & WAY_BOTH_DONE) == WAY_BOTH_DONE;
    108108  }
    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 
    110137  // Public data
    111138  // The id of the node
     
    811838  const DBNodeSimple& grandparent = branchingTree.nodes_[grandparent_id];
    812839 
     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  }
    813846  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");
    815852    return false;
    816853  }
     
    827864  const bool parent_is_down_child = parent_id == grandparent.child_down_;
    828865
    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.0e-6) {
     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.0e-6) {
     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());
    830894    const int greatgrandparent_id = grandparent.parent_;
    831895    const int x = GP_brvar_fullid; // for easier reference... we'll use s_x
     
    841905    const double* obj = model.getObjCoefficients();
    842906    const double yA_x = dj[x] - obj[x];
    843     bool canSwitch = true;
    844907
    845908    if (direction > 0) { // minimization problem
    846909      if (parent_is_down_child) {
    847910        const double s_x = CoinMax(yA_x, -1e-8);
    848         if (s_x > 1e-6) { // if 0 then canSwitch can stay true
    849           const double yb_plus_rl_minus_su = compute_val_for_ray(model);
    850           if (yb_plus_rl_minus_su < 1e-8) {
    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 - 1e-8;
    859           }
    860         }
     911        if (s_x < 1e-6) {
     912          return true;
     913        }
     914        const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     915        if (yb_plus_rl_minus_su < 1e-8) {
     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 - 1e-8;
    861924      } else {
    862925        const double r_x = CoinMax(yA_x, -1e-8);
    863         if (r_x > 1e-6) { // if 0 then canSwitch can stay true
    864           const double yb_plus_rl_minus_su = compute_val_for_ray(model);
    865           if (yb_plus_rl_minus_su < 1e-8) {
    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 + 1e-8;
    874           }
    875         }
     926        if (r_x < 1e-6) {
     927          return true;
     928        }
     929        const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     930        if (yb_plus_rl_minus_su < 1e-8) {
     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 + 1e-8;
    876939      }
    877940    } else { // maximization problem
    878941      if (parent_is_down_child) {
    879942        const double s_x = CoinMin(yA_x, 1e-8);
    880         if (s_x < -1e-6) { // if 0 then canSwitch can stay true
    881           const double yb_plus_rl_minus_su = compute_val_for_ray(model);
    882           if (yb_plus_rl_minus_su > -1e-8) {
    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 - 1e-8;
    891           }
    892         }
     943        if (s_x > -1e-6) {
     944          return true;
     945        }
     946        const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     947        if (yb_plus_rl_minus_su > -1e-8) {
     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 - 1e-8;
    893956      } else {
    894957        const double r_x = CoinMin(yA_x, 1e-8);
    895         if (r_x > -1e-6) { // 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 > -1e-8) {
    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 + 1e-8;
    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.0e-6) {
    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.0e-6) {
    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 < -1e-6) {
     959          return true;
     960        }
     961        const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     962        if (yb_plus_rl_minus_su > -1e-8) {
     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 + 1e-8;
     971      }
     972    }
     973  }
     974
     975  return true; // to placate some compilers
    938976}
    939977
     
    947985    variable names respecting the truth.
    948986  */
     987  const bool childWasInfeasible = model.isProvenPrimalInfeasible();
    949988  const int parent_id = node.node_id_;
    950989  DBNodeSimple& parent = nodes_[parent_id];
     
    956995  const bool parent_is_down_child = parent_id == grandparent.child_down_;
    957996
    958 #if defined(DEBUG_DYNAMIC_BRANCHING)
     997#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
    959998  printf("entered moveNodeUp\n");
    960999  printf("parent_id %d grandparent_id %d greatgrandparent_id %d\n",
     
    9671006  parent.parent_ = greatgrandparent_id;
    9681007  grandparent.parent_ = parent_id;
    969   const bool down_child_stays_with_parent = parent.way_ & DBNodeSimple::WAY_DOWN_CURRENT;
     1008  const bool down_child_stays_with_parent = parent.workingOnDownChild();
    9701009  int& child_to_move =
    9711010    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
    9741014  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);
    9751015#endif
     
    9931033  }
    9941034
    995 #if defined(DEBUG_DYNAMIC_BRANCHING)
     1035#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
    9961036  printf("after exchange\n");
    9971037  printf("parent.parent_ %d parent.child_down_ %d parent.child_up_ %d\n",
     
    10151055    }
    10161056    if (grandparent.bothChildDone()) {
    1017       if (child_to_move == -1) {
     1057      if (! child_to_move_is_processed) {
    10181058        grandparent.way_ = parent_is_down_child ?
    10191059          DBNodeSimple::WAY_UP_DOWN__UP_DONE :
     
    10221062      }
    10231063    } else { // only parent is processed from the two children of grandparent
    1024       if (child_to_move == -1) {
     1064      if (! child_to_move_is_processed) {
    10251065        grandparent.way_ = parent_is_down_child ?
    10261066          DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE :
     
    10381078    }
    10391079    if (grandparent.bothChildDone()) {
    1040       if (child_to_move == -1) {
     1080      if (! child_to_move_is_processed) {
    10411081        grandparent.way_ = parent_is_down_child ?
    10421082          DBNodeSimple::WAY_UP_DOWN__UP_DONE :
     
    10451085      }
    10461086    } else { // only parent is processed from the two children of grandparent
    1047       if (child_to_move == -1) {
     1087      if (! child_to_move_is_processed) {
    10481088        grandparent.way_ = parent_is_down_child ?
    10491089          DBNodeSimple::WAY_DOWN_UP__NOTHING_DONE :
     
    10641104  const int GP_brvar = grandparent.variable_;
    10651105  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];
    10691107    parent.upper_[GP_brvar] = old_upper;
    10701108    model.setColUpper(which[GP_brvar], old_upper);
    10711109  } 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];
    10751111    parent.lower_[GP_brvar] = old_lower;
    10761112    model.setColLower(which[GP_brvar], old_lower);
    10771113  }
     1114#if 0
    10781115  // THINK: this might not be necessary
    10791116  model.resolve();
     1117#endif
    10801118
    10811119  // Now add the branching var bound change of P to GP and all of its
     
    10991137                           false /*lower bd*/, P_brvar, new_bd);
    11001138  }
     1139#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
     1140  if (childWasInfeasible) {
     1141    model.resolve();
     1142    assert(model.isProvenPrimalInfeasible());
     1143  }
     1144#endif
    11011145}
    11021146
     
    11821226    // while until nothing on stack
    11831227    while (branchingTree.size()) {
    1184 #if defined(DEBUG_DYNAMIC_BRANCHING)
     1228#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
    11851229      printf("branchingTree.size = %d %d\n",branchingTree.size(),branchingTree.size_);
    11861230      printf("i node_id parent child_down child_up\n");
     
    11951239      int kNode = branchingTree.chosen_;
    11961240      branchingTree.pop_back();
    1197 #if defined(DEBUG_DYNAMIC_BRANCHING)
     1241#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
    11981242      printf("Deleted current parent %d %d\n",branchingTree.size(),branchingTree.size_);
    11991243#endif
     
    12241268        model.setWarmStart(node.basis_);
    12251269        // 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();
    12471271        if (down_branch) {
    12481272          model.setColUpper(which[node.variable_],floor(node.value_));
     
    12531277        // to be done. We want the whole tree all the time.
    12541278        branchingTree.push_back(node);
    1255 #if defined(DEBUG_DYNAMIC_BRANCHING)
     1279#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
    12561280      printf("Added current parent %d %d\n",branchingTree.size(),branchingTree.size_);
    12571281#endif
     
    13071331        }
    13081332
    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) {
    13171342          for(int k=0; k<branchingTree.size_; k++) {
    13181343            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;
    13211348          }
     1349        }
    13221350#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', pos-1);
     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', pos-1);
     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
    13241397        if ((numberNodes%1000)==0)
    13251398          printf("%d nodes, tree size %d\n",
     
    13421415          // push on stack
    13431416          branchingTree.push_back(newNode);
    1344 #if defined(DEBUG_DYNAMIC_BRANCHING)
    1345       printf("Added current child %d %d\n",branchingTree.size(),branchingTree.size_);
     1417#if defined(DEBUG_DYNAMIC_BRANCHING) && DEBUG_DYNAMIC_BRANCHING >= 1000
     1418          printf("Added current child %d %d\n",branchingTree.size(),branchingTree.size_);
    13461419#endif
    1347           if(branchingTree.nodes_[kNode].way_ & DBNodeSimple::WAY_DOWN_CURRENT)
     1420          if (branchingTree.nodes_[kNode].workingOnDownChild()) {
    13481421            branchingTree.nodes_[kNode].child_down_ = branchingTree.last_;
    1349           else
     1422          } else {
    13501423            branchingTree.nodes_[kNode].child_up_ = branchingTree.last_;
     1424          }
    13511425          if (newNode.variable_>=0) {
    13521426            assert (fabs(newNode.value_-floor(newNode.value_+0.5))>1.0e-6);
Note: See TracChangeset for help on using the changeset viewer.