Changeset 135


Ignore:
Timestamp:
May 19, 2005 11:24:16 AM (14 years ago)
Author:
forrest
Message:

starting dynamic pseudo costs

Location:
trunk
Files:
2 added
14 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcBranchActual.cpp

    r129 r135  
    126126  const int * integer = model_->integerVariable();
    127127  OsiSolverInterface * solver = model_->solver();
    128   const double * solution = model_->currentSolution();
     128  const double * solution = model_->testSolution();
    129129  const double * lower = solver->getColLower();
    130130  const double * upper = solver->getColUpper();
     
    191191  const int * integer = model_->integerVariable();
    192192  OsiSolverInterface * solver = model_->solver();
    193   const double * solution = model_->currentSolution();
     193  const double * solution = model_->testSolution();
    194194  const double * lower = solver->getColLower();
    195195  const double * upper = solver->getColUpper();
     
    223223  const int * integer = model_->integerVariable();
    224224  OsiSolverInterface * solver = model_->solver();
    225   const double * solution = model_->currentSolution();
     225  const double * solution = model_->testSolution();
    226226  const double * lower = solver->getColLower();
    227227  const double * upper = solver->getColUpper();
     
    398398  int lastNonZero = -1;
    399399  OsiSolverInterface * solver = model_->solver();
    400   const double * solution = model_->currentSolution();
     400  const double * solution = model_->testSolution();
    401401  const double * lower = solver->getColLower();
    402402  const double * upper = solver->getColUpper();
     
    459459  int lastNonZero = -1;
    460460  OsiSolverInterface * solver = model_->solver();
    461   const double * solution = model_->currentSolution();
     461  const double * solution = model_->testSolution();
    462462  //const double * lower = solver->getColLower();
    463463  const double * upper = solver->getColUpper();
     
    495495{
    496496  int j;
    497   const double * solution = model_->currentSolution();
     497  const double * solution = model_->testSolution();
    498498  double integerTolerance =
    499499      model_->getDblParam(CbcModel::CbcIntegerTolerance);
     
    622622{
    623623  OsiSolverInterface * solver = model_->solver();
    624   const double * solution = model_->currentSolution();
     624  const double * solution = model_->testSolution();
    625625  const double * lower = solver->getColLower();
    626626  const double * upper = solver->getColUpper();
     
    660660  const double * lower = solver->getColLower();
    661661  const double * upper = solver->getColUpper();
    662   const double * solution = model_->currentSolution();
     662  const double * solution = model_->testSolution();
    663663  double value = solution[columnNumber_];
    664664  value = CoinMax(value, lower[columnNumber_]);
     
    689689{
    690690  OsiSolverInterface * solver = model_->solver();
    691   const double * solution = model_->currentSolution();
     691  const double * solution = model_->testSolution();
    692692  const double * lower = solver->getColLower();
    693693  const double * upper = solver->getColUpper();
     
    724724{
    725725  OsiSolverInterface * solver = model_->solver();
    726   double value = model_->currentSolution()[columnNumber_];
     726  double value = model_->testSolution()[columnNumber_];
    727727
    728728  double nearest = floor(value+0.5);
     
    759759{
    760760  OsiSolverInterface * solver = model_->solver();
    761   double value = model_->currentSolution()[columnNumber_];
     761  double value = model_->testSolution()[columnNumber_];
    762762
    763763  double nearest = floor(value+0.5);
     
    10131013{
    10141014  OsiSolverInterface * solver = model_->solver();
    1015   const double * solution = model_->currentSolution();
     1015  const double * solution = model_->testSolution();
    10161016  const double * lower = solver->getColLower();
    10171017  const double * upper = solver->getColUpper();
     
    10531053{
    10541054  OsiSolverInterface * solver = model_->solver();
    1055   const double * solution = model_->currentSolution();
     1055  const double * solution = model_->testSolution();
    10561056  const double * lower = solver->getColLower();
    10571057  const double * upper = solver->getColUpper();
     
    10981098{
    10991099  OsiSolverInterface * solver = model_->solver();
    1100   const double * solution = model_->currentSolution();
     1100  const double * solution = model_->testSolution();
    11011101  const double * lower = solver->getColLower();
    11021102  const double * upper = solver->getColUpper();
     
    11241124{
    11251125  OsiSolverInterface * solver = model_->solver();
    1126   const double * solution = model_->currentSolution();
     1126  const double * solution = model_->testSolution();
    11271127  const double * lower = solver->getColLower();
    11281128  const double * upper = solver->getColUpper();
  • trunk/CbcBranchCut.cpp

    r129 r135  
    376376  assert (way==-1);
    377377  OsiSolverInterface * solver = model_->solver();
    378   const double * solution = model_->currentSolution();
     378  const double * solution = model_->testSolution();
    379379  const double * lower = solver->getColLower();
    380380  const double * upper = solver->getColUpper();
     
    520520  //if (numberRows!=solver->getNumRows())
    521521  //return 0;
    522   const double * solution = model_->currentSolution();
     522  const double * solution = model_->testSolution();
    523523  const double * lower = solver->getColLower();
    524524  const double * upper = solver->getColUpper();
  • trunk/CbcBranchLotsize.cpp

    r129 r135  
    421421{
    422422  OsiSolverInterface * solver = model_->solver();
    423   const double * solution = model_->currentSolution();
     423  const double * solution = model_->testSolution();
    424424  const double * lower = solver->getColLower();
    425425  const double * upper = solver->getColUpper();
     
    486486  const double * lower = solver->getColLower();
    487487  const double * upper = solver->getColUpper();
    488   const double * solution = model_->currentSolution();
     488  const double * solution = model_->testSolution();
    489489  double value = solution[columnNumber_];
    490490  value = CoinMax(value, lower[columnNumber_]);
     
    523523{
    524524  OsiSolverInterface * solver = model_->solver();
    525   const double * solution = model_->currentSolution();
     525  const double * solution = model_->testSolution();
    526526  const double * lower = solver->getColLower();
    527527  const double * upper = solver->getColUpper();
     
    545545{
    546546  OsiSolverInterface * solver = model_->solver();
    547   double value = model_->currentSolution()[columnNumber_];
     547  double value = model_->testSolution()[columnNumber_];
    548548
    549549  bool feasible = findRange(value);
     
    593593{
    594594  OsiSolverInterface * solver = model_->solver();
    595   double value = model_->currentSolution()[columnNumber_];
     595  double value = model_->testSolution()[columnNumber_];
    596596
    597597  double nearest = floor(value+0.5);
  • trunk/CbcModel.cpp

    r132 r135  
    1717#include "CoinPackedMatrix.hpp"
    1818#include "CbcBranchActual.hpp"
     19#include "CbcBranchDynamic.hpp"
    1920#include "CbcHeuristic.hpp"
    2021#include "CbcModel.hpp"
     
    402403*/
    403404  findIntegers(false) ;
     405  // If dynamic pseudo costs then do
     406  if (numberBeforeTrust_>0)
     407    convertToDynamic();
     408
    404409/*
    405410  Ensure that objects on the lists of CbcObjects, heuristics, and cut
     
    433438  originalContinuousObjective_ = solver_->getObjValue();
    434439  bestPossibleObjective_=originalContinuousObjective_;
     440  sumChangeObjective1_=0.0;
     441  sumChangeObjective2_=0.0;
    435442/*
    436443  OsiRowCutDebugger knows an optimal answer for a subset of MIP problems.
     
    454461  bestObjective_ = CoinMin(bestObjective_,1.0e50) ;
    455462  numberSolutions_ = 0 ;
     463  stateOfSearch_=0;
    456464  numberHeuristicSolutions_ = 0 ;
    457465  // Everything is minimization
     
    471479  if (!currentSolution_)
    472480    currentSolution_ = new double[numberColumns] ;
     481  testSolution_ = currentSolution_;
    473482/*
    474483  Create a copy of the solver, thus capturing the original (root node)
     
    593602    while (anyAction == -1)
    594603    {
    595       anyAction = newNode->chooseBranch(this,NULL,numberPassesLeft) ;
     604      if (numberBeforeTrust_<=0 ) {
     605        anyAction = newNode->chooseBranch(this,NULL,numberPassesLeft) ;
     606      } else {
     607        anyAction = newNode->chooseDynamicBranch(this,NULL,numberPassesLeft) ;
     608        if (anyAction==-3)
     609          anyAction = newNode->chooseBranch(this,NULL,numberPassesLeft) ; // dynamic did nothing
     610      }
    596611      numberPassesLeft--;
    597612      if (anyAction == -1)
     
    758773      for (j = 0;j < nNodes;j++) {
    759774        CbcNode * node = tree_->nodePointer(j) ;
    760         if (node->objectiveValue() < bestPossibleObjective_)
     775        if (node&&node->objectiveValue() < bestPossibleObjective_)
    761776          bestPossibleObjective_ = node->objectiveValue() ;
    762777      }
     
    765780        << CoinMessageEol ;
    766781    }
     782    // If no solution but many nodes - signal change in strategy
     783    if (numberNodes_>2*numberObjects_+1000&&stateOfSearch_!=2)
     784      stateOfSearch_=3;
    767785    // See if can stop on gap
    768786    double testGap = CoinMax(dblParam_[CbcAllowableGap],
     
    786804  active subproblem.
    787805*/
    788     CbcNode *node = tree_->top() ;
     806    CbcNode *node = tree_->bestNode(cutoff) ;
     807    // Possible one on tree worse than cutoff
     808    if (!node)
     809      continue;
    789810    currentNode_=node; // so can be accessed elsewhere
    790811#ifdef CBC_DEBUG
     
    793814           node->guessedObjectiveValue());
    794815#endif
    795     tree_->pop() ;
     816    // Save clone in branching decision
     817    if(branchingMethod_)
     818      branchingMethod_->saveBranchingObject(node->modifiableBranchingObject());
    796819    bool nodeOnTree=false; // Node has been popped
    797820    // Say not on optimal path
     
    912935          while (anyAction == -1)
    913936          {
    914             anyAction = newNode->chooseBranch(this,node,numberPassesLeft) ;
    915             if (onOptimalPath)
    916               assert (anyAction!=-2);
     937            if (numberBeforeTrust_<=0 ) {
     938              anyAction = newNode->chooseBranch(this,node,numberPassesLeft) ;
     939            } else {
     940              anyAction = newNode->chooseDynamicBranch(this,node,numberPassesLeft) ;
     941              if (anyAction==-3)
     942                anyAction = newNode->chooseBranch(this,node,numberPassesLeft) ; // dynamic did nothing
     943            }
     944            //if (onOptimalPath)
     945            //assert (anyAction!=-2); // can be useful but gives false positives on strong
    917946            numberPassesLeft--;
    918947            if (numberPassesLeft<=-1) {
     
    12441273  bestObjective_(COIN_DBL_MAX),
    12451274  bestPossibleObjective_(COIN_DBL_MAX),
     1275  sumChangeObjective1_(0.0),
     1276  sumChangeObjective2_(0.0),
    12461277  bestSolution_(NULL),
    12471278  currentSolution_(NULL),
     1279  testSolution_(NULL),
    12481280  minimumDrop_(1.0e-4),
    12491281  numberSolutions_(0),
     1282  stateOfSearch_(0),
    12501283  hotstartStrategy_(0),
    12511284  numberHeuristicSolutions_(0),
     
    12691302  presolve_(0),
    12701303  numberStrong_(5),
     1304  numberBeforeTrust_(0),
     1305  problemType_(0),
    12711306  printFrequency_(0),
    12721307  numberCutGenerators_(0),
     
    13221357  bestObjective_(COIN_DBL_MAX),
    13231358  bestPossibleObjective_(COIN_DBL_MAX),
     1359  sumChangeObjective1_(0.0),
     1360  sumChangeObjective2_(0.0),
    13241361  minimumDrop_(1.0e-4),
    13251362  numberSolutions_(0),
     1363  stateOfSearch_(0),
    13261364  hotstartStrategy_(0),
    13271365  numberHeuristicSolutions_(0),
     
    13431381  presolve_(0),
    13441382  numberStrong_(5),
     1383  numberBeforeTrust_(0),
     1384  problemType_(0),
    13451385  printFrequency_(0),
    13461386  numberCutGenerators_(0),
     
    14011441    currentSolution_=NULL;
    14021442  }
     1443  testSolution_=currentSolution_;
    14031444  if (numberIntegers_) {
    14041445    integerVariable_ = new int [numberIntegers_];
     
    14871528  bestObjective_(rhs.bestObjective_),
    14881529  bestPossibleObjective_(rhs.bestPossibleObjective_),
     1530  sumChangeObjective1_(rhs.sumChangeObjective1_),
     1531  sumChangeObjective2_(rhs.sumChangeObjective2_),
    14891532  minimumDrop_(rhs.minimumDrop_),
    14901533  numberSolutions_(rhs.numberSolutions_),
     1534  stateOfSearch_(rhs.stateOfSearch_),
    14911535  hotstartStrategy_(rhs.hotstartStrategy_),
    14921536  numberHeuristicSolutions_(rhs.numberHeuristicSolutions_),
     
    14991543  presolve_(rhs.presolve_),
    15001544  numberStrong_(rhs.numberStrong_),
     1545  numberBeforeTrust_(rhs.numberBeforeTrust_),
     1546  problemType_(rhs.problemType_),
    15011547  printFrequency_(rhs.printFrequency_),
    15021548  howOftenGlobalScan_(rhs.howOftenGlobalScan_),
     
    16071653    currentSolution_=NULL;
    16081654  }
     1655  testSolution_=currentSolution_;
    16091656  numberRowsAtContinuous_ = rhs.numberRowsAtContinuous_;
    16101657  maximumNumberCuts_=rhs.maximumNumberCuts_;
     
    16151662    bestObjective_ = COIN_DBL_MAX;
    16161663    numberSolutions_ =0;
     1664    stateOfSearch_= 0;
    16171665    numberHeuristicSolutions_=0;
    16181666    numberNodes_=0;
     
    16861734    bestObjective_ = rhs.bestObjective_;
    16871735    bestPossibleObjective_=rhs.bestPossibleObjective_;
     1736    sumChangeObjective1_=rhs.sumChangeObjective1_;
     1737    sumChangeObjective2_=rhs.sumChangeObjective2_;
    16881738    delete [] bestSolution_;
    16891739    if (rhs.bestSolution_) {
     
    17011751      currentSolution_=NULL;
    17021752    }
     1753    testSolution_=currentSolution_;
    17031754    minimumDrop_ = rhs.minimumDrop_;
    17041755    numberSolutions_=rhs.numberSolutions_;
     1756    stateOfSearch_= rhs.stateOfSearch_;
    17051757    hotstartStrategy_=rhs.hotstartStrategy_;
    17061758    numberHeuristicSolutions_=rhs.numberHeuristicSolutions_;
     
    17131765    presolve_ = rhs.presolve_;
    17141766    numberStrong_ = rhs.numberStrong_;
     1767    numberBeforeTrust_ = rhs.numberBeforeTrust_;
     1768    problemType_ = rhs.problemType_;
    17151769    printFrequency_ = rhs.printFrequency_;
    17161770    howOftenGlobalScan_=rhs.howOftenGlobalScan_;
     
    18521906  delete [] currentSolution_;
    18531907  currentSolution_=NULL;
     1908  testSolution_=currentSolution_;
    18541909  delete [] integerVariable_;
    18551910  integerVariable_=NULL;
     
    19341989}
    19351990void
     1991CbcModel::setNumberBeforeTrust(int number)
     1992{
     1993  if (number<=0) {
     1994    numberBeforeTrust_=0;
     1995  } else {
     1996    numberBeforeTrust_=number;
     1997    numberStrong_ = CoinMax(numberStrong_,1);
     1998  }
     1999}
     2000void
    19362001CbcModel::setHowOftenGlobalScan(int number)
    19372002{
     
    22722337                        whichGenerator grows.
    22732338
    2274     node: (currently unused)
     2339    node: (i)     So we can update dynamic pseudo costs
    22752340*/
    22762341                       
     
    23022367  after the debug stuff.
    23032368*/
     2369  double objectiveValue = solver_->getObjValue()*solver_->getObjSense();
     2370  if (node)
     2371    objectiveValue= node->objectiveValue();
    23042372  feasible = resolve() ;
     2373 
     2374  // Update branching information if wanted
     2375  if(node &&branchingMethod_)
     2376    branchingMethod_->updateInformation(solver_,node);
    23052377
    23062378#ifdef CBC_DEBUG
     
    23092381           (solver_->isProvenOptimal())?"proven":"unproven",
    23102382           solver_->getNumRows()) ; }
     2383 
    23112384  else
    23122385  { printf("Infeasible %d rows\n",solver_->getNumRows()) ; }
     
    23332406
    23342407  if (!feasible) return (false) ;
     2408  sumChangeObjective1_ += solver_->getObjValue()*solver_->getObjSense()
     2409    - objectiveValue ;
     2410  //if ((numberNodes_%100)==0)
     2411  //printf("XXa sum obj changed by %g\n",sumChangeObjective1_);
     2412  objectiveValue = solver_->getObjValue()*solver_->getObjSense();
    23352413  // Return at once if numberTries zero
    23362414  if (!numberTries) {
     
    25872665      }
    25882666    }
     2667    // If at root node and first pass do heuristics without cuts
     2668    if (!numberNodes_&&currentPassNumber_==1) {
     2669      for (int i = 0;i<numberHeuristics_;i++) {
     2670        // see if heuristic will do anything
     2671        double saveValue = heuristicValue ;
     2672        int ifSol = heuristic_[i]->solution(heuristicValue,
     2673                                            newSolution);
     2674        if (ifSol>0) {
     2675          // better solution found
     2676          found = i ;
     2677        } else {
     2678          heuristicValue = saveValue ;
     2679        }
     2680      }
     2681    }
    25892682/*
    25902683  End of the loop to exercise each generator/heuristic.
     
    28442937    }
    28452938  } while (numberTries>0) ;
     2939  // If at root node do heuristics
     2940  if (!numberNodes_) {
     2941    // mark so heuristics can tell
     2942    int savePass=currentPassNumber_;
     2943    currentPassNumber_=999999;
     2944    double * newSolution = new double [numberColumns] ;
     2945    double heuristicValue = getCutoff() ;
     2946    int found = -1; // no solution found
     2947    for (int i = 0;i<numberHeuristics_;i++) {
     2948      // see if heuristic will do anything
     2949      double saveValue = heuristicValue ;
     2950      int ifSol = heuristic_[i]->solution(heuristicValue,
     2951                                          newSolution);
     2952      if (ifSol>0) {
     2953        // better solution found
     2954        found = i ;
     2955      } else {
     2956        heuristicValue = saveValue ;
     2957      }
     2958    }
     2959    currentPassNumber_=savePass;
     2960    if (found >= 0) {
     2961      phase_=4;
     2962      setBestSolution(CBC_ROUNDING,heuristicValue,newSolution) ;
     2963    }
     2964    delete [] newSolution ;
     2965  }
     2966  // Up change due to cuts
     2967  if (feasible)
     2968    sumChangeObjective2_ += solver_->getObjValue()*solver_->getObjSense()
     2969      - objectiveValue ;
     2970  //if ((numberNodes_%100)==0)
     2971  //printf("XXb sum obj changed by %g\n",sumChangeObjective2_);
    28462972/*
    28472973  End of cut generation loop.
     
    29053031          howOften = 1+1000000 ;
    29063032        }
     3033        // If cuts useless switch off
     3034        if (numberNodes_>=10&&sumChangeObjective1_>1.0e2*(sumChangeObjective2_+1.0e-12)) {
     3035          howOften = 1000000+SCANCUTS; // wait until next time
     3036          printf("switch off cut %d due to lack of use\n",i);
     3037        }
    29073038      }
    29083039      if (howOften>=0&&generator_[i]->generator()->mayGenerateRowCutsInTree())
     
    29103041       
    29113042      generator_[i]->setHowOften(howOften) ;
     3043      if (howOften>=1000000&&howOften<2000000&&0) {
     3044        // Go to depth
     3045        int bias=1;
     3046        if (howOften==1+1000000)
     3047          generator_[i]->setWhatDepth(bias+1);
     3048        else if (howOften<=10+1000000)
     3049          generator_[i]->setWhatDepth(bias+2);
     3050        else
     3051          generator_[i]->setWhatDepth(bias+1000);
     3052      }
    29123053      int newFrequency = generator_[i]->howOften()%1000000 ;
    29133054      // increment cut counts
     
    36123753      handler_->message(CBC_NOINT,messages_) << CoinMessageEol ;
    36133754}
     3755/* If numberBeforeTrust >0 then we are going to use CbcBranchDynamic.
     3756   Scan and convert CbcSimpleInteger objects
     3757*/
     3758void
     3759CbcModel::convertToDynamic()
     3760{
     3761  int iObject;
     3762  for (iObject = 0;iObject<numberObjects_;iObject++) {
     3763    CbcSimpleInteger * obj1 =
     3764      dynamic_cast <CbcSimpleInteger *>(object_[iObject]) ;
     3765    CbcSimpleIntegerDynamicPseudoCost * obj2 =
     3766      dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[iObject]) ;
     3767    if (obj1&&!obj2) {
     3768      // replace
     3769      int iColumn = obj1->columnNumber();
     3770      delete object_[iObject];
     3771      CbcSimpleIntegerDynamicPseudoCost * newObject =
     3772        new CbcSimpleIntegerDynamicPseudoCost(this,iObject,iColumn,0.3);
     3773      newObject->setNumberBeforeTrust(numberBeforeTrust_);
     3774      object_[iObject] = newObject;
     3775    }
     3776  }
     3777  if (branchingMethod_&&(branchingMethod_->whichMethod()&1)==0) {
     3778    // Need a method which can do better
     3779    branchingMethod_=NULL;
     3780  }
     3781}
    36143782
    36153783/* Add in any object information (objects are cloned - owner can delete
     
    37833951  solver_->setColSolution(solution);
    37843952  // Put current solution in safe place
    3785   memcpy(currentSolution_,solver_->getColSolution(),
    3786          numberColumns*sizeof(double));
     3953  // Point to current solution
     3954  const double * save = testSolution_;
     3955  // Safe as will be const inside infeasibility()
     3956  testSolution_ = solver_->getColSolution();
     3957  //memcpy(currentSolution_,solver_->getColSolution(),
     3958  // numberColumns*sizeof(double));
    37873959  //solver_->messageHandler()->setLogLevel(4);
    37883960
     
    38484020  */
    38494021  if (solver_->isProvenOptimal() && objectiveValue <= cutoff)
    3850   { solution = solver_->getColSolution() ;
    3851     memcpy(currentSolution_,solution,numberColumns*sizeof(double)) ;
     4022  {
     4023    double * solution = new double[numberColumns];
     4024    memcpy(solution ,solver_->getColSolution(),numberColumns*sizeof(double)) ;
    38524025
    38534026    const double * rowLower = solver_->getRowLower() ;
     
    38614034    int iColumn;
    38624035    for (iColumn = 0 ; iColumn < numberColumns ; iColumn++)
    3863     { double value = currentSolution_[iColumn] ;
     4036    { double value = solution[iColumn] ;
    38644037      value = CoinMax(value, saveLower[iColumn]) ;
    38654038      value = CoinMin(value, saveUpper[iColumn]) ;
    38664039      if (solver_->isInteger(iColumn))
    3867         assert(fabs(value-currentSolution_[iColumn]) <= integerTolerance) ;
    3868       currentSolution_[iColumn] = value ; }
     4040        assert(fabs(value-solution[iColumn]) <= integerTolerance) ;
     4041      solution[iColumn] = value ; }
    38694042   
    3870     solver_->getMatrixByCol()->times(currentSolution_,rowActivity) ;
     4043    solver_->getMatrixByCol()->times(solution,rowActivity) ;
     4044    delete [] solution;
    38714045    double primalTolerance ;
    38724046    solver_->getDblParam(OsiPrimalTolerance,primalTolerance) ;
     
    39014075  */
    39024076  solver_=saveSolver;
     4077  testSolution_ = save;
    39034078  return objectiveValue;
    39044079}
     
    39494124    if (!bestSolution_)
    39504125      bestSolution_ = new double[numberColumns];
    3951     memcpy(bestSolution_,currentSolution_,numberColumns*sizeof(double));
     4126    memcpy(bestSolution_,solution,numberColumns*sizeof(double));
    39524127
    39534128    cutoff = bestObjective_-dblParam_[CbcCutoffIncrement];
     
    39604135      numberHeuristicSolutions_++;
    39614136    numberSolutions_++;
     4137    if (numberHeuristicSolutions_==numberSolutions_)
     4138      stateOfSearch_ = 1;
     4139    else
     4140      stateOfSearch_ = 2;
    39624141
    39634142    handler_->message(how,messages_)
     
    40284207  int preferredWay;
    40294208  int j;
     4209  // Point to current solution
     4210  const double * save = testSolution_;
     4211  // Safe as will be const inside infeasibility()
     4212  testSolution_ = solver_->getColSolution();
    40304213  // Put current solution in safe place
    4031   memcpy(currentSolution_,solver_->getColSolution(),
    4032         solver_->getNumCols()*sizeof(double));
     4214  //memcpy(currentSolution_,solver_->getColSolution(),
     4215  // solver_->getNumCols()*sizeof(double));
    40334216  for (j=0;j<numberIntegers_;j++) {
    40344217    const CbcObject * object = object_[j];
     
    40504233    }
    40514234  }
     4235  // and restore
     4236  testSolution_ = save;
    40524237  numberObjectInfeasibilities = numberUnsatisfied-numberIntegerInfeasibilities;
    40534238  return (!numberUnsatisfied);
     
    46724857          if (!currentSolution_)
    46734858            currentSolution_ = new double[numberColumns] ;
     4859          testSolution_=currentSolution_;
    46744860          // better solution save
    46754861          setBestSolution(CBC_ROUNDING,heuristicValue,
     
    48235009      if (!currentSolution_)
    48245010        currentSolution_ = new double[numberColumns] ;
     5011      testSolution_ = currentSolution_;
    48255012      assert(feasibleSolution(numberIntegerInfeasibilities,
    48265013                              numberObjectInfeasibilities));
     
    48605047  if (!currentSolution_)
    48615048    currentSolution_ = new double[numberColumns] ;
     5049  testSolution_=currentSolution_;
    48625050  if (solution)
    48635051    memcpy(currentSolution_,solution,numberColumns*sizeof(double));
     
    52025390  if (!currentSolution_)
    52035391    currentSolution_ = new double[numberColumns] ;
     5392  testSolution_=currentSolution_;
    52045393/*
    52055394  Create a copy of the solver, thus capturing the original (root node)
  • trunk/CbcNode.cpp

    r130 r135  
    88//#define CBC_DEBUG 1
    99//#define CHECK_CUT_COUNTS
     10//#define CHECK_NODE
    1011#include <cassert>
    1112#include <cfloat>
     
    1718#include "CbcNode.hpp"
    1819#include "CbcBranchActual.hpp"
     20#include "CbcBranchDynamic.hpp"
    1921#include "OsiRowCut.hpp"
    2022#include "OsiRowCutDebugger.hpp"
     
    874876  double * saveSolution = new double[numberColumns];
    875877  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
    876  
     878  model->reserveCurrentSolution(saveSolution);
    877879  /*
    878880    Get a branching decision object. Use the default decision criteria unless
     
    883885    decision = new CbcBranchDefaultDecision();
    884886
    885   typedef struct {
    886     CbcBranchingObject * possibleBranch; // what a branch would do
    887     double upMovement; // cost going up (and initial away from feasible)
    888     double downMovement; // cost going down
    889     int numIntInfeasUp ; // without odd ones
    890     int numObjInfeasUp ; // just odd ones
    891     bool finishedUp; // true if solver finished
    892     int numItersUp ; // number of iterations in solver
    893     int numIntInfeasDown ; // without odd ones
    894     int numObjInfeasDown ; // just odd ones
    895     bool finishedDown; // true if solver finished
    896     int numItersDown; // number of iterations in solver
    897     int objectNumber; // Which object it is
    898     int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down
    899   } Strong;
    900   Strong * choice = new Strong[maximumStrong];
     887  CbcStrongInfo * choice = new CbcStrongInfo[maximumStrong];
    901888  for (i=0;i<numberColumns;i++) {
    902889    saveLower[i] = lower[i];
     
    948935      int iSmallest = 0;
    949936      double mostAway = 1.0e-100;
    950       for (i = 0 ; i < maximumStrong ; i++) choice[i].possibleBranch = NULL ;
     937      for (i = 0 ; i < maximumStrong ; i++)
     938        choice[i].possibleBranch = NULL ;
    951939      numberStrong=0;
    952940      for (i=0;i<numberObjects;i++) {
     
    10691057          solver->resolve();
    10701058          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1059          model->reserveCurrentSolution(saveSolution);
    10711060          if (!solver->isProvenOptimal()) {
    10721061            // infeasible
     
    11501139      if (osiclp&&(osiclp->specialOptions()&16)!=0&&osiclp->specialOptions()>0)
    11511140        allNormal=false;
     1141      if (osiclp&&!allNormal) {
     1142        // say do fast
     1143        int easy=1;
     1144        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     1145      }
    11521146      if (osiclp&& allNormal) {
    11531147        clp = osiclp->getModelPtr();
     
    12651259                sol2[iColumn]=saveSolution[iColumn];
    12661260              }
    1267               //printf("strong %d col %d sol %g sol2 %g\n",i,iColumn,sol[iColumn],
    1268               //     sol2[iColumn]);
    1269               //if (fabs(sol[iColumn]-0.5)<0.499)
    1270               //x=false;
    1271               //if (fabs(sol2[iColumn]-0.5)<0.499)
    1272               //x2=false;
    12731261            }
    1274 #if 0
    1275             if( outputStuff[2*i]!=0&&outputStuff[2*i+1]!=0)
    1276               checkSol=false;
    1277             if (x&&checkSol) {
    1278               int iStatus = outputStuff[2*i];
    1279               double newObjectiveValue = objectiveValue+newUpper[i];
    1280               //printf("solution found - status %d obj %g\n",iStatus,newObjectiveValue);
    1281               if (!iStatus) {
    1282                 const double * lower = solver->getRowLower();
    1283                 const double * upper = solver->getRowUpper();
    1284                 int numberRows = solver->getNumRows();
    1285                 double * rhs = new double [numberRows];
    1286                 CoinZeroN(rhs,numberRows);
    1287                 {
    1288                   int numberColumns = solver->getNumCols();
    1289                   const double * columnLower = solver->getColLower();
    1290                   const double * columnUpper = solver->getColUpper();
    1291                   int numberRows = solver->getNumRows();
    1292                  
    1293                   const double * element = matrix->getElements();
    1294                   const int * row = matrix->getIndices();
    1295                   const CoinBigIndex * columnStart = matrix->getVectorStarts();
    1296                   const int * columnLength = matrix->getVectorLengths();
    1297                   CoinZeroN(rhs,numberRows);
    1298                   int iColumn;
    1299                   for (iColumn=0;iColumn<numberColumns;iColumn++) {
    1300                     double lower = columnLower[iColumn];
    1301                     double upper = columnUpper[iColumn];
    1302                     double solValue = sol[iColumn];
    1303                     assert (solValue>=lower-1.0e-4&&solValue<upper+1.0e-4);
    1304                     for (CoinBigIndex j = columnStart[iColumn];
    1305                          j<columnStart[iColumn]+columnLength[iColumn];j++) {
    1306                       int iRow = row[j];
    1307                       double value = element[j];
    1308                       rhs[iRow] += solValue*value;
    1309                       if (iRow==-19)
    1310                         printf("col %d has sol %g and el %g , rhs now %g\n",
    1311                                iColumn,solValue,element[j],rhs[19]);
    1312                     }
    1313                   }
    1314                 }
    1315                 for (int i=0;i<numberRows;i++) {
    1316                   assert (rhs[i]>lower[i]-1.0e-3);
    1317                   assert (rhs[i]<upper[i]+1.0e-3);
    1318                 }
    1319                 delete [] rhs;
    1320               }
    1321             }
    1322             if (x2&&checkSol) {
    1323               int iStatus = outputStuff[2*i+1];
    1324               double newObjectiveValue = objectiveValue+newLower[i];
    1325               //printf("solution found - status %d obj %g\n",iStatus,newObjectiveValue);
    1326               if (!iStatus) {
    1327                 const double * lower = solver->getRowLower();
    1328                 const double * upper = solver->getRowUpper();
    1329                 int numberRows = solver->getNumRows();
    1330                 double * rhs = new double [numberRows];
    1331                 CoinZeroN(rhs,numberRows);
    1332                 solver->getMatrixByCol()->times(sol2,rhs) ;
    1333                 for (int i=0;i<numberRows;i++) {
    1334                   assert (rhs[i]>lower[i]-1.0e-4);
    1335                   assert (rhs[i]<upper[i]+1.0e-4);
    1336                 }
    1337                 delete [] rhs;
    1338               }
    1339             }
    1340 #endif
    13411262          }
    13421263#endif
     
    15631484            // up feasible, down infeasible
    15641485            anyAction=-1;
     1486            //printf("Down infeasible for choice %d sequence %d\n",i,
     1487            // model->object(choice[i].objectNumber)->columnNumber());
    15651488            if (!solveAll) {
    15661489              choice[i].possibleBranch->way(1);
     
    15751498            // down feasible, up infeasible
    15761499            anyAction=-1;
     1500            //printf("Up infeasible for choice %d sequence %d\n",i,
     1501            // model->object(choice[i].objectNumber)->columnNumber());
    15771502            if (!solveAll) {
    15781503              choice[i].possibleBranch->way(-1);
     
    15851510            // neither side feasible
    15861511            anyAction=-2;
     1512            //printf("Both infeasible for choice %d sequence %d\n",i,
     1513            // model->object(choice[i].objectNumber)->columnNumber());
    15871514            break;
    15881515          }
     
    16481575          int numberLeft=0;
    16491576          for (i = 0 ; i < numberStrong ; i++) {
    1650             Strong thisChoice = choice[i];
     1577            CbcStrongInfo thisChoice = choice[i];
    16511578            choice[i].possibleBranch=NULL;
    16521579            const CbcObject * object = model->object(thisChoice.objectNumber);
     
    17161643        // all feasible - choose best bet
    17171644       
    1718 #if 0
    1719         for (i = 0 ; i < numberStrong ; i++)
    1720           { int iColumn =
    1721               model->integerVariable()[choice[i].possibleBranch->variable()] ;
    1722           model->messageHandler()->message(CBC_STRONG,model->messages())
    1723             << i << iColumn
    1724             <<choice[i].downMovement<<choice[i].numIntInfeasDown
    1725             <<choice[i].upMovement<<choice[i].numIntInfeasUp
    1726             <<choice[i].possibleBranch->value()
    1727             <<CoinMessageEol;
    1728           int betterWay = decision->betterBranch(choice[i].possibleBranch,
    1729                                                  branch_,
    1730                                                  choice[i].upMovement,
    1731                                                  choice[i].numIntInfeasUp ,
    1732                                                  choice[i].downMovement,
    1733                                                  choice[i].numIntInfeasDown );
    1734           if (betterWay) {
    1735             delete branch_;
    1736             // C) create branching object
    1737             branch_ = choice[i].possibleBranch;
    1738             choice[i].possibleBranch=NULL;
    1739             branch_->way(betterWay);
    1740           }
    1741           }
    1742 #else
    17431645        // New method does all at once so it can be more sophisticated
    17441646        // in deciding how to balance actions.
     
    17771679        delete [] numberInfeasibilitiesDown;
    17781680        delete [] objects;
    1779 #endif
     1681      }
     1682      if (osiclp&&!allNormal) {
     1683        // back to normal
     1684        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
    17801685      }
    17811686    }
     
    17921697  }
    17931698  // Set guessed solution value
     1699  objectiveValue_ = solver->getObjSense()*saveObjectiveValue;
    17941700  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
    17951701/*
     
    18111717}
    18121718
     1719/*
     1720  Version for dynamic pseudo costs.
     1721
     1722  **** For now just return if anything odd
     1723  later allow even if odd
     1724
     1725  The routine scans through the object list of the model looking for objects
     1726  that indicate infeasibility. It tests each object using strong branching
     1727  and selects the one with the least objective degradation.  A corresponding
     1728  branching object is left attached to lastNode.
     1729  This version gives preference in evaluation to variables which
     1730  have not been evaluated many times.  It also uses numberStrong
     1731  to say give up if last few tries have not changed incumbent.
     1732  See Achterberg, Koch and Martin.
     1733
     1734  If strong branching is disabled, a candidate object is chosen essentially
     1735  at random (whatever object ends up in pos'n 0 of the candidate array).
     1736
     1737  If a branching candidate is found to be monotone, bounds are set to fix the
     1738  variable and the routine immediately returns (the caller is expected to
     1739  reoptimize).
     1740
     1741  If a branching candidate is found to result in infeasibility in both
     1742  directions, the routine immediately returns an indication of infeasibility.
     1743
     1744  Returns:  0   both branch directions are feasible
     1745           -1   branching variable is monotone
     1746           -2   infeasible
     1747           -3   Use another method
     1748
     1749           For now just fix on objective from strong branching.
     1750*/
     1751
     1752int CbcNode::chooseDynamicBranch (CbcModel *model, CbcNode *lastNode,int numberPassesLeft)
     1753
     1754{ if (lastNode)
     1755    depth_ = lastNode->depth_+1;
     1756  else
     1757    depth_ = 0;
     1758  delete branch_;
     1759  branch_=NULL;
     1760  OsiSolverInterface * solver = model->solver();
     1761  objectiveValue_ = solver->getObjSense()*solver->getObjValue();
     1762  const double * lower = solver->getColLower();
     1763  const double * upper = solver->getColUpper();
     1764  int anyAction=0;
     1765  int i;
     1766  int stateOfSearch = model->stateOfSearch();
     1767  int numberStrong=model->numberStrong();
     1768  // But make more likely to get out after some times
     1769  int changeStrategy=numberStrong;
     1770  double changeFactor=1.0;
     1771  // Use minimum of this and one stored in objects
     1772  //int numberBeforeTrust = model->numberBeforeTrust();
     1773  int numberObjects = model->numberObjects();
     1774  bool checkFeasibility = numberObjects>model->numberIntegers();
     1775  // For now return if not simple
     1776  if (checkFeasibility)
     1777    return -3;
     1778  // Return if doing hot start (in BAB sense)
     1779  int hotstartStrategy=model->getHotstartStrategy();
     1780  if (hotstartStrategy>0)
     1781    return -3;
     1782  int numberColumns = model->getNumCols();
     1783  double * saveUpper = new double[numberColumns];
     1784  double * saveLower = new double[numberColumns];
     1785
     1786  // Save solution in case heuristics need good solution later
     1787 
     1788  double * saveSolution = new double[numberColumns];
     1789  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1790  model->reserveCurrentSolution(saveSolution);
     1791  /*
     1792    Get a branching decision object. Use the default dynamic decision criteria unless
     1793    the user has loaded a decision method into the model.
     1794  */
     1795  CbcBranchDecision *decision = model->branchingMethod();
     1796  if (!decision)
     1797    decision = new CbcBranchDynamicDecision();
     1798
     1799  for (i=0;i<numberColumns;i++) {
     1800    saveLower[i] = lower[i];
     1801    saveUpper[i] = upper[i];
     1802  }
     1803  // Get arrays to sort
     1804  double * sort = new double[numberObjects];
     1805  int * whichObject = new int[numberObjects];
     1806  CbcStrongInfo * fixObject = new CbcStrongInfo[numberObjects];
     1807  double estimatedDegradation=0.0;
     1808  // May go round twice if strong branching fixes all local candidates
     1809  bool finished=false;
     1810  while(!finished) {
     1811    finished=true;
     1812    decision->initialize(model);
     1813    // Some objects may compute an estimate of best solution from here
     1814    estimatedDegradation=0.0;
     1815    int numberToFix=0;
     1816    int numberIntegerInfeasibilities=0; // without odd ones
     1817    int numberToDo=0;
     1818   
     1819    // We may go round this loop twice (only if we think we have solution)
     1820    for (int iPass=0;iPass<2;iPass++) {
     1821     
     1822      // compute current state
     1823      int numberObjectInfeasibilities; // just odd ones
     1824      model->feasibleSolution(
     1825                              numberIntegerInfeasibilities,
     1826                              numberObjectInfeasibilities);
     1827     
     1828      // Some objects may compute an estimate of best solution from here
     1829      estimatedDegradation=0.0;
     1830      numberUnsatisfied_ = 0;
     1831      int bestPriority=INT_MAX;
     1832      /*
     1833        Scan for branching objects that indicate infeasibility. Choose candidates
     1834        using priority as the first criteria, then integer infeasibility.
     1835       
     1836        The algorithm is to fill the array with a set of good candidates (by
     1837        infeasibility) with priority bestPriority.  Finding a candidate with
     1838        priority better (less) than bestPriority flushes the choice array. (This
     1839        serves as initialization when the first candidate is found.)
     1840       
     1841      */
     1842      numberToDo=0;
     1843      for (i=0;i<numberObjects;i++) {
     1844        const CbcObject * object = model->object(i);
     1845        int preferredWay;
     1846        double infeasibility = object->infeasibility(preferredWay);
     1847        int priorityLevel = object->priority();
     1848        if (infeasibility) {
     1849          // Increase estimated degradation to solution
     1850          estimatedDegradation += CoinMin(object->upEstimate(),object->downEstimate());
     1851          numberUnsatisfied_++;
     1852          // Better priority? Flush choices.
     1853          if (priorityLevel<bestPriority) {
     1854            numberToDo=0;
     1855            bestPriority = priorityLevel;
     1856          } else if (priorityLevel>bestPriority) {
     1857            continue;
     1858          }
     1859          // Check for suitability based on infeasibility.
     1860          sort[numberToDo]=-infeasibility;
     1861          whichObject[numberToDo++]=i;
     1862        }
     1863      }
     1864      if (numberUnsatisfied_) {
     1865        // some infeasibilities - go to next steps
     1866        break;
     1867      } else if (!iPass) {
     1868        // looks like a solution - get paranoid
     1869        bool roundAgain=false;
     1870        // get basis
     1871        CoinWarmStartBasis * ws = dynamic_cast<CoinWarmStartBasis*>(solver->getWarmStart());
     1872        if (!ws)
     1873          break;
     1874        for (i=0;i<numberColumns;i++) {
     1875          double value = saveSolution[i];
     1876          if (value<lower[i]) {
     1877            saveSolution[i]=lower[i];
     1878            roundAgain=true;
     1879            ws->setStructStatus(i,CoinWarmStartBasis::atLowerBound);
     1880          } else if (value>upper[i]) {
     1881            saveSolution[i]=upper[i];
     1882            roundAgain=true;
     1883            ws->setStructStatus(i,CoinWarmStartBasis::atUpperBound);
     1884          }
     1885        }
     1886        if (roundAgain) {
     1887          // restore basis
     1888          solver->setWarmStart(ws);
     1889          solver->setColSolution(saveSolution);
     1890          delete ws;
     1891          solver->resolve();
     1892          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1893          model->reserveCurrentSolution(saveSolution);
     1894          if (!solver->isProvenOptimal()) {
     1895            // infeasible
     1896            anyAction=-2;
     1897            break;
     1898          }
     1899        } else {
     1900          delete ws;
     1901          break;
     1902        }
     1903      }
     1904    }
     1905    if (anyAction==-2) {
     1906      break;
     1907    }
     1908    bool solveAll=false; // set true to say look at all even if some fixed (experiment)
     1909    solveAll=true;
     1910    // worth trying if too many times
     1911    // Save basis
     1912    CoinWarmStart * ws = solver->getWarmStart();
     1913    // save limit
     1914    int saveLimit;
     1915    solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
     1916    if (!stateOfSearch&&saveLimit<100)
     1917      solver->setIntParam(OsiMaxNumIterationHotStart,100);
     1918   
     1919    // Sort
     1920    CoinSort_2(sort,sort+numberToDo,whichObject);
     1921    // Say which one will be best
     1922    int whichChoice=0;
     1923    int bestChoice=-1;
     1924    // If we have hit max time don't do strong branching
     1925    bool hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
     1926                        model->getDblParam(CbcModel::CbcMaximumSeconds));
     1927    // also give up if we are looping round too much
     1928    if (hitMaxTime||numberPassesLeft<=0) {
     1929      int iObject = whichObject[0];
     1930      CbcObject * object = model->modifiableObject(iObject);
     1931      int preferredWay;
     1932      object->infeasibility(preferredWay);
     1933      branch_=object->createBranch(preferredWay);
     1934      branch_->way(preferredWay);
     1935      break;
     1936    } else {
     1937      // say do fast
     1938      int easy=1;
     1939      solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     1940      // Mark hot start
     1941      solver->markHotStart();
     1942      int iDo=0;
     1943      for ( iDo=0;iDo<numberToDo;iDo++) {
     1944        CbcStrongInfo choice;
     1945        int iObject = whichObject[iDo];
     1946        CbcObject * object = model->modifiableObject(iObject);
     1947        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
     1948          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     1949        int preferredWay;
     1950        object->infeasibility(preferredWay);
     1951        choice.possibleBranch=object->createBranch(preferredWay);
     1952        // Save which object it was
     1953        choice.objectNumber=iObject;
     1954        choice.numIntInfeasUp = numberUnsatisfied_;
     1955        choice.numIntInfeasDown = numberUnsatisfied_;
     1956        choice.fix=0; // say not fixed
     1957        // see if can skip strong branching
     1958        int canSkip = choice.possibleBranch->fillStrongInfo(choice);
     1959        // For now always do
     1960        canSkip=false;
     1961        if (model->messageHandler()->logLevel()>3)
     1962          dynamicObject->print(1,choice.possibleBranch->value());
     1963        if (!canSkip) {
     1964          double objectiveChange ;
     1965          double newObjectiveValue=1.0e100;
     1966          int j;
     1967          // status is 0 finished, 1 infeasible and other
     1968          int iStatus;
     1969          /*
     1970            Try the down direction first. (Specify the initial branching alternative as
     1971            down with a call to way(-1). Each subsequent call to branch() performs the
     1972            specified branch and advances the branch object state to the next branch
     1973            alternative.)
     1974          */
     1975          choice.possibleBranch->way(-1) ;
     1976          decision->saveBranchingObject( choice.possibleBranch);
     1977          choice.possibleBranch->branch() ;
     1978          solver->solveFromHotStart() ;
     1979          /*
     1980            We now have an estimate of objective degradation that we can use for strong
     1981            branching. If we're over the cutoff, the variable is monotone up.
     1982            If we actually made it to optimality, check for a solution, and if we have
     1983            a good one, call setBestSolution to process it. Note that this may reduce the
     1984            cutoff, so we check again to see if we can declare this variable monotone.
     1985          */
     1986          if (solver->isProvenOptimal())
     1987            iStatus=0; // optimal
     1988          else if (solver->isIterationLimitReached()
     1989                   &&!solver->isDualObjectiveLimitReached())
     1990            iStatus=2; // unknown
     1991          else
     1992            iStatus=1; // infeasible
     1993          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
     1994          choice.numItersDown = solver->getIterationCount();
     1995          objectiveChange = newObjectiveValue  - objectiveValue_;
     1996          decision->updateInformation( solver,this);
     1997          if (!iStatus) {
     1998            choice.finishedDown = true ;
     1999            if (newObjectiveValue>=model->getCutoff()) {
     2000              objectiveChange = 1.0e100; // say infeasible
     2001            } else {
     2002              // See if integer solution
     2003              if (model->feasibleSolution(choice.numIntInfeasDown,
     2004                                          choice.numObjInfeasDown)) {
     2005                model->setBestSolution(CBC_STRONGSOL,
     2006                                       newObjectiveValue,
     2007                                       solver->getColSolution()) ;
     2008                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2009                  objectiveChange = 1.0e100 ;
     2010              }
     2011            }
     2012          } else if (iStatus==1) {
     2013            objectiveChange = 1.0e100 ;
     2014          } else {
     2015            // Can't say much as we did not finish
     2016            choice.finishedDown = false ;
     2017          }
     2018          choice.downMovement = objectiveChange ;
     2019         
     2020          // restore bounds
     2021          for ( j=0;j<numberColumns;j++) {
     2022            if (saveLower[j] != lower[j])
     2023              solver->setColLower(j,saveLower[j]);
     2024            if (saveUpper[j] != upper[j])
     2025              solver->setColUpper(j,saveUpper[j]);
     2026          }
     2027          //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
     2028          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersDown,
     2029          //     choice.downMovement,choice.finishedDown,choice.numIntInfeasDown,
     2030          //     choice.numObjInfeasDown);
     2031         
     2032          // repeat the whole exercise, forcing the variable up
     2033          decision->saveBranchingObject( choice.possibleBranch);
     2034          choice.possibleBranch->branch();
     2035          solver->solveFromHotStart() ;
     2036          /*
     2037            We now have an estimate of objective degradation that we can use for strong
     2038            branching. If we're over the cutoff, the variable is monotone up.
     2039            If we actually made it to optimality, check for a solution, and if we have
     2040            a good one, call setBestSolution to process it. Note that this may reduce the
     2041            cutoff, so we check again to see if we can declare this variable monotone.
     2042          */
     2043          if (solver->isProvenOptimal())
     2044            iStatus=0; // optimal
     2045          else if (solver->isIterationLimitReached()
     2046                   &&!solver->isDualObjectiveLimitReached())
     2047            iStatus=2; // unknown
     2048          else
     2049            iStatus=1; // infeasible
     2050          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
     2051          choice.numItersUp = solver->getIterationCount();
     2052          objectiveChange = newObjectiveValue  - objectiveValue_;
     2053          decision->updateInformation( solver,this);
     2054          if (!iStatus) {
     2055            choice.finishedUp = true ;
     2056            if (newObjectiveValue>=model->getCutoff()) {
     2057              objectiveChange = 1.0e100; // say infeasible
     2058            } else {
     2059              // See if integer solution
     2060              if (model->feasibleSolution(choice.numIntInfeasUp,
     2061                                          choice.numObjInfeasUp)) {
     2062                model->setBestSolution(CBC_STRONGSOL,
     2063                                       newObjectiveValue,
     2064                                       solver->getColSolution()) ;
     2065                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2066                  objectiveChange = 1.0e100 ;
     2067              }
     2068            }
     2069          } else if (iStatus==1) {
     2070            objectiveChange = 1.0e100 ;
     2071          } else {
     2072            // Can't say much as we did not finish
     2073            choice.finishedUp = false ;
     2074          }
     2075          choice.upMovement = objectiveChange ;
     2076         
     2077          // restore bounds
     2078          for ( j=0;j<numberColumns;j++) {
     2079            if (saveLower[j] != lower[j])
     2080              solver->setColLower(j,saveLower[j]);
     2081            if (saveUpper[j] != upper[j])
     2082              solver->setColUpper(j,saveUpper[j]);
     2083          }
     2084         
     2085          //printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
     2086          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersUp,
     2087          //     choice.upMovement,choice.finishedUp,choice.numIntInfeasUp,
     2088          //     choice.numObjInfeasUp);
     2089          hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
     2090                         model->getDblParam(CbcModel::CbcMaximumSeconds));
     2091          if (hitMaxTime) {
     2092            break;
     2093          }
     2094        }
     2095        /*
     2096          End of evaluation for this candidate variable. Possibilities are:
     2097          * Both sides below cutoff; this variable is a candidate for branching.
     2098          * Both sides infeasible or above the objective cutoff: no further action
     2099          here. Break from the evaluation loop and assume the node will be purged
     2100          by the caller.
     2101          * One side below cutoff: Install the branch (i.e., fix the variable). Break
     2102          from the evaluation loop and assume the node will be reoptimised by the
     2103          caller.
     2104        */
     2105        if (choice.upMovement<1.0e100) {
     2106          if(choice.downMovement<1.0e100) {
     2107            // feasible - see which best
     2108            int iColumn =
     2109              model->integerVariable()[choice.possibleBranch->variable()] ;
     2110            model->messageHandler()->message(CBC_STRONG,model->messages())
     2111              << iObject << iColumn
     2112              <<choice.downMovement<<choice.numIntInfeasDown
     2113              <<choice.upMovement<<choice.numIntInfeasUp
     2114              <<choice.possibleBranch->value()
     2115              <<CoinMessageEol;
     2116            //if (!stateOfSearch)
     2117            //choice.numIntInfeasDown=99999; // temp fudge
     2118            int betterWay = decision->betterBranch(choice.possibleBranch,
     2119                                                   branch_,
     2120                                                   choice.upMovement*changeFactor,
     2121                                                   choice.numIntInfeasUp ,
     2122                                                   choice.downMovement*changeFactor,
     2123                                                   choice.numIntInfeasDown );
     2124            if (iDo>=changeStrategy) {
     2125              // make less likely
     2126              changeStrategy+=numberStrong;
     2127              changeFactor *= 0.9;
     2128            }
     2129            if (betterWay) {
     2130              delete branch_;
     2131              // C) create branching object
     2132              branch_ = choice.possibleBranch;
     2133              choice.possibleBranch=NULL;
     2134              branch_->way(betterWay);
     2135              bestChoice = choice.objectNumber;
     2136              whichChoice = iDo;
     2137            } else {
     2138              delete choice.possibleBranch;
     2139              if (iDo>=2*numberStrong)
     2140                break;
     2141              if (!dynamicObject||dynamicObject->numberTimesUp()>1) {
     2142                if (iDo-whichChoice>=numberStrong)
     2143                  break; // give up
     2144              } else {
     2145                if (iDo-whichChoice>=2*numberStrong)
     2146                  break; // give up
     2147              }
     2148            }
     2149          } else {
     2150            // up feasible, down infeasible
     2151            anyAction=-1;
     2152            //printf("Down infeasible for choice %d sequence %d\n",i,
     2153            // model->object(choice.objectNumber)->columnNumber());
     2154            if (!solveAll) {
     2155              choice.possibleBranch->way(1);
     2156              choice.possibleBranch->branch();
     2157              delete choice.possibleBranch;
     2158              break;
     2159            } else {
     2160              choice.fix=1;
     2161              fixObject[numberToFix++]=choice;
     2162            }
     2163          }
     2164        } else {
     2165          if(choice.downMovement<1.0e100) {
     2166            // down feasible, up infeasible
     2167            anyAction=-1;
     2168            //printf("Up infeasible for choice %d sequence %d\n",i,
     2169            // model->object(choice.objectNumber)->columnNumber());
     2170            if (!solveAll) {
     2171              choice.possibleBranch->way(-1);
     2172              choice.possibleBranch->branch();
     2173              delete choice.possibleBranch;
     2174              break;
     2175            } else {
     2176              choice.fix=-1;
     2177              fixObject[numberToFix++]=choice;
     2178            }
     2179          } else {
     2180            // neither side feasible
     2181            anyAction=-2;
     2182            delete choice.possibleBranch;
     2183            //printf("Both infeasible for choice %d sequence %d\n",i,
     2184            // model->object(choice.objectNumber)->columnNumber());
     2185            break;
     2186          }
     2187        }
     2188      }
     2189      if (model->messageHandler()->logLevel()>3) {
     2190        if (anyAction==-2)
     2191          printf("infeasible\n");
     2192        else if(anyAction==-1)
     2193          printf("%d fixed\n",numberToFix);
     2194        else
     2195          printf("choosing %d\n",bestChoice);
     2196      }
     2197      // Delete the snapshot
     2198      solver->unmarkHotStart();
     2199      // back to normal
     2200      solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
     2201      solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
     2202      // restore basis
     2203      solver->setWarmStart(ws);
     2204      // Unless infeasible we will carry on
     2205      // But we could fix anyway
     2206      if (numberToFix) {
     2207        if (anyAction==-2) {
     2208          // take off
     2209          for (i = 0 ; i < numberToFix ; i++) {
     2210            delete fixObject[i].possibleBranch;
     2211          }
     2212        } else {
     2213          // apply and take off
     2214          for (i = 0 ; i < numberToFix ; i++) {
     2215            fixObject[i].possibleBranch->way(fixObject[i].fix) ;
     2216            fixObject[i].possibleBranch->branch() ;
     2217            delete fixObject[i].possibleBranch;
     2218          }
     2219          bool feasible=true;
     2220          // can do quick optimality check
     2221          int easy=2;
     2222          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     2223          solver->resolve() ;
     2224          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
     2225          feasible = solver->isProvenOptimal();
     2226          if (feasible) {
     2227            anyAction=0;
     2228            memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     2229            model->reserveCurrentSolution(saveSolution);
     2230            memcpy(saveLower,solver->getColLower(),numberColumns*sizeof(double));
     2231            memcpy(saveUpper,solver->getColUpper(),numberColumns*sizeof(double));
     2232            // See if candidate still possible
     2233            if (branch_) {
     2234              const CbcObject * object = model->object(bestChoice);
     2235              int preferredWay;
     2236              double infeasibility = object->infeasibility(preferredWay);
     2237              if (!infeasibility) {
     2238                // take out
     2239                delete branch_;
     2240                branch_=NULL;
     2241              } else {
     2242                branch_->way(preferredWay);
     2243              }
     2244            }
     2245          } else {
     2246            anyAction=-2;
     2247            finished=true;
     2248          }
     2249          // If  fixed then round again
     2250          if (!branch_) {
     2251            finished=false;
     2252          }
     2253          // If these in then different action
     2254#if 0
     2255          //if (!anyAction)
     2256          //anyAction=-1;
     2257          //finished=true;
     2258#endif
     2259        }
     2260      }
     2261      delete ws;
     2262    }
     2263  }
     2264 
     2265  // Set guessed solution value
     2266  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
     2267/*
     2268  Cleanup, then we're outta here.
     2269*/
     2270  if (!model->branchingMethod())
     2271    delete decision;
     2272   
     2273  delete [] fixObject;
     2274  delete [] sort;
     2275  delete [] whichObject;
     2276  delete [] saveLower;
     2277  delete [] saveUpper;
     2278 
     2279  // restore solution
     2280  solver->setColSolution(saveSolution);
     2281  model->reserveCurrentSolution(saveSolution);
     2282  delete [] saveSolution;
     2283  return anyAction;
     2284}
     2285
    18132286
    18142287CbcNode::CbcNode(const CbcNode & rhs)
  • trunk/CbcStrategy.cpp

    r116 r135  
    4242CbcStrategyDefault::CbcStrategyDefault(bool cutsOnlyAtRoot,
    4343                                       int numberStrong,
     44                                       int numberBeforeTrust,
    4445                                       int printLevel)
    4546  :CbcStrategy(),
    4647   cutsOnlyAtRoot_(cutsOnlyAtRoot),
    4748   numberStrong_(numberStrong),
     49   numberBeforeTrust_(numberBeforeTrust),
    4850   printLevel_(printLevel)
    4951{
     
    6971  cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
    7072  numberStrong_(rhs.numberStrong_),
     73  numberBeforeTrust_(rhs.numberBeforeTrust_),
    7174  printLevel_(rhs.printLevel_)
    7275{
     
    8386  CglProbing generator1;
    8487  generator1.setUsingObjective(true);
    85   generator1.setMaxPass(3);
     88  generator1.setMaxPass(1);
    8689  // Number of unsatisfied variables to look at
    8790  generator1.setMaxProbe(10);
    8891  // How far to follow the consequences
    89   generator1.setMaxLook(50);
     92  generator1.setMaxLook(10);
    9093  // Only look at rows with fewer than this number of elements
    9194  generator1.setMaxElements(200);
    92   generator1.setRowCuts(3);
     95  //generator1.setRowCuts(3);
    9396
    9497  CglGomory generator2;
     
    113116  // Add in generators
    114117  int setting = cutsOnlyAtRoot_ ? -99 : -1;
    115 
    116   model.addCutGenerator(&generator1,setting,"Probing");
    117   model.addCutGenerator(&generator2,setting,"Gomory");
    118   model.addCutGenerator(&generator3,setting,"Knapsack");
    119   //model.addCutGenerator(&generator4,setting,"OddHole");
    120   model.addCutGenerator(&generator5,setting,"Clique");
    121   model.addCutGenerator(&flowGen,setting,"FlowCover");
    122   model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding");
    123   // Say we want timings
    124118  int numberGenerators = model.numberCutGenerators();
    125119  int iGenerator;
    126   for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     120  bool found;
     121  found=false;
     122  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     123    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     124    CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
     125    if (cgl) {
     126      found=true;
     127      break;
     128    }
     129  }
     130  if (!found)
     131    model.addCutGenerator(&generator1,setting,"Probing");
     132  found=false;
     133  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     134    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     135    CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
     136    if (cgl) {
     137      found=true;
     138      break;
     139    }
     140  }
     141  if (!found)
     142  model.addCutGenerator(&generator2,setting,"Gomory");
     143  found=false;
     144  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     145    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     146    CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
     147    if (cgl) {
     148      found=true;
     149      break;
     150    }
     151  }
     152  if (!found)
     153    model.addCutGenerator(&generator3,setting,"Knapsack");
     154  //model.addCutGenerator(&generator4,setting,"OddHole");
     155  found=false;
     156  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     157    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     158    CglClique * cgl = dynamic_cast<CglClique *>(generator);
     159    if (cgl) {
     160      found=true;
     161      break;
     162    }
     163  }
     164  if (!found)
     165    model.addCutGenerator(&generator5,setting,"Clique");
     166  found=false;
     167  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     168    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     169    CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
     170    if (cgl) {
     171      found=true;
     172      break;
     173    }
     174  }
     175  if (!found)
     176    model.addCutGenerator(&flowGen,setting,"FlowCover");
     177  found=false;
     178  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
     179    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
     180    CglMixedIntegerRounding * cgl = dynamic_cast<CglMixedIntegerRounding *>(generator);
     181    if (cgl) {
     182      found=true;
     183      break;
     184    }
     185  }
     186  if (!found)
     187    model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding");
     188  // Say we want timings
     189  int newNumberGenerators = model.numberCutGenerators();
     190  for (iGenerator=numberGenerators;iGenerator<newNumberGenerators;iGenerator++) {
    127191    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
    128192    generator->setTiming(true);
     
    142206
    143207  CbcRounding heuristic1(model);
    144   model.addHeuristic(&heuristic1);
     208  int numberHeuristics = model.numberHeuristics();
     209  int iHeuristic;
     210  bool found;
     211  found=false;
     212  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
     213    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
     214    CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
     215    if (cgl) {
     216      found=true;
     217      break;
     218    }
     219  }
     220  if (!found)
     221    model.addHeuristic(&heuristic1);
    145222}
    146223// Do printing stuff
     
    163240{
    164241  model.setNumberStrong(numberStrong_);
     242  model.setNumberBeforeTrust(numberBeforeTrust_);
    165243}
    166244
  • trunk/CbcTree.cpp

    r54 r135  
    6666{
    6767  return nodes_.empty();
     68}
     69// Gets best node and takes off heap
     70CbcNode *
     71CbcTree::bestNode(double cutoff)
     72{
     73  CbcNode * best = NULL;
     74  while (!best&&nodes_.size()) {
     75    best = nodes_.front();
     76    if (best)
     77      assert (best->nodeInfo()->numberBranchesLeft());
     78    if (!best||best->objectiveValue()>=cutoff) {
     79      // take off
     80      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     81      nodes_.pop_back();
     82      best=NULL;
     83    }
     84  }
     85  if (best&&comparison_.test_->fullScan()) {
     86    CbcNode * saveBest=best;
     87    int n=nodes_.size();
     88    int iBest=-1;
     89    for (int i=0;i<n;i++) {
     90      if (nodes_[i])
     91        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
     92      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
     93          &&comparison_.alternateTest(best,nodes_[i])) {
     94        best=nodes_[i];
     95        iBest=i;
     96      }
     97    }
     98    if (best==saveBest) {
     99      // can pop
     100      // take off
     101      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     102      nodes_.pop_back();
     103    } else {
     104      // make impossible
     105      nodes_[iBest]=NULL;
     106    }
     107  } else if (best) {
     108    // take off
     109    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     110    nodes_.pop_back();
     111  }
     112  return best;
    68113}
    69114
     
    92137    CbcNode * node = top();
    93138    pop();
    94     double value = node->objectiveValue();
     139    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
    95140    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
    96141    if (value >= cutoff) {
    97       nodeArray[--kDelete] = node;
    98       depth[kDelete] = node->depth();
     142      if (node) {
     143        nodeArray[--kDelete] = node;
     144        depth[kDelete] = node->depth();
     145      }
    99146    } else {
    100147      nodeArray[k++]=node;
     
    159206};
    160207
    161 
     208// Return the best node of the heap using alternate criterion
     209CbcNode *
     210CbcTree::bestAlternate() {
     211  int n=nodes_.size();
     212  CbcNode * best=NULL;
     213  if (n) {
     214    best = nodes_[0];
     215    for (int i=1;i<n;i++) {
     216      if (comparison_.alternateTest(best,nodes_[i])) {
     217        best=nodes_[i];
     218      }
     219    }
     220  }
     221  return best;
     222}
     223
  • trunk/Makefile.Cbc

    r98 r135  
    2020LIBSRC += CbcBranchBase.cpp
    2121LIBSRC += CbcBranchActual.cpp
     22LIBSRC += CbcBranchDynamic.cpp
    2223LIBSRC += CbcBranchLotsize.cpp
    2324LIBSRC += CbcBranchCut.cpp
  • trunk/include/CbcBranchBase.hpp

    r129 r135  
    387387  /** Pass in information on branch just done.
    388388      assumes object can get information from solver */
    389   virtual void updateInformation(OsiSolverInterface * solver) {};
     389  virtual void updateInformation(OsiSolverInterface * solver,
     390                                 const CbcNode * node) {};
    390391
    391392protected:
  • trunk/include/CbcCompareBase.hpp

    r26 r135  
    1111    At present the node list is stored as a heap and the "test"
    1212    comparison function returns true if node y is better than node x.
     13
     14    This is rather inflexible so if the comparison functions wants
     15    it can signal to use alternative criterion on a complete pass
     16    throgh tree.
    1317
    1418*/
     
    3741  virtual bool every1000Nodes(CbcModel * model,int numberNodes) {return false;};
    3842
     43  /// Returns true if wants code to do scan with alternate criterion
     44  virtual bool fullScan() const { return false;};
     45
    3946  virtual ~CbcCompareBase() {};
    4047
     
    5562  virtual bool test (CbcNode * x, CbcNode * y) {return true;};
    5663
     64  /// This is alternate test function
     65  virtual bool alternateTest (CbcNode * x, CbcNode * y) {return test(x,y);};
     66
    5767  bool operator() (CbcNode * x, CbcNode * y) {
    5868    return test(x,y);
     
    7282    return test_->test(x,y);
    7383  }
     84  /// This is alternate test function
     85  inline bool alternateTest (CbcNode * x, CbcNode * y) {return test_->alternateTest(x,y);};
     86
     87  /// return comparison object
     88  inline CbcCompareBase * comparisonObject() const
     89  { return test_;};
    7490};
    7591//#############################################################################
  • trunk/include/CbcModel.hpp

    r132 r135  
    342342
    343343  void findIntegers(bool startAgain);
     344
     345  /** If numberBeforeTrust >0 then we are going to use CbcBranchDynamic.
     346      Scan and convert CbcSimpleInteger objects
     347  */
     348  void convertToDynamic();
    344349 
    345350  //@}
     
    536541  inline int numberStrong() const
    537542  { return numberStrong_;};
     543
     544  /** Set the number of branches before pseudo costs believed
     545      in dynamic strong branching.
     546
     547    A value of 0 disables dynamic strong branching.
     548  */
     549  void setNumberBeforeTrust(int number);
     550  /** get the number of branches before pseudo costs believed
     551      in dynamic strong branching. */
     552  inline int numberBeforeTrust() const
     553  { return numberBeforeTrust_;};
     554  /** Problem type as set by user or found by analysis.  This will be extended
     555      0 - not known
     556      1 - Set partitioning <=
     557      2 - Set partitioning ==
     558      3 - Set covering
     559  */
     560  void inline setProblemType(int number)
     561  { problemType_=number;};
     562  inline int problemType() const
     563  { return problemType_;};
    538564
    539565  /// Set how often to scan global cuts
     
    751777  inline double * currentSolution() const
    752778  { return currentSolution_;};
     779  /** For testing infeasibilities - will point to
     780      currentSolution_ or solver-->getColSolution()
     781  */
     782  inline const double * testSolution() const
     783  { return testSolution_;};
     784  inline void setTestSolution(const double * solution)
     785  { testSolution_ = solution;};
    753786  /// Make sure region there and optionally copy solution
    754787  void reserveCurrentSolution(const double * solution=NULL);
     
    9881021  inline CbcNode * currentNode() const
    9891022  { return currentNode_;};
     1023  /** State of search
     1024      0 - no solution
     1025      1 - only heuristic solutions
     1026      2 - branched to a solution
     1027      3 - no solution but many nodes
     1028  */
     1029  inline int stateOfSearch() const
     1030  { return stateOfSearch_;};
    9901031
    9911032  /// Get the number of cut generators
     
    10421083  inline CbcHeuristic * heuristic(int i) const
    10431084  { return heuristic_[i];};
     1085  /// Get the number of heuristics
     1086  inline int numberHeuristics() const
     1087  { return numberHeuristics_;};
    10441088
    10451089  /** Pass in branching priorities.
     
    12071251  /// Best possible objective
    12081252  double bestPossibleObjective_;
     1253  /// Sum of Changes to objective by first solve
     1254  double sumChangeObjective1_;
     1255  /// Sum of Changes to objective by subsequent solves
     1256  double sumChangeObjective2_;
    12091257
    12101258  /// Array holding the incumbent (best) solution.
     
    12161264  */
    12171265  double * currentSolution_;
    1218 
     1266  /** For testing infeasibilities - will point to
     1267      currentSolution_ or solver-->getColSolution()
     1268  */
     1269  mutable const double * testSolution_;
    12191270  /// Global cuts
    12201271  OsiCuts globalCuts_;
     
    12241275  /// Number of solutions
    12251276  int numberSolutions_;
     1277  /** State of search
     1278      0 - no solution
     1279      1 - only heuristic solutions
     1280      2 - branched to a solution
     1281      3 - no solution but many nodes
     1282  */
     1283  int stateOfSearch_;
    12261284  /// Hotstart strategy 0 =off, 1=branch if incorrect,2=branch even if correct, ....
    12271285  int hotstartStrategy_;
     
    13131371  */
    13141372  int numberStrong_;
    1315 
     1373  /** The number of branches before pseudo costs believed
     1374      in dynamic strong branching. (0 off) */
     1375  int numberBeforeTrust_;
     1376  /** Problem type as set by user or found by analysis.  This will be extended
     1377      0 - not known
     1378      1 - Set partitioning <=
     1379      2 - Set partitioning ==
     1380      3 - Set covering
     1381  */
     1382  int problemType_;
    13161383  /// Print frequency
    13171384  int printFrequency_;
  • trunk/include/CbcNode.hpp

    r48 r135  
    436436                    CbcNode * lastNode,
    437437                    int numberPassesLeft);
     438  /** Create a branching object for the node - when dynamic pseudo costs
     439
     440    The routine scans the object list of the model and selects a set of
     441    unsatisfied objects as candidates for branching. The candidates are
     442    evaluated, and an appropriate branch object is installed.
     443    This version gives preference in evaluation to variables which
     444    have not been evaluated many times.  It also uses numberStrong
     445    to say give up if last few tries have not changed incumbent.
     446    See Achterberg, Koch and Martin.
     447
     448    The numberPassesLeft is decremented to stop fixing one variable each time
     449    and going on and on (e.g. for stock cutting, air crew scheduling)
     450
     451    If evaluation determines that an object is monotone or infeasible,
     452    the routine returns immediately. In the case of a monotone object,
     453    the branch object has already been called to modify the model.
     454
     455    Return value:
     456    <ul>
     457      <li>  0: A branching object has been installed
     458      <li> -1: A monotone object was discovered
     459      <li> -2: An infeasible object was discovered
     460    </ul>
     461  */
     462  int chooseDynamicBranch (CbcModel * model,
     463                    CbcNode * lastNode,
     464                    int numberPassesLeft);
    438465 
    439466  /// Decrement active cut counts
     
    509536  /// Branching object for this node
    510537  const CbcBranchingObject * branchingObject() const
     538  { return branch_;};
     539  /// Modifiable branching object for this node
     540  CbcBranchingObject * modifiableBranchingObject() const
    511541  { return branch_;};
    512542
  • trunk/include/CbcStrategy.hpp

    r99 r135  
    8787  CbcStrategyDefault (bool cutsOnlyAtRoot=true,
    8888                      int numberStrong=5,
     89                      int numberBeforeTrust=0,
    8990                      int printLevel=0);
    9091
     
    116117  int numberStrong_;
    117118
     119  // Number branches needed to trust with dynamic pseudo costs
     120  int numberBeforeTrust_;
     121
    118122  // Print level 0 little, 1 medium
    119123  int printLevel_;
  • trunk/include/CbcTree.hpp

    r54 r135  
    4545  /// Remove the top node from the heap
    4646  virtual void pop() ;
     47  /// Gets best node and takes off heap
     48  virtual CbcNode * bestNode(double cutoff);
    4749
    4850//@}
     
    8082  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    8183
     84  /// Get best on list using alternate method
     85  CbcNode * bestAlternate();
     86
    8287  /// We may have got an intelligent tree so give it one more chance
    8388  virtual void endSearch() {};
Note: See TracChangeset for help on using the changeset viewer.