Changeset 146


Ignore:
Timestamp:
Jun 7, 2005 6:23:45 AM (15 years ago)
Author:
forrest
Message:

for node stats

Location:
trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcModel.cpp

    r143 r146  
    602602  bool resolved = false ;
    603603  CbcNode *newNode = NULL ;
     604/*
     605  For printing totals and for CbcNode (numberNodes_)
     606*/
     607  numberIterations_ = 0 ;
     608  numberNodes_ = 0 ;
    604609
    605610  if (feasible)
    606611  { newNode = new CbcNode ;
    607612    newNode->setObjectiveValue(direction*solver_->getObjValue()) ;
    608     newNode->setNodeNumber(numberNodes_);
    609613    anyAction = -1 ;
    610614    // To make depth available we may need a fake node
     
    707711    for (i = 0;i < numberObjects_;i++)
    708712      object_[i]->resetBounds() ; }
    709 /*
    710   For printing totals and for CbcNode (numberNodes_)
    711 */
    712   numberIterations_ = 0 ;
    713   numberNodes_ = 0 ;
    714713  bool stoppedOnGap = false ;
    715714/*
     
    956955          if (newNode->objectiveValue() >= getCutoff())
    957956            anyAction=-2;
    958           newNode->setNodeNumber(numberNodes_);
    959957          anyAction =-1 ;
    960958          resolved = false ;
     
    968966              anyAction = newNode->chooseBranch(this,node,numberPassesLeft) ;
    969967            } else {
    970               anyAction = newNode->chooseDynamicBranch(this,NULL,numberPassesLeft) ;
     968              anyAction = newNode->chooseDynamicBranch(this,node,numberPassesLeft) ;
    971969              if (anyAction==-3)
    972970                anyAction = newNode->chooseBranch(this,node,numberPassesLeft) ; // dynamic did nothing
     
    27562754    // If at root node and first pass do heuristics without cuts
    27572755    if (!numberNodes_&&currentPassNumber_==1) {
     2756      // Save number solutions
     2757      int saveNumberSolutions = numberSolutions_;
     2758      int saveNumberHeuristicSolutions = numberHeuristicSolutions_;
    27582759      for (int i = 0;i<numberHeuristics_;i++) {
    27592760        // see if heuristic will do anything
     
    27652766          found = i ;
    27662767          incrementUsed(newSolution);
     2768          // increment number of solutions so other heuristics can test
     2769          numberSolutions_++;
     2770          numberHeuristicSolutions_++;
    27672771        } else {
    27682772          heuristicValue = saveValue ;
    27692773        }
    27702774      }
     2775      // Restore number solutions
     2776      numberSolutions_ = saveNumberSolutions;
     2777      numberHeuristicSolutions_ = saveNumberHeuristicSolutions;
    27712778    }
    27722779/*
     
    31763183        // update size of problem
    31773184        numberRowsAtContinuous_ = solver_->getNumRows() ;
    3178         //#ifdef COIN_USE_CLP
    31793185#if 0
    31803186        OsiClpSolverInterface * clpSolver
  • trunk/CbcNode.cpp

    r140 r146  
    3535  owner_(NULL),
    3636  numberCuts_(0),
     37  nodeNumber_(0),
    3738  cuts_(NULL),
    3839  numberRows_(0),
     
    5051  owner_(NULL),
    5152  numberCuts_(0),
     53  nodeNumber_(0),
    5254  cuts_(NULL),
    5355  numberRows_(0),
     
    6870  owner_(rhs.owner_),
    6971  numberCuts_(rhs.numberCuts_),
     72  nodeNumber_(rhs.nodeNumber_),
    7073  cuts_(NULL),
    7174  numberRows_(rhs.numberRows_),
     
    97100  owner_(owner),
    98101  numberCuts_(0),
     102  nodeNumber_(0),
    99103  cuts_(NULL),
    100104  numberRows_(0),
     
    632636  branch_(NULL),
    633637  depth_(-1),
    634   numberUnsatisfied_(0),
    635   nodeNumber_(-1)
     638  numberUnsatisfied_(0)
    636639{
    637640#ifdef CHECK_NODE
     
    647650  branch_(NULL),
    648651  depth_(-1),
    649   numberUnsatisfied_(0),
    650   nodeNumber_(model->getNodeCount())
     652  numberUnsatisfied_(0)
    651653{
    652654#ifdef CHECK_NODE
     
    818820    delete ws;
    819821  }
     822  // Set node number
     823  nodeInfo_->setNodeNumber(model->getNodeCount());
    820824}
    821825
     
    17621766  OsiSolverInterface * solver = model->solver();
    17631767  objectiveValue_ = solver->getObjSense()*solver->getObjValue();
     1768  double cutoff =model->getCutoff();
     1769  double distanceToCutoff = cutoff-objectiveValue_;
    17641770  const double * lower = solver->getColLower();
    17651771  const double * upper = solver->getColUpper();
     
    17821788  if (hotstartStrategy>0)
    17831789    return -3;
     1790  // Pass number
     1791  int kPass=0;
    17841792  int numberColumns = model->getNumCols();
    17851793  double * saveUpper = new double[numberColumns];
    17861794  double * saveLower = new double[numberColumns];
     1795  // Ratio to cutoff for pseudo costs
     1796  double tryStrongPseudo = 0.8*distanceToCutoff;
     1797  // Ratio to cutoff for penalties
     1798  //double tryStrongPenalty = 0.5*distanceToCutoff;
    17871799
    17881800  // Save solution in case heuristics need good solution later
     
    18061818  double * sort = new double[numberObjects];
    18071819  int * whichObject = new int[numberObjects];
    1808   int * whichColumn = new int[2*numberObjects+1];
     1820  int * objectMark = new int[2*numberObjects+1];
    18091821  CbcStrongInfo * fixObject = new CbcStrongInfo[numberObjects];
    18101822  double estimatedDegradation=0.0;
     1823  int numberBeforeTrust = model->numberBeforeTrust();
     1824  int numberPenalties = model->numberPenalties();
     1825  double scaleFactor = model->penaltyScaleFactor();
    18111826  // May go round twice if strong branching fixes all local candidates
    18121827  bool finished=false;
     
    18261841    int iBestGot=-1;
    18271842    double best=0.0;
     1843    int numberNotTrusted=0;
    18281844   
    18291845    // We may go round this loop twice (only if we think we have solution)
     
    18671883        double infeasibility = object->infeasibility(preferredWay);
    18681884        int priorityLevel = object->priority();
    1869         bool gotDown;
    1870         if (dynamicObject->numberTimesDown()) {
     1885        bool gotDown=false;
     1886        int numberThisDown = dynamicObject->numberTimesDown();
     1887        if (numberThisDown) {
    18711888          averageDown += dynamicObject->downDynamicPseudoCost();
    18721889          numberDown++;
    1873           gotDown=true;
    1874         } else {
    1875           gotDown=false;
    1876         }
    1877         bool gotUp;
    1878         if (dynamicObject->numberTimesUp()) {
     1890          if (numberThisDown>=numberBeforeTrust)
     1891            gotDown=true;
     1892        }
     1893        bool gotUp=false;
     1894        int numberThisUp = dynamicObject->numberTimesUp();
     1895        if (numberThisUp) {
    18791896          averageUp += dynamicObject->upDynamicPseudoCost();
    18801897          numberUp++;
    1881           gotUp=true;
    1882         } else {
    1883           gotUp=false;
     1898          if (numberThisUp>=numberBeforeTrust)
     1899            gotUp=true;
    18841900        }
    18851901        if (infeasibility) {
     
    18931909            iBestGot=-1;
    18941910            best=0.0;
     1911            numberNotTrusted=0;
    18951912          } else if (priorityLevel>bestPriority) {
    18961913            continue;
    18971914          }
     1915          if (!gotUp||!gotDown)
     1916            numberNotTrusted++;
    18981917          // Check for suitability based on infeasibility.
    1899           if (gotDown||gotUp) {
     1918          if ((gotDown&&gotUp)&&numberStrong>0) {
    19001919            sort[numberToDo]=-infeasibility;
    19011920            if (infeasibility>best) {
     
    19031922              iBestGot=numberToDo;
    19041923            }
    1905             whichColumn[numberToDo]=-1; // range info not wanted
     1924            if (infeasibility<tryStrongPseudo)
     1925              objectMark[i]=2*numberBeforeTrust; // range info not wanted
     1926            else
     1927              objectMark[i]=numberBeforeTrust; // keep as possible cutoff
    19061928          } else {
    19071929            int iColumn = dynamicObject->columnNumber();
     
    19111933              bestNot = fabs(sort[numberToDo]);
    19121934            }
    1913             whichColumn[numberToDo]=dynamicObject->columnNumber();
     1935            objectMark[i]=numberThisDown+numberThisUp;
    19141936          }
    19151937          whichObject[numberToDo++]=i;
     
    19862008                        model->getDblParam(CbcModel::CbcMaximumSeconds));
    19872009    // also give up if we are looping round too much
    1988     if (hitMaxTime||numberPassesLeft<=0) {
     2010    if (hitMaxTime||numberPassesLeft<=0||!numberNotTrusted) {
    19892011      int iObject = whichObject[bestChoice];
    19902012      CbcObject * object = model->modifiableObject(iObject);
     
    20062028      else
    20072029        averageUp=1.0;
    2008       double weight;
    2009       if (!stateOfSearch)
    2010         weight=0.5;
    2011       else
    2012         weight=0.8;
    20132030      double average = 0.5*(averageUp+averageDown);
    20142031      int iDo;
     2032      // Bias by trust
     2033      int iObj;
     2034      for (iObj=0;iObj<numberToDo;iObj++) {
     2035        int iObject=whichObject[iObj];
     2036        double add = objectMark[iObject];
     2037        if (sort[iObj]<0.0)
     2038          sort[iObj] += add*average;
     2039        else
     2040          sort[iObj] = -CoinMax(sort[iObj]*averageDown,(1.0-sort[iObj])*averageUp);
     2041      }
     2042      // Sort
     2043      CoinSort_2(sort,sort+numberToDo,whichObject);
     2044      int needed2=numberToDo;
    20152045#define RANGING
    20162046#ifdef RANGING
    20172047      OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver);
    2018       if (osiclp&&iBestNot>=0) {
     2048      if (osiclp&&numberPenalties) {
    20192049        // just get those not touched and best and not trusted
     2050        int n=CoinMin(numberPenalties,numberToDo);
     2051        int * which = objectMark+numberObjects+1;
     2052        int i;
    20202053        int needed=0;
    2021         int * which = whichColumn+numberToDo+1;
    2022         int i;
    2023         for ( i=0;i<numberToDo;i++) {
    2024           if (whichColumn[i]>=0) {
    2025             which[needed++]=whichColumn[i];
    2026           }
     2054        for ( i=0;i<n;i++) {
     2055          int iObject=whichObject[i];
     2056          CbcObject * object = model->modifiableObject(iObject);
     2057          CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
     2058            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     2059          which[needed++]=dynamicObject->columnNumber();
    20272060        }
    20282061        which--;
     
    20312064        osiclp->passInRanges(which);
    20322065        // Mark hot start and get ranges
    2033         solver->markHotStart();
     2066        if (kPass) {
     2067          // until can work out why solution can go funny
     2068          int save = osiclp->specialOptions();
     2069          osiclp->setSpecialOptions(save|256);
     2070          solver->markHotStart();
     2071          osiclp->setSpecialOptions(save);
     2072        } else {
     2073          solver->markHotStart();
     2074        }
     2075        kPass++;
    20342076        osiclp->passInRanges(NULL);
     2077        needed2=0;
    20352078        int put=0;
    2036         int get=0;
    2037         const double * downRange=osiclp->downRange();
    2038         const double * upRange=osiclp->upRange();;
    2039         int numberBeforeTrust = model->numberBeforeTrust();
     2079        const double * downCost=osiclp->upRange();
     2080        const double * upCost=osiclp->downRange();;
    20402081        for ( i=0;i<numberToDo;i++) {
    20412082          int iObject = whichObject[i];
     
    20432084          CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
    20442085            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     2086          int iSequence=dynamicObject->columnNumber();
    20452087          double estimate = sort[i];
    2046           bool keep=false;
    2047           if (i==iBestGot) {
    2048             // keep
    2049             keep=true;
    2050             estimate=-COIN_DBL_MAX;
     2088          if (i<needed) {
     2089            // We have looked at penalties
     2090            int iAction=0;
     2091            double value = saveSolution[iSequence];
     2092            value -= floor(value);
     2093            double upPenalty = upCost[i]*(1.0-value);
     2094            double downPenalty = downCost[i]*value;
     2095            if (upPenalty>distanceToCutoff) {
     2096              if(downPenalty>distanceToCutoff) {
     2097                //printf("%d infeas both penalty %g %g\n",iObject,upPenalty,downPenalty);
     2098                iAction=3;
     2099              } else {
     2100                //printf("%d infeas up penalty %g %g\n",iObject,upPenalty,downPenalty);
     2101                iAction=2;
     2102              }
     2103            } else if(downPenalty>distanceToCutoff) {
     2104              //printf("%d infeas down penalty %g %g\n",iObject,upPenalty,downPenalty);
     2105              iAction=1;
     2106            }
     2107            if (iAction) {
     2108              if (iAction==3) {
     2109                //printf("%d infeas both penalty %g %g\n",iObject,upPenalty,downPenalty);
     2110                anyAction=-2;
     2111                break;
     2112              } else if (iAction==2) {
     2113                //printf("%d infeas up penalty %g %g\n",iObject,upPenalty,downPenalty);
     2114                CbcStrongInfo choice;
     2115                choice.objectNumber=iObject;
     2116                choice.fix=-1;
     2117                choice.possibleBranch=object->createBranch(-1);
     2118                fixObject[numberToFix++]=choice;
     2119                if (!anyAction)
     2120                  anyAction=-1;
     2121              } else {
     2122                //printf("%d infeas down penalty %g %g\n",iObject,upPenalty,downPenalty);
     2123                CbcStrongInfo choice;
     2124                choice.objectNumber=iObject;
     2125                choice.fix=1;
     2126                choice.possibleBranch=object->createBranch(1);
     2127                fixObject[numberToFix++]=choice;
     2128                if (!anyAction)
     2129                  anyAction=-1;
     2130              }
     2131            } else {
     2132              double add = objectMark[iObject];
     2133              double trueEstimate = sort[i] - add*average;
     2134              trueEstimate=0.0; // temp
     2135              estimate = trueEstimate-scaleFactor*(upPenalty+downPenalty);
     2136              sort[put]=estimate;
     2137              whichObject[put++]=iObject;
     2138              needed2=put;
     2139            }
    20512140          } else {
    2052             int numberDown = dynamicObject->numberTimesDown();
    2053             int numberUp = dynamicObject->numberTimesUp();
    2054             if (numberDown<numberBeforeTrust||
    2055                 numberUp<numberBeforeTrust) {
    2056               keep=true;
    2057               // make positive
    2058               estimate += best + 0.1*average*(2*numberBeforeTrust-numberUp-numberDown);
    2059               if (whichColumn[i]>=0) {
    2060                 estimate = - (downRange[get]+upRange[get]);
    2061                 get++;
    2062               }
    2063             }
    2064           }
    2065           if (keep) {
    2066             sort[put]=estimate;
     2141            // just estimate
     2142            double add = objectMark[iObject];
     2143            sort[iObj] += add*average;
     2144            double trueEstimate = sort[i] - add*average;
     2145            sort[put]=trueEstimate;
    20672146            whichObject[put++]=iObject;
    20682147          }
     
    20722151        // Mark hot start
    20732152        solver->markHotStart();
     2153        if (solver->isProvenPrimalInfeasible())
     2154          printf("**** Hot start says node infeasible\n");
    20742155        // make sure best will be first
    20752156        if (iBestGot>=0)
     
    20832164        sort[iBestGot]=-COIN_DBL_MAX;
    20842165#endif
    2085       // Sort
    2086       CoinSort_2(sort,sort+numberToDo,whichObject);
     2166      // Actions 0 - exit for repeat, 1 resolve and try old choice,2 exit for continue
     2167#define ACTION 0
     2168#if ACTION<2
     2169      if (anyAction)
     2170        numberToDo=0; // skip as we will be trying again
     2171#endif
     2172      // Sort (but just those re-computed)
     2173      CoinSort_2(sort,sort+needed2,whichObject);
     2174      // Just first if strong off
     2175      if (!numberStrong)
     2176        numberToDo=CoinMin(numberToDo,1);
    20872177      iDo=0;
    20882178      int saveLimit2;
     
    21052195        int canSkip = choice.possibleBranch->fillStrongInfo(choice);
    21062196        // For now always do
    2107         //canSkip=false;
     2197        canSkip=false;
    21082198        if (model->messageHandler()->logLevel()>3)
    21092199          dynamicObject->print(1,choice.possibleBranch->value());
     
    21482238          if (!iStatus) {
    21492239            choice.finishedDown = true ;
    2150             if (newObjectiveValue>=model->getCutoff()) {
     2240            if (newObjectiveValue>=cutoff) {
    21512241              objectiveChange = 1.0e100; // say infeasible
    21522242            } else {
     
    21582248                                       solver->getColSolution()) ;
    21592249                model->incrementUsed(solver->getColSolution());
    2160                 if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2250                cutoff =model->getCutoff();
     2251                if (newObjectiveValue >= cutoff)        //  *new* cutoff
    21612252                  objectiveChange = 1.0e100 ;
    21622253              }
     
    22062297          if (!iStatus) {
    22072298            choice.finishedUp = true ;
    2208             if (newObjectiveValue>=model->getCutoff()) {
     2299            if (newObjectiveValue>=cutoff) {
    22092300              objectiveChange = 1.0e100; // say infeasible
    22102301            } else {
     
    22162307                                       solver->getColSolution()) ;
    22172308                model->incrementUsed(solver->getColSolution());
    2218                 if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2309                cutoff =model->getCutoff();
     2310                if (newObjectiveValue >= cutoff)        //  *new* cutoff
    22192311                  objectiveChange = 1.0e100 ;
    22202312              }
     
    22402332          //     choice.upMovement,choice.finishedUp,choice.numIntInfeasUp,
    22412333          //     choice.numObjInfeasUp);
    2242           hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
    2243                          model->getDblParam(CbcModel::CbcMaximumSeconds));
    2244           if (hitMaxTime) {
    2245             break;
    2246           }
    22472334        }
    22482335   
     
    22902377              bestChoice = choice.objectNumber;
    22912378              whichChoice = iDo;
     2379              if (numberStrong<=1)
     2380                break;
    22922381            } else {
    22932382              delete choice.possibleBranch;
     
    23412430          }
    23422431        }
     2432        // Check max time
     2433        hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
     2434                       model->getDblParam(CbcModel::CbcMaximumSeconds));
     2435        if (hitMaxTime) {
     2436          if (!branch_) {
     2437            // make sure something there
     2438            branch_ = choice.possibleBranch;
     2439            choice.possibleBranch=NULL;
     2440            branch_->way(-1);
     2441            bestChoice = choice.objectNumber;
     2442            whichChoice = iDo;
     2443          }
     2444          for (i = 0 ; i < numberToFix ; i++) {
     2445            delete fixObject[i].possibleBranch;
     2446          }
     2447          anyAction=0;
     2448          break;
     2449        }
    23432450      }
    2344       if (model->messageHandler()->logLevel()>3) {
     2451      if (model->messageHandler()->logLevel()>3||false) {
    23452452        if (anyAction==-2)
    23462453          printf("infeasible\n");
     
    23482455          printf("%d fixed\n",numberToFix);
    23492456        else
    2350           printf("choosing %d iDo %d numberToDo %d\n",bestChoice,whichChoice,numberToDo);
     2457          printf("choosing %d iDo %d iChosenWhen %d numberToDo %d\n",bestChoice,
     2458                 iDo,whichChoice,numberToDo);
    23512459      }
    23522460      // Delete the snapshot
     
    23732481          }
    23742482          bool feasible=true;
     2483#if ACTION <2
    23752484          // can do quick optimality check
    23762485          int easy=2;
     
    24022511            finished=true;
    24032512          }
     2513#endif
    24042514          // If  fixed then round again
    2405           if (!branch_) {
     2515          if (!branch_&&anyAction!=-2) {
    24062516            finished=false;
    24072517          }
    24082518          // If these in then different action
    2409 #if 0
    2410           //if (!anyAction)
    2411           //anyAction=-1;
    2412           //finished=true;
     2519#if ACTION == 1
     2520          if (!anyAction)
     2521            anyAction=-1;
     2522          finished=true;
    24132523#endif
    24142524        }
     
    24212531  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
    24222532/*
    2423   Cleanup, then we're outta here.
     2533  Cleanup, then we're finished
    24242534*/
    24252535  if (!model->branchingMethod())
     
    24292539  delete [] sort;
    24302540  delete [] whichObject;
    2431   delete [] whichColumn;
     2541  delete [] objectMark;
    24322542  delete [] saveLower;
    24332543  delete [] saveUpper;
     
    24582568  depth_ = rhs.depth_;
    24592569  numberUnsatisfied_ = rhs.numberUnsatisfied_;
    2460   nodeNumber_=rhs.nodeNumber_;
    24612570}
    24622571
     
    24782587    depth_ = rhs.depth_;
    24792588    numberUnsatisfied_ = rhs.numberUnsatisfied_;
    2480     nodeNumber_=rhs.nodeNumber_;
    24812589  }
    24822590  return *this;
     
    25472655  double changeInGuessed=branch_->branch(true);
    25482656  guessedObjectiveValue_+= changeInGuessed;
     2657  //#define PRINTIT
     2658#ifdef PRINTIT
     2659  int numberLeft = nodeInfo_->numberBranchesLeft();
     2660  CbcNodeInfo * parent = nodeInfo_->parent();
     2661  int parentNodeNumber = -1;
     2662  if (parent)
     2663    parentNodeNumber = parent->nodeNumber();
     2664  printf("Node number %d, %s, way %d, depth %d, parent node number %d\n",
     2665         nodeInfo_->nodeNumber(),(numberLeft==2) ? "leftBranch" : "rightBranch",
     2666         way(),depth_,parentNodeNumber);
     2667#endif
    25492668  return nodeInfo_->branchedOn();
    25502669}
  • trunk/include/CbcNode.hpp

    r135 r146  
    181181  inline void nullOwner()
    182182  { owner_=NULL;};
     183  const inline CbcNode * owner() const
     184  { return owner_;};
     185  /// The node number
     186  inline int nodeNumber() const
     187  { return nodeNumber_;};
     188  inline void setNodeNumber(int node)
     189  { nodeNumber_=node;};
    183190protected:
    184191
     
    200207  /// Number of row cuts (this node)
    201208  int numberCuts_;
     209
     210  /// The node number
     211  int nodeNumber_;
    202212
    203213  /// Array of pointers to cuts
     
    523533  inline int numberUnsatisfied() const
    524534  {return numberUnsatisfied_;};
    525   /// The node number
    526   inline int nodeNumber() const
    527   { return nodeNumber_;};
    528   inline void setNodeNumber(int node)
    529   { nodeNumber_=node;};
    530535
    531536  // Guessed objective value (for solution)
     
    555560  /// The number of objects unsatisfied at this node.
    556561  int numberUnsatisfied_;
    557   /// The node number
    558   int nodeNumber_;
    559562};
    560563
Note: See TracChangeset for help on using the changeset viewer.