Changeset 974 for branches


Ignore:
Timestamp:
Jun 10, 2008 5:43:09 PM (11 years ago)
Author:
ladanyi
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/dynamicbranching/dynamicbranching.cpp

    r973 r974  
     1/**********************************************************************
     2TODO:
     3
     4If we swap two nodes (parent and grandparent) then we should check if anything
     5has been explored under GP after the swap, and if not, just get rid of GP and
     6everything below.
     7
     8If strong branching fixed anything in the grandparent we may still swap it
     9with the parent (we don't do it yet, see the test on
     10strong_branching_fixed_vars_), but those fixings must be moved to the parent as
     11well.
     12
     13Same thing for locally valid cuts, if GP has them and GP is switched with P
     14then locally valid cuts must be treated as generated in P.
     15
     16Same for reduced cost fixing :-(. If P has done any then P and GP can't be
     17switched.
     18
     19Maybe the best solution is to create local information (strong branching, rc
     20fixing, local cuts, etc.) only every so often, say every 10th level. Then that
     21would block switches, but everywhere else we would be safe. Good question
     22what is worth more: the switches or the local info.
     23
     24Alternative solution: Do not add local info to the tree, but keep it in a set
     25of excluded clauses ala Todias Achterberg: Conflict Analysis in Mixed Integer
     26Programming.
     27
     28We may want to disable fixing by strong branching completely and if such
     29situation occurs then simply do the branch and one side will be fathomed
     30immediately and we can try to switch.
     31
     32Bound modifications when nodes are swapped could be avoided if always start
     33from original bounds and go back to root to apply all branching decisions. On
     34the other hand, reduced cost fixing would be lost. And so would fixings by
     35strong branching. Although both could be stored in an array keeping track of
     36changes implied by the branching decisions.
     37
     38**********************************************************************
     39
     40
     41**********************************************************************/
    142#include "CoinTime.hpp"
    243#include "OsiClpSolverInterface.hpp"
     
    647#include <vector>
    748#include <map>
     49
     50class DBVectorNode;
    851
    952// Trivial class for Branch and Bound
     
    3376  // Also chooses branching variable (if none set to -1)
    3477  DBNodeSimple (OsiSolverInterface &model,
    35                  int numberIntegers, int * integer,
    36                  CoinWarmStart * basis);
     78                int numberIntegers, int * integer,
     79                CoinWarmStart * basis);
    3780  void gutsOfConstructor (OsiSolverInterface &model,
    38                  int numberIntegers, int * integer,
    39                  CoinWarmStart * basis);
     81                          int numberIntegers, int * integer,
     82                          CoinWarmStart * basis);
    4083  // Copy constructor
    4184  DBNodeSimple ( const DBNodeSimple &);
     
    5497  inline void incrementDescendants()
    5598  { descendants_++;}
     99  // Tests if we can switch this node (this is the parent) with its parent
     100  bool canSwitchParentWithGrandparent(const int* which,
     101                                      OsiSolverInterface & model,
     102                                      const int * original_lower,
     103                                      const int * original_upper,
     104                                      DBVectorNode & branchingTree);
     105
    56106  // Public data
     107  // The id of the node
     108  int node_id_;
    57109  // Basis (should use tree, but not as wasteful as bounds!)
    58110  CoinWarmStart * basis_;
     
    75127  // Right child
    76128  int child_up_;
     129  // Whether strong branching fixed variables when we branched on this node
     130  bool strong_branching_fixed_vars_;
     131  // Whether reduced cost fixing fixed anything in this node
     132  bool reduced_cost_fixed_vars_;
    77133  // Previous in chain
    78134  int previous_;
     
    87143
    88144DBNodeSimple::DBNodeSimple() :
     145  node_id_(-1),
    89146  basis_(NULL),
    90147  objectiveValue_(COIN_DBL_MAX),
     
    97154  child_down_(-1),
    98155  child_up_(-1),
     156  strong_branching_fixed_vars_(false),
     157  reduced_cost_fixed_vars_(false),
    99158  previous_(-1),
    100159  next_(-1),
     
    104163}
    105164DBNodeSimple::DBNodeSimple(OsiSolverInterface & model,
    106                 int numberIntegers, int * integer,CoinWarmStart * basis)
     165                          int numberIntegers, int * integer,CoinWarmStart * basis)
    107166{
    108167  gutsOfConstructor(model,numberIntegers,integer,basis);
     
    110169void
    111170DBNodeSimple::gutsOfConstructor(OsiSolverInterface & model,
    112                  int numberIntegers, int * integer,CoinWarmStart * basis)
    113 {
     171                                int numberIntegers, int * integer,CoinWarmStart * basis)
     172{
     173  node_id_ = -1;
    114174  basis_ = basis;
    115175  variable_=-1;
     
    121181  child_down_ = -1;
    122182  child_up_ = -1;
     183  strong_branching_fixed_vars_ = false;
     184  reduced_cost_fixed_vars_ = false;
    123185  previous_ = -1;
    124186  next_ = -1;
     
    371433DBNodeSimple::DBNodeSimple(const DBNodeSimple & rhs)
    372434{
     435  node_id_=rhs.node_id_;
    373436  if (rhs.basis_)
    374437    basis_=rhs.basis_->clone();
     
    384447  child_down_ = rhs.child_down_;
    385448  child_up_ = rhs.child_up_;
     449  strong_branching_fixed_vars_ = rhs.strong_branching_fixed_vars_;
     450  reduced_cost_fixed_vars_ = rhs.reduced_cost_fixed_vars_;
    386451  previous_ = rhs.previous_;
    387452  next_ = rhs.next_;
     
    402467  if (this != &rhs) {
    403468    gutsOfDestructor();
     469    node_id_=rhs.node_id_;
    404470    if (rhs.basis_)
    405471      basis_=rhs.basis_->clone();
     
    413479    child_down_ = rhs.child_down_;
    414480    child_up_ = rhs.child_up_;
     481    strong_branching_fixed_vars_ = rhs.strong_branching_fixed_vars_;
     482    reduced_cost_fixed_vars_ = rhs.reduced_cost_fixed_vars_;
    415483    previous_ = rhs.previous_;
    416484    next_ = rhs.next_;
     
    446514bool
    447515DBNodeSimple::extension(const DBNodeSimple & other,
    448                          const double * originalLower,
    449                          const double * originalUpper) const
     516                        const double * originalLower,
     517                        const double * originalUpper) const
    450518{
    451519  bool ok=true;
     
    465533#include <vector>
    466534#define FUNNY_BRANCHING 1
    467 #define FUNNY_TREE
    468 #ifndef FUNNY_TREE
    469 // Vector of DBNodeSimples
    470 typedef std::vector<DBNodeSimple>    DBVectorNode;
    471 #else
     535
    472536// Must code up by hand
    473537class DBVectorNode  {
     
    490554  { return size_-sizeDeferred_;}
    491555  // Push
    492   void push_back(const DBNodeSimple & node);
     556  void push_back(DBNodeSimple & node); // the node_id_ of node will change
    493557  // Last one in (or other criterion)
    494558  DBNodeSimple back() const;
     
    497561  // Works out best one
    498562  int best() const;
    499  
     563  // Rearranges the tree
     564  void moveNodeUp(const int* which,
     565                  OsiSolverInterface& model, DBNodeSimple & node);
     566  // It changes the bounds of the descendants of node with node_id
     567  void changeDescendantBounds(const int node_id, const bool lower_bd,
     568                              const int brvar, const int new_bd);
     569
    500570  // Public data
    501571  // Maximum size
     
    573643// Push
    574644void
    575 DBVectorNode::push_back(const DBNodeSimple & node)
     645DBVectorNode::push_back(DBNodeSimple & node)
    576646{
    577647  if (size_==maximumSize_) {
     
    597667  int next = nodes_[firstSpare_].next_;
    598668  nodes_[firstSpare_]=node;
     669  nodes_[firstSpare_].node_id_ = firstSpare_;
    599670  if (last_>=0) {
    600671    assert (nodes_[last_].next_==-1);
     
    677748  size_--;
    678749}
    679 #endif
     750
     751static double
     752compute_val_for_ray(const OsiSolverInterface& model)
     753{
     754  const std::vector<double*> dual_rays = model.getDualRays(1);
     755  if (dual_rays.size() == 0) {
     756    printf("WARNING: LP is infeas, but no dual ray is returned!\n");
     757    return 0;
     758  }
     759  const double* dual_ray = dual_rays[0];
     760  const double direction = model.getObjSense();
     761  const double* rub = model.getRowUpper();
     762  const double* rlb = model.getRowLower();
     763  const double* cub = model.getColUpper();
     764  const double* clb = model.getColLower();
     765  const double* dj  = model.getReducedCost();
     766  const double* obj = model.getObjCoefficients();
     767  const int numRows = model.getNumRows();
     768  const int numCols = model.getNumCols();
     769  double yb_plus_rl_minus_su = 0;
     770  for (int i = 0; i < numRows; ++i) {
     771    const double ray_i = dual_ray[i];
     772    if (ray_i > 1e-6) {
     773      yb_plus_rl_minus_su += ray_i*rlb[i];
     774    } else if (ray_i < 1e-6) {
     775      yb_plus_rl_minus_su += ray_i*rub[i];
     776    }
     777  }
     778  for (int j = 0; j < numCols; ++j) {
     779    const double yA_j = dj[j] - obj[j];
     780    if (direction * yA_j > 1e-6) {
     781      yb_plus_rl_minus_su -= yA_j*cub[j];
     782    } else if (direction * yA_j < -1e-6) {
     783      yb_plus_rl_minus_su -= yA_j*clb[j];
     784    }
     785  }
     786  for (int i = dual_rays.size()-1; i >= 0; --i) {
     787    delete[] dual_rays[i];
     788  }
     789  return yb_plus_rl_minus_su;
     790}
    680791
    681792bool
    682 DBNodeSimple::isGrandparentIrrelevant()
    683 {
     793DBNodeSimple::canSwitchParentWithGrandparent(const int* which,
     794                                             OsiSolverInterface & model,
     795                                             const int * original_lower,
     796                                             const int * original_upper,
     797                                             DBVectorNode & branchingTree)
     798{
     799  /*
     800    The current node ('this') is really the parent (P) and the solution in the
     801    model represents the child. The grandparent (GP) is this.parent_. Let's have
     802    variable names respecting the truth.
     803  */
    684804#if !defined(FUNNY_BRANCHING)
    685805  return false;
    686806#endif
    687807
    688   if (parent_ == -1) {
     808  const int parent_id = node_id_;
     809  const DBNodeSimple& parent = branchingTree.nodes_[parent_id];
     810  const int grandparent_id = parent.parent_;
     811
     812  if (grandparent_id == -1) {
    689813    // can't flip root higher up...
    690814    return false;
    691815  }
     816  const DBNodeSimple& grandparent = branchingTree.nodes_[grandparent_id];
    692817 
    693818  if (model.isProvenDualInfeasible()) {
     
    695820    return false;
    696821  }
     822
     823  if (parent.strong_branching_fixed_vars_ || parent.reduced_cost_fixed_vars_ ||
     824      grandparent.strong_branching_fixed_vars_) {
     825    return false;
     826  }
     827 
     828  const double direction = model.getObjSense();
     829
     830  const int GP_brvar = grandparent.variable_;
     831  const int GP_brvar_fullid = which[GP_brvar];
     832  const bool parent_is_down_child = parent_id == grandparent.child_down_;
     833
    697834  if (model.isProvenPrimalInfeasible()) {
    698     ...;
     835    const int greatgrandparent_id = grandparent.parent_;
     836    const int x = GP_brvar_fullid; // for easier reference... we'll use s_x
     837
     838    /*
     839      Now we are going to check that if we relax the GP's branching decision
     840      then the child's LP relaxation is still infeasible. The test is done by
     841      checking whether the column (or its negative) of the GP's branching
     842      variable cuts off the dual ray proving the infeasibility.
     843    */
     844   
     845    const double* dj = model.getReducedCost();
     846    const double* obj = model.getObjCoefficients();
     847    const double yA_x = dj[x] - obj[x];
     848    bool canSwitch = true;
     849
     850    if (direction > 0) { // minimization problem
     851      if (parent_is_down_child) {
     852        const double s_x = CoinMax(yA_x, -1e-8);
     853        if (s_x > 1e-6) { // if 0 then canSwitch can stay true
     854          const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     855          if (yb_plus_rl_minus_su < 1e-8) {
     856            printf("WARNING: yb_plus_rl_minus_su is not positive!\n");
     857            canSwitch = false;
     858          } else {
     859            const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x];
     860            const double u_x_without_GP = greatgrandparent_id >= 0 ?
     861              branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] :
     862              original_upper[GP_brvar];
     863            canSwitch = max_u_x > u_x_without_GP - 1e-8;
     864          }
     865        }
     866      } else {
     867        const double r_x = CoinMax(yA_x, -1e-8);
     868        if (r_x > 1e-6) { // if 0 then canSwitch can stay true
     869          const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     870          if (yb_plus_rl_minus_su < 1e-8) {
     871            printf("WARNING: yb_plus_rl_minus_su is not positive!\n");
     872            canSwitch = false;
     873          } else {
     874            const double min_l_x = - yb_plus_rl_minus_su / r_x + model.getColLower()[x];
     875            const double l_x_without_GP = greatgrandparent_id >= 0 ?
     876              branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] :
     877              original_lower[GP_brvar];
     878            canSwitch = min_l_x < l_x_without_GP + 1e-8;
     879          }
     880        }
     881      }
     882    } else { // maximization problem
     883      if (parent_is_down_child) {
     884        const double s_x = CoinMin(yA_x, 1e-8);
     885        if (s_x < -1e-6) { // if 0 then canSwitch can stay true
     886          const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     887          if (yb_plus_rl_minus_su > -1e-8) {
     888            printf("WARNING: yb_plus_rl_minus_su is not negative!\n");
     889            canSwitch = false;
     890          } else {
     891            const double max_u_x = yb_plus_rl_minus_su / s_x + model.getColUpper()[x];
     892            const double u_x_without_GP = greatgrandparent_id >= 0 ?
     893              branchingTree.nodes_[greatgrandparent_id].upper_[GP_brvar] :
     894              original_upper[GP_brvar];
     895            canSwitch = max_u_x > u_x_without_GP - 1e-8;
     896          }
     897        }
     898      } else {
     899        const double r_x = CoinMin(yA_x, 1e-8);
     900        if (r_x > -1e-6) { // if 0 then canSwitch can stay true
     901          const double yb_plus_rl_minus_su = compute_val_for_ray(model);
     902          if (yb_plus_rl_minus_su > -1e-8) {
     903            printf("WARNING: yb_plus_rl_minus_su is not negative!\n");
     904            canSwitch = false;
     905          } else {
     906            const double min_l_x = - yb_plus_rl_minus_su / r_x + model.getColLower()[x];
     907            const double l_x_without_GP = greatgrandparent_id >= 0 ?
     908              branchingTree.nodes_[greatgrandparent_id].lower_[GP_brvar] :
     909              original_lower[GP_brvar];
     910            canSwitch = min_l_x < l_x_without_GP + 1e-8;
     911          }
     912        }
     913      }
     914    }
     915
     916    return canSwitch;
    699917  }
    700918  // Both primal and dual feasible, and in this case we don't care how we have
     
    702920  // etc.), we can just look at the reduced costs to figure out if the
    703921  // 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) {
     922  double djValue = model.getReducedCost()[GP_brvar_fullid]*direction;
     923  if (djValue > 1.0e-6) {
    709924    // wants to go down
    710     if (down_child) {
     925    if (parent_is_down_child) {
    711926      return true;
    712927    }
    713     const double up_lower = std::floor(parent.value_);
    714     if (model.getColLower()[iColumn] > up_lower) {
     928    if (model.getColLower()[GP_brvar_fullid] > std::ceil(grandparent.value_)) {
    715929      return true;
    716930    }
    717931    return false;
     932  } else if (djValue < -1.0e-6) {
     933    // wants to go up
     934    if (! parent_is_down_child) {
     935      return true;
     936    }
     937    if (model.getColUpper()[GP_brvar_fullid] < std::floor(grandparent.value_)) {
     938      return true;
     939    }
     940    return false;
     941  }
     942  return false;
     943}
     944
     945void
     946DBVectorNode::moveNodeUp(const int* which,
     947                         OsiSolverInterface& model, DBNodeSimple & node)
     948{
     949  /*
     950    The current node ('this') is really the parent (P) and the solution in the
     951    model represents the child. The grandparent (GP) is this.parent_. Let's have
     952    variable names respecting the truth.
     953  */
     954  const int parent_id = node.node_id_;
     955  DBNodeSimple& parent = nodes_[parent_id];
     956  const int grandparent_id = parent.parent_;
     957  assert(grandparent_id != -1);
     958  DBNodeSimple& grandparent = nodes_[grandparent_id];
     959  const int greatgrandparent_id = grandparent.parent_;
     960 
     961  const bool parent_is_down_child = parent_id == grandparent.child_down_;
     962
     963  // First hang the nodes where they belong.
     964  parent.parent_ = greatgrandparent_id;
     965  grandparent.parent_ = parent_id;
     966  const bool down_child_stays_with_parent = parent.way_ & DBNodeSimple::DOWN_CURRENT;
     967  int& child_to_move =
     968    down_child_stays_with_parent ? parent.child_up_ : parent.child_down_;
     969  if (parent_is_down_child) {
     970    grandparent.child_down_ = child_to_move;
    718971  } 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;
     972    grandparent.child_up_ = child_to_move;
     973  }
     974  if (child_to_move >= 0) {
     975    nodes_[child_to_move].parent_ = grandparent_id;
     976  }
     977  child_to_move = grandparent_id;
     978  if (greatgrandparent_id >= 0) {
     979    DBNodeSimple& greatgrandparent = nodes_[greatgrandparent_id];
     980    if (grandparent_id == greatgrandparent.child_down_) {
     981      greatgrandparent.child_down_ = parent_id;
     982    } else {
     983      greatgrandparent.child_up_ = parent_id;
     984    }
     985  }
     986
     987  // Now modify bounds
     988
     989  // First, get rid of GP's bound change of its branching variable in the
     990  // bound list of P. Note: If greatgrandparent_id is < 0 then GP is the root
     991  // so its bounds are the original bounds.
     992  const int GP_brvar = grandparent.variable_;
     993  if (parent_is_down_child) {
     994    const int old_upper = greatgrandparent_id >= 0 ?
     995      nodes_[greatgrandparent_id].upper_[GP_brvar] :
     996      grandparent.upper_[GP_brvar];
     997    parent.upper_[GP_brvar] = old_upper;
     998    model.setColUpper(which[GP_brvar], old_upper);
     999  } else {
     1000    const int old_lower = greatgrandparent_id >= 0 ?
     1001      nodes_[greatgrandparent_id].lower_[GP_brvar] :
     1002      grandparent.lower_[GP_brvar];
     1003    parent.lower_[GP_brvar] = old_lower;
     1004    model.setColLower(which[GP_brvar], old_lower);
     1005  }
     1006  // THINK: this might not be necessary
     1007  model.resolve();
     1008
     1009  // Now add the branching var bound change of P to GP and all of its
     1010  // descendant
     1011  const int P_brvar = parent.variable_;
     1012  const double P_value = parent.value_;
     1013  int new_bd;
     1014  if (down_child_stays_with_parent) {
     1015    // Former up child of P is now the down child of GP, so we need to change
     1016    // bounds of GP, its up child and descendants of that one.
     1017    new_bd = (int)std::ceil(P_value);
     1018    grandparent.lower_[P_brvar] = new_bd;
     1019    changeDescendantBounds(grandparent.child_up_,
     1020                           true /*lower bd*/, P_brvar, new_bd);
     1021  } else {
     1022    // Former down child of P is now the up child of GP, so we need to change
     1023    // bounds of GP, its down child and descendants of that one.
     1024    new_bd = (int)floor(P_value);
     1025    grandparent.upper_[P_brvar] = new_bd;
     1026    changeDescendantBounds(grandparent.child_down_,
     1027                           false /*lower bd*/, P_brvar, new_bd);
     1028  }
    7301029}
    7311030
    7321031void
    733 DBVectorNode::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;
     1032DBVectorNode::changeDescendantBounds(const int node_id, const bool lower_bd,
     1033                                     const int brvar, const int new_bd)
     1034{
     1035  if (node_id == -1) {
     1036    return;
     1037  }
     1038  changeDescendantBounds(nodes_[node_id].child_down_, lower_bd, brvar, new_bd);
     1039  changeDescendantBounds(nodes_[node_id].child_up_, lower_bd, brvar, new_bd);
     1040  if (lower_bd) {
     1041    nodes_[node_id].lower_[brvar] = new_bd;
    7491042  } 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 
    799 
    800 bool moveNodes(OsiSolverInterface & model,
    801                DBVectorNode & branchingTree,
    802                int kNode)
    803 {
    804 
    805   DBNodeSimple & node = branchingTree[kNode];
    806   DBNodeSimple & grandParent = branchingTree[node.parent_];
    807   int grandParentVariable = grandParent.variable_;
    808   // check if branching constraint of grandparent is tight
    809   bool canMoveNodes = checkGrandparent();
    810 
    811   if(!canMoveNodes)
    812     return false;
    813 
    814   node.parent_ = grandParent.parent_;
    815   grandParent.parent_ = kNode;
    816   // change bounds of grandParent
    817   grandParent.lower_[
    818 
    819 
    820 }
     1043    nodes_[node_id].upper_[brvar] = new_bd;
     1044  }
     1045}
     1046
    8211047
    8221048// Invoke solver's built-in enumeration algorithm
     
    8811107    int numberIterations=0;
    8821108    int numberNodes =0;
    883     int nRedundantUp=0;
    884     int nRedundantDown=0;
    885     int nRedundantUp2=0;
    886     int nRedundantDown2=0;
    8871109    DBNodeSimple bestNode;
    8881110    ////// Start main while of branch and bound
     
    9071129        bool down_branch = true;
    9081130        switch (node.way_) {
    909         case WAY_UNSET:
    910         case DOWN_UP__BOTH_DONE:
    911         case UP_DOWN__BOTH_DONE:
     1131        case DBNodeSimple::WAY_UNSET:
     1132        case DBNodeSimple::DOWN_UP__BOTH_DONE:
     1133        case DBNodeSimple::UP_DOWN__BOTH_DONE:
    9121134          abort();
    913         case DOWN_UP__NOTHING_DONE:
    914           node.way_ = DOWN_UP__DOWN_DONE;
     1135        case DBNodeSimple::DOWN_UP__NOTHING_DONE:
     1136          node.way_ = DBNodeSimple::DOWN_UP__DOWN_DONE;
    9151137          break;
    916         case DOWN_UP__DOWN_DONE:
    917           node.way_ = DOWN_UP__BOTH_DONE:
     1138        case DBNodeSimple::DOWN_UP__DOWN_DONE:
     1139          node.way_ = DBNodeSimple::DOWN_UP__BOTH_DONE;
    9181140          down_branch = false;
    9191141          break;
    920         case UP_DOWN__NOTHING_DONE:
    921           node.way_ = UP_DOWN__UP_DONE:
     1142        case DBNodeSimple::UP_DOWN__NOTHING_DONE:
     1143          node.way_ = DBNodeSimple::UP_DOWN__UP_DONE;
    9221144          down_branch = false;
    9231145          break;
    924         case UP_DOWN__UP_DONE:
    925           node.way_ = UP_DOWN__BOTH_DONE;
     1146        case DBNodeSimple::UP_DOWN__UP_DONE:
     1147          node.way_ = DBNodeSimple::UP_DOWN__BOTH_DONE;
    9261148          break;
    9271149        }
     
    9471169        model.getDblParam(OsiDualObjectiveLimit,cutoff);
    9481170        double gap=(cutoff-model.getObjValue())*direction+1.0e-4;
    949         //        double gap=(cutoff-modelPtr_->objectiveValue())*direction+1.0e-4;
     1171        //        double
     1172        //        gap=(cutoff-modelPtr_->objectiveValue())*direction+1.0e-4;
     1173        bool did_reduced_cost_fixing_for_child = false;
    9501174        if (gap<1.0e10&&model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) {
    9511175          const double * dj = model.getReducedCost();
     
    9671191            }
    9681192          }
    969           //if (nFixed0+nFixed1)
    970           //printf("%d fixed to lower, %d fixed to upper\n",nFixed0,nFixed1);
    971         }
    972         if (model.isAbandoned()) {
    973           // THINK: What the heck should we do???
    974           abort();
    975         }
    976         while (node.isGrandparentIrrelevant()) {
    977           branchingTree.moveNodeUp(node);
    978         }
    979 
    980 
    981 
    982 
    983         if (!model.isIterationLimitReached()) {
    984           if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) {
    985 #if FUNNY_BRANCHING
    986             // See if branched variable off bounds
    987             const double * dj = model.getReducedCost();
    988             const double * lower = model.getColLower();
    989             const double * upper = model.getColUpper();
    990             const double * solution = model.getColSolution();
    991             // Better to use "natural" value - need flag to say fixed
    992             for (i=0;i<numberIntegers;i++) {
    993               iColumn=which[i];
    994               relaxedLower[i]=originalLower[i];
    995               relaxedUpper[i]=originalUpper[i];
    996               double djValue = dj[iColumn]*direction;
    997               if (djValue>1.0e-6) {
    998                 // wants to go down
    999                 if (lower[iColumn]>originalLower[i]) {
    1000                   // Lower bound active
    1001                   relaxedLower[i]=(int) lower[iColumn];
    1002                 }
    1003                 if (upper[iColumn]<originalUpper[i]) {
    1004                   // Upper bound NOT active
    1005                 }
    1006               } else if (djValue<-1.0e-6) {
    1007                 // wants to go up
    1008                 if (lower[iColumn]>originalLower[i]) {
    1009                   // Lower bound NOT active
    1010                 }
    1011                 if (upper[iColumn]<originalUpper[i]) {
    1012                   // Upper bound active
    1013                   relaxedUpper[i]=(int) upper[iColumn];
    1014                 }
     1193          if (nFixed0+nFixed1) {
     1194            //      printf("%d fixed to lower, %d fixed to upper\n",
     1195            //             nFixed0,nFixed1);
     1196            did_reduced_cost_fixing_for_child = true;
     1197          }
     1198          if (model.isAbandoned()) {
     1199            // THINK: What the heck should we do???
     1200            abort();
     1201          }
     1202          while (node.canSwitchParentWithGrandparent(which, model,
     1203                                                     originalLower,
     1204                                                     originalUpper,
     1205                                                     branchingTree)) {
     1206            branchingTree.moveNodeUp(which, model, node);
     1207          }
     1208          if (!model.isIterationLimitReached()) {
     1209            if (model.isProvenOptimal()&&!model.isDualObjectiveLimitReached()) {
     1210              if ((numberNodes%1000)==0)
     1211                printf("%d nodes, tree size %d\n",
     1212                       numberNodes,branchingTree.size());
     1213              if (CoinCpuTime()-time1>3600.0) {
     1214                printf("stopping after 3600 seconds\n");
     1215                exit(77);
    10151216              }
    1016             }
    1017             // See if can do anything
    1018             {
    1019               /*
    1020                 If kNode is on second branch then
    1021                 a) If other feasible could free up as well
    1022                 b) If other infeasible could do something clever.
    1023                 For now - we have to give up
    1024               */
    1025               int jNode=branchingTree.nodes_[kNode].parent_;
    1026               bool canDelete = (branchingTree.nodes_[kNode].descendants_<2);
    1027               while (jNode>=0) {
    1028                 DBNodeSimple & node = branchingTree.nodes_[jNode];
    1029                 int next = node.parent_;
    1030                 if (node.descendants_<2) {
    1031                   int variable = node.variable_;
    1032                   iColumn=which[variable];
    1033                   double value = node.value_;
    1034                   double djValue = dj[iColumn]*direction;
    1035                   assert (node.way_==2||node.way_==-2);
    1036                   // we don't know which branch it was - look at current bounds
    1037                   if (upper[iColumn]<value&&node.lower_[variable]<upper[iColumn]) {
    1038                     // must have been down branch
    1039                     if (djValue>1.0e-3||solution[iColumn]<upper[iColumn]-1.0e-5) {
    1040                       if (canDelete) {
    1041                         nRedundantDown++;
    1042 #if 1
    1043                         printf("%d redundant branch down with value %g current upper %g solution %g dj %g\n",
    1044                                variable,node.value_,upper[iColumn],solution[iColumn],djValue);
    1045 #endif
    1046                         node.descendants_=2; // ignore
    1047                         branchingTree.sizeDeferred_++;
    1048                         int newUpper = originalUpper[variable];
    1049                         if (next>=0) {
    1050                           DBNodeSimple & node2 = branchingTree.nodes_[next];
    1051                           newUpper = node2.upper_[variable];
    1052                         }
    1053                         if (branchingTree.nodes_[jNode].parent_!=next)
    1054                           assert (newUpper>upper[iColumn]);
    1055                         model.setColUpper(iColumn,newUpper);
    1056                         int kNode2=next;
    1057                         int jNode2=branchingTree.nodes_[kNode].parent_;
    1058                         assert (newUpper>branchingTree.nodes_[kNode].upper_[variable]);
    1059                         branchingTree.nodes_[kNode].upper_[variable]= newUpper;
    1060                         while (jNode2!=kNode2) {
    1061                           DBNodeSimple & node2 = branchingTree.nodes_[jNode2];
    1062                           int next = node2.parent_;
    1063                           if (next!=kNode2)
    1064                             assert (newUpper>node2.upper_[variable]);
    1065                           node2.upper_[variable]= newUpper;
    1066                           jNode2=next;
    1067                         }
    1068                       } else {
    1069                         // can't delete but can add other way to jNode
    1070                         nRedundantDown2++;
    1071                         DBNodeSimple & node2 = branchingTree.nodes_[kNode];
    1072                         assert (node2.way_==2||node2.way_==-2);
    1073                         double value2 = node2.value_;
    1074                         int variable2 = node2.variable_;
    1075                         int iColumn2 = which[variable2];
    1076                         if (variable != variable2) {
    1077                           if (node2.way_==2&&upper[iColumn2]<value2) {
    1078                             // must have been down branch which was done - carry over
    1079                             int newUpper = (int) floor(value2);
    1080                             assert (newUpper<node.upper_[variable2]);
    1081                             node.upper_[variable2]=newUpper;
    1082                           } else if (node2.way_==-2&&lower[iColumn2]>value2) {
    1083                             // must have been up branch which was done - carry over
    1084                             int newLower = (int) ceil(value2);
    1085                             assert (newLower>node.lower_[variable2]);
    1086                             node.lower_[variable2]=newLower;
    1087                           }
    1088                           if (node.lower_[variable2]>node.upper_[variable2]) {
    1089                             // infeasible
    1090                             node.descendants_=2; // ignore
    1091                             branchingTree.sizeDeferred_++;
    1092                           }
    1093                         }
    1094                       }
    1095                       break;
    1096                     }           
    1097                     // we don't know which branch it was - look at current bounds
    1098                   } else if (lower[iColumn]>value&&node.upper_[variable]>lower[iColumn]) {
    1099                     // must have been up branch
    1100                     if (djValue<-1.0e-3||solution[iColumn]>lower[iColumn]+1.0e-5) {
    1101                       if (canDelete) {
    1102                         nRedundantUp++;
    1103 #if 1
    1104                         printf("%d redundant branch up with value %g current lower %g solution %g dj %g\n",
    1105                                variable,node.value_,lower[iColumn],solution[iColumn],djValue);
    1106 #endif
    1107                         node.descendants_=2; // ignore
    1108                         branchingTree.sizeDeferred_++;
    1109                         int newLower = originalLower[variable];
    1110                         if (next>=0) {
    1111                           DBNodeSimple & node2 = branchingTree.nodes_[next];
    1112                           newLower = node2.lower_[variable];
    1113                         }
    1114                         if (branchingTree.nodes_[jNode].parent_!=next)
    1115                           assert (newLower<lower[iColumn]);
    1116                         model.setColLower(iColumn,newLower);
    1117                         int kNode2=next;
    1118                         int jNode2=branchingTree.nodes_[kNode].parent_;
    1119                         assert (newLower<branchingTree.nodes_[kNode].lower_[variable]);
    1120                         branchingTree.nodes_[kNode].lower_[variable]= newLower;
    1121                         while (jNode2!=kNode2) {
    1122                           DBNodeSimple & node2 = branchingTree.nodes_[jNode2];
    1123                           int next = node2.parent_;
    1124                           if (next!=kNode2)
    1125                             assert (newLower<node2.lower_[variable]);
    1126                           node2.lower_[variable]=newLower;
    1127                           jNode2=next;
    1128                         }
    1129                       } else {
    1130                         // can't delete but can add other way to jNode
    1131                         nRedundantUp2++;
    1132                         DBNodeSimple & node2 = branchingTree.nodes_[kNode];
    1133                         assert (node2.way_==2||node2.way_==-2);
    1134                         double value2 = node2.value_;
    1135                         int variable2 = node2.variable_;
    1136                         int iColumn2 = which[variable2];
    1137                         if (variable != variable2) {
    1138                           if (node2.way_==2&&upper[iColumn2]<value2) {
    1139                             // must have been down branch which was done - carry over
    1140                             int newUpper = (int) floor(value2);
    1141                             assert (newUpper<node.upper_[variable2]);
    1142                             node.upper_[variable2]=newUpper;
    1143                           } else if (node2.way_==-2&&lower[iColumn2]>value2) {
    1144                             // must have been up branch which was done - carry over
    1145                             int newLower = (int) ceil(value2);
    1146                             assert (newLower>node.lower_[variable2]);
    1147                             node.lower_[variable2]=newLower;
    1148                           }
    1149                           if (node.lower_[variable2]>node.upper_[variable2]) {
    1150                             // infeasible
    1151                             node.descendants_=2; // ignore
    1152                             branchingTree.sizeDeferred_++;
    1153                           }
    1154                         }
    1155                       }
    1156                       break;
    1157                     }           
    1158                   }
    1159                 } else {
    1160                   break;
    1161                 }
    1162                 jNode=next;
     1217              DBNodeSimple newNode(model,numberIntegers,which,ws);
     1218              // something extra may have been fixed by strong branching
     1219              // if so go round again
     1220              while (newNode.variable_==numberIntegers) {
     1221                model.resolve();
     1222                newNode = DBNodeSimple(model,numberIntegers,which,model.getWarmStart());
     1223                newNode.strong_branching_fixed_vars_ = true;
    11631224              }
    1164             }
    1165             // solve
    1166             //resolve();
    1167             //assert(!getIterationCount());
    1168             if ((numberNodes%1000)==0)
    1169               printf("%d nodes, redundant down %d (%d) up %d (%d) tree size %d\n",
    1170                      numberNodes,nRedundantDown,nRedundantDown2,nRedundantUp,nRedundantUp2,branchingTree.size());
    1171 #else
    1172             if ((numberNodes%1000)==0)
    1173               printf("%d nodes, tree size %d\n",
    1174                      numberNodes,branchingTree.size());
    1175 #endif
    1176             if (CoinCpuTime()-time1>3600.0) {
    1177               printf("stopping after 3600 seconds\n");
    1178               exit(77);
    1179             }
    1180             DBNodeSimple newNode(model,numberIntegers,which,ws);
    1181             // something extra may have been fixed by strong branching
    1182             // if so go round again
    1183             while (newNode.variable_==numberIntegers) {
    1184               model.resolve();
    1185               newNode = DBNodeSimple(model,numberIntegers,which,model.getWarmStart());
    1186             }
    1187             if (newNode.objectiveValue_<1.0e100) {
    1188               if (newNode.variable_>=0)
    1189                 assert (fabs(newNode.value_-floor(newNode.value_+0.5))>1.0e-6);
    1190               newNode.parent_ = kNode;
    1191               // push on stack
    1192               branchingTree.push_back(newNode);
    1193               if(branchingTree.nodes_[kNode].child_down_ < 0)
    1194                 branchingTree.nodes_[kNode].child_down_ = branchingTree.last_;
    1195               else
    1196                 branchingTree.nodes_[kNode].child_up_ = branchingTree.last_;
     1225              newNode.reduced_cost_fixed_vars_ = did_reduced_cost_fixing_for_child;
     1226              if (newNode.objectiveValue_<1.0e100) {
     1227                if (newNode.variable_>=0)
     1228                  assert (fabs(newNode.value_-floor(newNode.value_+0.5))>1.0e-6);
     1229                newNode.parent_ = kNode;
     1230                // push on stack
     1231                branchingTree.push_back(newNode);
     1232                if(branchingTree.nodes_[kNode].child_down_ < 0)
     1233                  branchingTree.nodes_[kNode].child_down_ = branchingTree.last_;
     1234                else
     1235                  branchingTree.nodes_[kNode].child_up_ = branchingTree.last_;
    11971236#if 0
    11981237              } else {
     
    12051244                         <<" found after "<<numberIterations
    12061245                         <<" iterations and "<<numberNodes<<" nodes"
    1207                 <<std::endl;
     1246                        <<std::endl;
    12081247              }
    12091248#endif
Note: See TracChangeset for help on using the changeset viewer.