Changeset 1232


Ignore:
Timestamp:
Sep 15, 2009 11:52:18 AM (11 years ago)
Author:
forrest
Message:

try and improve branching

Location:
trunk/Cbc/src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcBranchActual.cpp

    r1224 r1232  
    45374537      info->integerTolerance_=model_->getIntegerTolerance();
    45384538      info->integerIncrement_=model_->getCutoffIncrement();
     4539      info->numberBeforeTrust_ = model_->numberBeforeTrust();
     4540      info->stateOfSearch_=model_->stateOfSearch();
     4541      // Compute "small" change in branch
     4542      int nBranches = model_->getIntParam(CbcModel::CbcNumberBranches);
     4543      if (nBranches) {
     4544        double average = model_->getDblParam(CbcModel::CbcSumChange)/static_cast<double>(nBranches);
     4545        info->smallChange_ =
     4546          CoinMax(average*1.0e-5,model_->getDblParam(CbcModel::CbcSmallestChange));
     4547        info->smallChange_ = CoinMax(info->smallChange_,1.0e-8);
     4548      } else {
     4549        info->smallChange_ = 1.0e-8;
     4550      }
    45394551      int numberIntegers = model_->numberIntegers();
    45404552      double * down = new double[numberIntegers];
  • trunk/Cbc/src/CbcBranchDynamic.cpp

    r1224 r1232  
    617617#endif
    618618#endif
    619 #if MOD_SHADOW==0
     619#define MOD_SHADOW 1
     620#if MOD_SHADOW>0
    620621  if (!downShadowPrice_) {
    621622    if (number>0.0)
     
    657658#endif
    658659#endif
    659 #if MOD_SHADOW==0
     660#if MOD_SHADOW>0
    660661  if (!upShadowPrice_) {
    661662    if (number>0.0)
     
    701702#define WEIGHT_AFTER 0.8
    702703#define WEIGHT_BEFORE 0.1
    703   //Stolen from Constraint Integer Programming book
     704  //Stolen from Constraint Integer Programming book (with epsilon change)
    704705#define WEIGHT_PRODUCT
    705706  if (fabs(value-nearest)<=integerTolerance) {
     
    749750      returnValue = WEIGHT_AFTER*minValue + (1.0-WEIGHT_AFTER)*maxValue;
    750751#else
    751       returnValue = CoinMax(minValue,1.0e-8)*CoinMax(maxValue,1.0e-8);
     752      double minProductWeight = model_->getDblParam(CbcModel::CbcSmallChange);
     753      returnValue = CoinMax(minValue,minProductWeight)*CoinMax(maxValue,minProductWeight);
     754      //returnValue += minProductWeight*minValue;
    752755#endif
    753756    }
     
    911914#endif
    912915}
     916// Modify down pseudo cost in a slightly different way
     917void
     918CbcSimpleIntegerDynamicPseudoCost::updateDownDynamicPseudoCost(double value)
     919{
     920  sumDownCost_ += value;
     921  numberTimesDown_++;
     922  downDynamicPseudoCost_=sumDownCost_/static_cast<double>(numberTimesDown_);
     923}
    913924// Set up pseudo cost
    914925void
     
    929940  }
    930941#endif
     942}
     943// Modify up pseudo cost in a slightly different way
     944void
     945CbcSimpleIntegerDynamicPseudoCost::updateUpDynamicPseudoCost(double value)
     946{
     947  sumUpCost_ += value;
     948  numberTimesUp_++;
     949  upDynamicPseudoCost_=sumUpCost_/static_cast<double>(numberTimesUp_);
    931950}
    932951/* Pass in information on branch just done and create CbcObjectUpdateData instance.
     
    17511770    value = WEIGHT_AFTER*minValue + (1.0-WEIGHT_AFTER)*maxValue;
    17521771#else
    1753     value = CoinMax(minValue,1.0e-8)*CoinMax(maxValue,1.0e-8);
     1772    double minProductWeight = model->getDblParam(CbcModel::CbcSmallChange);
     1773    value = CoinMax(minValue,minProductWeight)*CoinMax(maxValue,minProductWeight);
     1774    //value += minProductWeight*minValue;
    17541775#endif
    17551776    double useValue = value;
  • trunk/Cbc/src/CbcBranchDynamic.hpp

    r1224 r1232  
    9090  /// Set down pseudo cost
    9191  void setDownDynamicPseudoCost(double value) ;
     92  /// Modify down pseudo cost in a slightly different way
     93  void updateDownDynamicPseudoCost(double value);
    9294
    9395  /// Up pseudo cost
     
    9698  /// Set up pseudo cost
    9799  void setUpDynamicPseudoCost(double value);
     100  /// Modify up pseudo cost in a slightly different way
     101  void updateUpDynamicPseudoCost(double value);
    98102
    99103  /// Down pseudo shadow price cost
  • trunk/Cbc/src/CbcHeuristicFPump.cpp

    r1224 r1232  
    17761776            }
    17771777            newSolver->setColSolution(newSolution);
    1778 #define CLP_INVESTIGATE2
     1778            //#define CLP_INVESTIGATE2
    17791779#ifdef CLP_INVESTIGATE2
    17801780            {
  • trunk/Cbc/src/CbcModel.cpp

    r1230 r1232  
    11191119*/
    11201120  dblParam_[CbcStartSeconds] = CoinCpuTime();
     1121  dblParam_[CbcSmallestChange]=COIN_DBL_MAX;
     1122  dblParam_[CbcSumChange]=0.0;
     1123  dblParam_[CbcLargestChange]=0.0;
     1124  intParam_[CbcNumberBranches] = 0;
    11211125  strongInfo_[0]=0;
    11221126  strongInfo_[1]=0;
     
    35243528          << CoinMessageEol ;
    35253529      }
    3526       if (!eventHandler->event(CbcEventHandler::treeStatus)) {
     3530      if (eventHandler&&!eventHandler->event(CbcEventHandler::treeStatus)) {
    35273531        eventHappened_=true; // exit
    35283532      }
     
    44834487  intParam_[CbcMaxNumNode] = 2147483647;
    44844488  intParam_[CbcMaxNumSol] = 9999999;
    4485   intParam_[CbcFathomDiscipline] = 0;
    4486 
     4489
     4490  memset(dblParam_,0,sizeof(dblParam_));
    44874491  dblParam_[CbcIntegerTolerance] = 1e-6;
    4488   dblParam_[CbcInfeasibilityWeight] = 0.0;
    44894492  dblParam_[CbcCutoffIncrement] = 1e-5;
    44904493  dblParam_[CbcAllowableGap] = 1.0e-10;
    4491   dblParam_[CbcAllowableFractionGap] = 0.0;
    4492   dblParam_[CbcHeuristicGap] = 0.0;
    4493   dblParam_[CbcHeuristicFractionGap] = 0.0;
    44944494  dblParam_[CbcMaximumSeconds] = 1.0e100;
    44954495  dblParam_[CbcCurrentCutoff] = 1.0e100;
     
    44974497  dblParam_[CbcCurrentObjectiveValue] = 1.0e100;
    44984498  dblParam_[CbcCurrentMinimizationObjectiveValue] = 1.0e100;
    4499   dblParam_[CbcStartSeconds] = 0.0;
    45004499  strongInfo_[0]=0;
    45014500  strongInfo_[1]=0;
     
    45254524  handler_->setLogLevel(2);
    45264525  messages_ = CbcMessage();
    4527   eventHandler_ = new CbcEventHandler() ;
     4526  //eventHandler_ = new CbcEventHandler() ;
    45284527}
    45294528
     
    46454644  intParam_[CbcMaxNumNode] = 2147483647;
    46464645  intParam_[CbcMaxNumSol] = 9999999;
    4647   intParam_[CbcFathomDiscipline] = 0;
    4648 
     4646
     4647  memset(dblParam_,0,sizeof(dblParam_));
    46494648  dblParam_[CbcIntegerTolerance] = 1e-6;
    4650   dblParam_[CbcInfeasibilityWeight] = 0.0;
    46514649  dblParam_[CbcCutoffIncrement] = 1e-5;
    46524650  dblParam_[CbcAllowableGap] = 1.0e-10;
    4653   dblParam_[CbcAllowableFractionGap] = 0.0;
    4654   dblParam_[CbcHeuristicGap] = 0.0;
    4655   dblParam_[CbcHeuristicFractionGap] = 0.0;
    46564651  dblParam_[CbcMaximumSeconds] = 1.0e100;
    46574652  dblParam_[CbcCurrentCutoff] = 1.0e100;
     
    46594654  dblParam_[CbcCurrentObjectiveValue] = 1.0e100;
    46604655  dblParam_[CbcCurrentMinimizationObjectiveValue] = 1.0e100;
    4661   dblParam_[CbcStartSeconds] = 0.0;
    46624656  strongInfo_[0]=0;
    46634657  strongInfo_[1]=0;
     
    46794673  handler_->setLogLevel(2);
    46804674  messages_ = CbcMessage();
    4681   eventHandler_ = new CbcEventHandler() ;
     4675  //eventHandler_ = new CbcEventHandler() ;
    46824676  solver_ = rhs.clone();
    46834677  referenceSolver_ = solver_->clone();
     
    67506744    return (false) ;
    67516745  }
     6746  double change = lastObjective-objectiveValue;
     6747  if (change>1.0e-10) {
     6748    dblParam_[CbcSmallestChange]=CoinMin(dblParam_[CbcSmallestChange],change);
     6749    dblParam_[CbcSumChange] += change;
     6750    dblParam_[CbcLargestChange]=CoinMax(dblParam_[CbcLargestChange],change);
     6751    intParam_[CbcNumberBranches]++;
     6752  }
    67526753  sumChangeObjective1_ += solver_->getObjValue()*solver_->getObjSense()
    67536754    - objectiveValue ;
     
    94249425        if (obj1) {
    94259426          assert (obj1->downShadowPrice()>0.0);
    9426 #if 0
    9427           obj1->setDownShadowPrice(-1.0e-1*obj1->downShadowPrice());
    9428           obj1->setUpShadowPrice(-1.0e-1*obj1->upShadowPrice());
     9427#define P_FACTOR 1.0
     9428#if 1
     9429          obj1->setDownShadowPrice(-P_FACTOR*obj1->downShadowPrice());
     9430          obj1->setUpShadowPrice(-P_FACTOR*obj1->upShadowPrice());
    94299431#else
    9430           obj1->incrementNumberTimesDown();
    9431           obj1->setDownDynamicPseudoCost(1.0e1*obj1->downShadowPrice());
     9432          double pCost;
     9433          double sCost;
     9434          pCost = obj1->downDynamicPseudoCost();
     9435          sCost = P_FACTOR*obj1->downShadowPrice();
     9436          if (!obj1->numberTimesDown()||sCost>pCost)
     9437            obj1->updateDownDynamicPseudoCost(sCost);
    94329438          obj1->setDownShadowPrice(0.0);
    9433           obj1->incrementNumberTimesUp();
    9434           obj1->setUpDynamicPseudoCost(1.0e1*obj1->upShadowPrice());
     9439          pCost = obj1->upDynamicPseudoCost();
     9440          sCost = P_FACTOR*obj1->upShadowPrice();
     9441          if (!obj1->numberTimesUp()||sCost>pCost)
     9442            obj1->updateUpDynamicPseudoCost(sCost);
    94359443          obj1->setUpShadowPrice(0.0);
    94369444#endif
     
    97089716    double smallDown = 0.0001*(downSum/static_cast<double> (numberIntegers));
    97099717    double smallUp = 0.0001*(upSum/static_cast<double> (numberIntegers));
     9718#define PSEUDO_FACTOR 1.0e-1
    97109719    for (int i=0;i<numberObjects_;i++) {
    97119720      CbcSimpleIntegerDynamicPseudoCost * obj1 =
     
    97159724        double upPseudoCost = obj1->upDynamicPseudoCost();
    97169725        double saveUp = upPseudoCost;
    9717         upPseudoCost = CoinMax(upPseudoCost,smallUp);
     9726        upPseudoCost = CoinMax(PSEUDO_FACTOR*upPseudoCost,smallUp);
    97189727        upPseudoCost = CoinMax(upPseudoCost,up[iColumn]);
    97199728        upPseudoCost = CoinMax(upPseudoCost,0.001*down[iColumn]);
     
    97249733        double downPseudoCost = obj1->downDynamicPseudoCost();
    97259734        double saveDown = downPseudoCost;
    9726         downPseudoCost = CoinMax(downPseudoCost,smallDown);
     9735        downPseudoCost = CoinMax(PSEUDO_FACTOR*downPseudoCost,smallDown);
    97279736        downPseudoCost = CoinMax(downPseudoCost,down[iColumn]);
    97289737        downPseudoCost = CoinMax(downPseudoCost,0.001*up[iColumn]);
     
    1217212181  bool feasible=true;
    1217312182  int branchingState=-1;
     12183  // Compute "small" change in branch
     12184  int nBranches = intParam_[CbcNumberBranches];
     12185  if (nBranches) {
     12186    double average = dblParam_[CbcSumChange]/static_cast<double>(nBranches);
     12187    dblParam_[CbcSmallChange] =
     12188      CoinMax(average*1.0e-5,dblParam_[CbcSmallestChange]);
     12189    dblParam_[CbcSmallChange] = CoinMax(dblParam_[CbcSmallChange],1.0e-8);
     12190  } else {
     12191    dblParam_[CbcSmallChange] = 1.0e-8;
     12192  }
    1217412193#if 0
    1217512194  // Say not on optimal path
     
    1325013269            info->integerTolerance_=getIntegerTolerance();
    1325113270            info->integerIncrement_=getCutoffIncrement();
     13271            info->numberBeforeTrust_ = numberBeforeTrust_;
     13272            info->stateOfSearch_=1;
     13273            if (numberSolutions_>0) {
     13274              info->stateOfSearch_ = 3;
     13275            } if (numberNodes_>2*numberObjects_+1000) {
     13276              info->stateOfSearch_=4;
     13277            }
     13278  // Compute "small" change in branch
     13279            int nBranches = intParam_[CbcNumberBranches];
     13280            if (nBranches) {
     13281              double average = dblParam_[CbcSumChange]/static_cast<double>(nBranches);
     13282              info->smallChange_ =
     13283                CoinMax(average*1.0e-5,dblParam_[CbcSmallestChange]);
     13284              info->smallChange_ = CoinMax(info->smallChange_,1.0e-8);
     13285            } else {
     13286              info->smallChange_ = 1.0e-8;
     13287            }
    1325213288            double * down = new double[numberIntegers_];
    1325313289            double * up = new double[numberIntegers_];
     
    1377113807      deleted, and newNode is null.
    1377213808    */
    13773     if (!getEventHandler()->event(CbcEventHandler::node)) {
     13809    if (eventHandler_&&!eventHandler_->event(CbcEventHandler::node)) {
    1377413810      eventHappened_=true; // exit
    1377513811    }
     
    1486714903  for (i=0;i<numberIntegers_;i++)
    1486814904    back[integerVariable_[i]]=i;
     14905#ifdef CLP_INVESTIGATE
     14906  int numberNot=0;
     14907#endif
    1486914908  for ( i=0;i<numberObjects_;i++) {
    1487014909    CbcSimpleIntegerDynamicPseudoCost * obj =
     
    1487214911    if (!obj)
    1487314912      continue;
     14913#ifdef CLP_INVESTIGATE
     14914    if (obj->numberTimesDown()<numberBeforeTrust_||
     14915        obj->numberTimesUp()<numberBeforeTrust_)
     14916      numberNot++;
     14917#endif
    1487414918    int iColumn = obj->columnNumber();
    1487514919    iColumn = back[iColumn];
     
    1488814932    }
    1488914933  }
     14934#ifdef CLP_INVESTIGATE
     14935  printf("Before fathom %d not trusted out of %d\n",
     14936         numberNot,numberIntegers_);
     14937#endif
    1489014938  delete [] back;
    1489114939}
  • trunk/Cbc/src/CbcModel.hpp

    r1230 r1232  
    115115  */
    116116  CbcPrinting,
     117  /** Number of branches (may be more than number of nodes as may
     118      include strong branching) */
     119  CbcNumberBranches,
    117120  /** Just a marker, so that a static sized array can store parameters. */
    118121  CbcLastIntParam
     
    173176  */
    174177  CbcHeuristicFractionGap,
     178  /// Smallest non-zero change on a branch
     179  CbcSmallestChange,
     180  /// Sum of non-zero changes on a branch
     181  CbcSumChange,
     182  /// Largest non-zero change on a branch
     183  CbcLargestChange,
     184  /// Small non-zero change on a branch to be used as guess
     185  CbcSmallChange,
    175186  /** Just a marker, so that a static sized array can store parameters. */
    176187  CbcLastDblParam
  • trunk/Cbc/src/CbcSolver.cpp

    r1230 r1232  
    20012001      printf("movement %s was %g costing %g\n",
    20022002             (way==-1) ? "down" : "up",movement,moveObj);
    2003       if (way==-1&&(moveObj>=(1.0-movement)*objective[iSmallest]||lpSolver->status())) {
     2003      if (way==-1&&(moveObj>=maxCostUp||lpSolver->status())) {
    20042004        // go up
    20052005        columnLower = models[kPass].columnLower();
     
    35633563      diveOptions=diveOptions2%100;
    35643564      diveOptions2 -= diveOptions;
    3565       diveOptions2 += 100; // so 0 will be marked
    35663565    } else {
    35673566      diveOptions=diveOptions2;
  • trunk/Cbc/src/unitTestClp.cpp

    r1225 r1232  
    222222  int numberFailures=0;
    223223  int numberAttempts=0;
     224  int numberPossibleAttempts=0;
     225  for (m = 0 ; m < mpsName.size() ; m++) {
     226    int test = testSet[m];
     227    if(testSwitch>=test&&loSwitch<=test)
     228      numberPossibleAttempts++;
     229  }
    224230 
    225231  /*
     
    231237      numberAttempts++;
    232238      std::cout << "  processing mps file: " << mpsName[m]
    233                 << " (" << m+1 << " out of " << mpsName.size() << ")\n";
     239                << " (" << numberAttempts << " out of "
     240                << numberPossibleAttempts << ")\n";
    234241      /*
    235242        Stage 1: Read the MPS
Note: See TracChangeset for help on using the changeset viewer.