Changeset 299


Ignore:
Timestamp:
Apr 6, 2006 3:46:14 PM (14 years ago)
Author:
lou
Message:

addCuts: addCuts: rewrote loop that drops loose cuts; compressRows makes
clear we're not just tweaking status. solveWithCuts: use CbcModel?'s cached
bounds & solution; automatically refreshed on resolve().
FULL_DEBUG -> CBC_CHECK_BASIS

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcModel.cpp

    r295 r299  
    32043204/*
    32053205  adjustCuts might be a better name: If the node is feasible, we sift through
    3206   the cuts we've collected, add the ones that are tight and omit the ones that
    3207   are loose. If the node is infeasible, we just adjust the reference counts to
    3208   reflect that we're about to prune this node and its descendants.
    3209 
    3210   The reason we need to pass in lastws is that OsiClp automagically corrects
    3211   the basis when it deletes constraints. So when all cuts are stripped within
    3212   addCuts1, we lose their basis entries, hence the ability to determine if
    3213   they are loose or tight. The question is whether we really need to pass in
    3214   a basis or if we can capture it here. I'm thinking we can capture it here
    3215   and pass it back out if required.
     3206  the cuts collected by addCuts1, add the ones that are tight and omit the
     3207  ones that are loose. If the node is infeasible, we just adjust the
     3208  reference counts to reflect that we're about to prune this node and its
     3209  descendants.
    32163210*/
    32173211int CbcModel::addCuts (CbcNode *node, CoinWarmStartBasis *&lastws,bool canFix)
     
    32803274/*
    32813275  If the node can't be fathomed by bound, reinstall tight cuts in the
    3282   constraint system.
     3276  constraint system. Even if there are no cuts, we'll want to set the
     3277  reconstructed basis in the solver.
    32833278*/
    32843279  if (node->objectiveValue() < cutoff)
    3285   { int numberToAdd = 0;
    3286     const OsiRowCut * * addCuts;
    3287     if (currentNumberCuts == 0)
    3288       addCuts = NULL;
    3289     else
    3290       addCuts = new const OsiRowCut  * [currentNumberCuts];
    3291 #   ifdef CHECK_CUT_COUNTS
     3280  {
     3281#   ifdef CBC_CHECK_BASIS
    32923282    printf("addCuts: expanded basis; rows %d+%d\n",
    32933283           numberRowsAtContinuous_,currentNumberCuts);
     
    32973287  Adjust the basis and constraint system so that we retain only active cuts.
    32983288  There are three steps:
    3299     1) Scan the basis. If the logical associated with the cut is basic, it's
    3300        loose and we drop it. The status of the logical for tight cuts is
    3301        written back into the status array, compressing as we go.
    3302     2) Resize the basis to fit the number of active cuts, stash a clone, and
    3303        install with a call to setWarmStart().
    3304     3) Install the tight cuts into the constraint system (applyRowCuts).
    3305 
    3306     Update lastws
    3307 */
    3308     int nxrow = lastws->getNumArtificial();
    3309     for (i=0;i<currentNumberCuts;i++) {
    3310       assert (i+numberRowsAtContinuous_<nxrow);
    3311       CoinWarmStartBasis::Status status =
    3312         lastws->getArtifStatus(i+numberRowsAtContinuous_);
    3313       if (addedCuts_[i]&&(status != CoinWarmStartBasis::basic||addedCuts_[i]->effectiveness()==COIN_DBL_MAX)) {
    3314 #       ifdef CHECK_CUT_COUNTS
    3315         printf("Using cut %d %x as row %d\n",i,addedCuts_[i],
    3316                numberRowsAtContinuous_+numberToAdd);
    3317 #       endif
    3318         lastws->setArtifStatus(numberToAdd+numberRowsAtContinuous_,status);
    3319         addCuts[numberToAdd++] = new OsiRowCut(*addedCuts_[i]);
    3320       } else {
    3321 #       ifdef CHECK_CUT_COUNTS
    3322         printf("Dropping cut %d %x\n",i,addedCuts_[i]);
    3323 #       endif
    3324         addedCuts_[i]=NULL;
    3325       }
    3326     }
    3327     int numberRowsNow=numberRowsAtContinuous_+numberToAdd;
    3328     lastws->resize(numberRowsNow,numberColumns);
    3329 #ifdef FULL_DEBUG
    3330     printf("addCuts: stripped basis; rows %d + %d\n",
    3331            numberRowsAtContinuous_,numberToAdd);
    3332     lastws->print();
    3333 #endif
    3334 /*
    3335   Apply the cuts and set the basis in the solver.
    3336 */
    3337     solver_->applyRowCuts(numberToAdd,addCuts);
     3289    1) Scan the basis. Sort the cuts into effective cuts to be kept and
     3290       loose cuts to be dropped.
     3291    2) Drop the loose cuts and resize the basis to fit.
     3292    3) Install the tight cuts in the constraint system (applyRowCuts) and
     3293       and install the basis (setWarmStart).
     3294  Use of compressRows conveys we're compressing the basis and not just
     3295  tweaking the artificialStatus_ array.
     3296*/
     3297    if (currentNumberCuts > 0) {
     3298      int numberToAdd = 0;
     3299      const OsiRowCut **addCuts;
     3300      int numberToDrop = 0 ;
     3301      int *cutsToDrop ;
     3302      addCuts = new const OsiRowCut* [currentNumberCuts];
     3303      cutsToDrop = new int[currentNumberCuts] ;
     3304      int nxrow = lastws->getNumArtificial();
     3305      for (i=0;i<currentNumberCuts;i++) {
     3306        assert (i+numberRowsAtContinuous_<nxrow);
     3307        CoinWarmStartBasis::Status status =
     3308          lastws->getArtifStatus(i+numberRowsAtContinuous_);
     3309        if (addedCuts_[i] &&
     3310            (status != CoinWarmStartBasis::basic ||
     3311             addedCuts_[i]->effectiveness()==COIN_DBL_MAX)) {
     3312#         ifdef CHECK_CUT_COUNTS
     3313          printf("Using cut %d %x as row %d\n",i,addedCuts_[i],
     3314                 numberRowsAtContinuous_+numberToAdd);
     3315#         endif
     3316          addCuts[numberToAdd++] = new OsiRowCut(*addedCuts_[i]);
     3317        } else {
     3318#         ifdef CHECK_CUT_COUNTS
     3319          printf("Dropping cut %d %x\n",i,addedCuts_[i]);
     3320#         endif
     3321          addedCuts_[i]=NULL;
     3322          cutsToDrop[numberToDrop++] = numberRowsAtContinuous_+i ;
     3323        }
     3324      }
     3325      int numberRowsNow=numberRowsAtContinuous_+numberToAdd;
     3326      lastws->compressRows(numberToDrop,cutsToDrop) ;
     3327      lastws->resize(numberRowsNow,numberColumns);
     3328      solver_->applyRowCuts(numberToAdd,addCuts);
     3329#     ifdef CBC_CHECK_BASIS
     3330      printf("addCuts: stripped basis; rows %d + %d\n",
     3331             numberRowsAtContinuous_,numberToAdd);
     3332      lastws->print();
     3333#     endif
     3334      for (i=0;i<numberToAdd;i++)
     3335        delete addCuts[i];
     3336      delete [] addCuts;
     3337      delete [] cutsToDrop ;
     3338    }
     3339/*
     3340  Set the basis in the solver.
     3341*/
    33383342    solver_->setWarmStart(lastws);
    3339 
    33403343#if 0
    33413344    if ((numberNodes_%printFrequency_)==0) {
     
    33483351  Clean up and we're out of here.
    33493352*/
    3350     for (i=0;i<numberToAdd;i++)
    3351       delete addCuts[i];
    3352     delete [] addCuts;
    33533353    numberNodes_++;
    33543354    return 0;
     
    34983498  Resolve the problem. If we've lost feasibility, might as well bail out right
    34993499  after the debug stuff. The resolve will also refresh cached copies of the
    3500   solver solution (cbcColLower_, ...)
     3500  solver solution (cbcColLower_, ...) held by CbcModel.
    35013501*/
    35023502  double objectiveValue = solver_->getObjValue()*solver_->getObjSense();
     
    36163616    OsiCuts theseCuts ;
    36173617/*
    3618   Depending on actions in the loop (bound changes, addition of cuts,
    3619   reoptimisation) these pointers can change.
    3620 */
    3621     const double *lower = solver_->getColLower() ;
    3622     const double *upper = solver_->getColUpper() ;
    3623     const double *solution = solver_->getColSolution() ;
    3624 /*
    36253618  Scan previously generated global column and row cuts to see if any are
    36263619  useful.
     
    36353628      for ( i = 0 ; i < numberCuts ; i++)
    36363629      { const OsiColCut *thisCut = globalCuts_.colCutPtr(i) ;
    3637         if (thisCut->violated(solution)>primalTolerance) {
     3630        if (thisCut->violated(cbcColSolution_)>primalTolerance) {
    36383631          printf("Global cut added - violation %g\n",
    3639                  thisCut->violated(solution)) ;
     3632                 thisCut->violated(cbcColSolution_)) ;
    36403633          whichGenerator_[numberViolated++]=-1;
    36413634          theseCuts.insert(*thisCut) ;
     
    36473640      for ( i = 0;i<numberCuts;i++) {
    36483641        const OsiRowCut * thisCut = globalCuts_.rowCutPtr(i) ;
    3649         if (thisCut->violated(solution)>primalTolerance) {
     3642        if (thisCut->violated(cbcColSolution_)>primalTolerance) {
    36503643          //printf("Global cut added - violation %g\n",
    3651           // thisCut->violated(solution)) ;
     3644          // thisCut->violated(cbcColSolution_)) ;
    36523645          whichGenerator_[numberViolated++]=-1;
    36533646          theseCuts.insert(*thisCut) ;
     
    36673660
    36683661  The need to resolve here should only happen after a heuristic solution.
    3669   However, when it's triggered, the solution may change, which implies a reload
    3670   of lower, upper, and solution. (Note default OSI implementation of
    3671   optimalBasisIsAvailable always returns false.)
    3672 */
    3673     // This should only happen after heuristic solution
     3662  (Note default OSI implementation of optimalBasisIsAvailable always returns
     3663  false.)
     3664*/
    36743665    if (solverCharacteristics_->warmStart()&&
    36753666        !solver_->optimalBasisIsAvailable()) {
    36763667      //printf("XXXXYY no opt basis\n");
    36773668      resolve(node ? node->nodeInfo() : NULL,3);
    3678 /* dylp bug
    3679 
    3680   Need to reload cached solution pointers after resolve. Solver not required
    3681   to use same vector for revised solution. cbcColLower_, etc., set by
    3682   CbcModel::setPointers() in CbcModel::resolve(). Any reason not to convert
    3683   this routine to use cbcColLower_, etc.?
    3684 */
    3685       lower = cbcColLower_ ;
    3686       upper = cbcColUpper_ ;
    3687       solution = cbcColSolution_ ;
    36883669    }
    36893670    if (nextRowCut_) {
     
    36933674        nextRowCut_->print();
    36943675      const OsiRowCut * cut=nextRowCut_;
    3695       // const double * solution = solver_->getColSolution();
    36963676      double lb = cut->lb();
    36973677      double ub = cut->ub();
     
    37033683        int iColumn = column[i];
    37043684        double value = element[i];
    3705         //if (solution[iColumn]>1.0e-7)
    3706         //printf("value of %d is %g\n",iColumn,solution[iColumn]);
    3707         sum += value * solution[iColumn];
     3685        //if (cbcColSolution_[iColumn]>1.0e-7)
     3686        //printf("value of %d is %g\n",iColumn,cbcColSolution_[iColumn]);
     3687        sum += value * cbcColSolution_[iColumn];
    37083688      }
    37093689      delete nextRowCut_;
     
    37533733          if (mustResolve) {
    37543734            int returncode = resolve(node ? node->nodeInfo() : NULL,2);
    3755 /* dylp bug
    3756 
    3757   Need to reload cached solution pointers after resolve. Solver not required
    3758   to use same vector for revised solution.
    3759 */
    3760             lower = cbcColLower_ ;
    3761             upper = cbcColUpper_ ;
    3762             solution = cbcColSolution_ ;
    37633735            feasible = returnCode  != 0 ;
    37643736            if (returncode<0)
     
    38073779        }
    38083780      }
    3809       assert(lower == solver_->getColLower()) ;
    3810       assert(upper == solver_->getColUpper()) ;
    3811       assert(solution == solver_->getColSolution()) ;
    3812 
    38133781/*
    38143782  The cut generator/heuristic has done its thing, and maybe it generated some
     
    38863854      for ( i = 0;i<numberCuts;i++) {
    38873855        const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ;
    3888         if (thisCut->violated(solution)>100.0*primalTolerance) {
     3856        if (thisCut->violated(cbcColSolution_)>100.0*primalTolerance) {
    38893857          if (messageHandler()->logLevel()>2)
    38903858            printf("Old cut added - violation %g\n",
    3891                    thisCut->violated(solution)) ;
     3859                   thisCut->violated(cbcColSolution_)) ;
    38923860          whichGenerator_[numberOld++]=-1;
    38933861          theseCuts.insert(*thisCut) ;
     
    39413909      double * oldLower = new double [numberColumns] ;
    39423910      double * oldUpper = new double [numberColumns] ;
    3943       memcpy(oldLower,lower,numberColumns*sizeof(double)) ;
    3944       memcpy(oldUpper,upper,numberColumns*sizeof(double)) ;
     3911      memcpy(oldLower,cbcColLower_,numberColumns*sizeof(double)) ;
     3912      memcpy(oldUpper,cbcColUpper_,numberColumns*sizeof(double)) ;
    39453913#endif
    39463914
     
    39593927        for (j = 0;j<n;j++) {
    39603928          int iColumn = which[j] ;
    3961           double value = solution[iColumn] ;
     3929          double value = cbcColSolution_[iColumn] ;
    39623930#if CBC_DEBUG>1
    39633931          printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn],
    3964                  solution[iColumn],oldUpper[iColumn],values[j]) ;
     3932                 cbcColSolution_[iColumn],oldUpper[iColumn],values[j]) ;
    39653933#endif
    39663934          solver_->setColLower(iColumn,values[j]) ;
    39673935          if (value<values[j]-integerTolerance)
    39683936            violated = -1 ;
    3969           if (values[j]>upper[iColumn]+integerTolerance) {
     3937          if (values[j]>cbcColUpper_[iColumn]+integerTolerance) {
    39703938            // infeasible
    39713939            violated = -2 ;
     
    39783946        for (j = 0;j<n;j++) {
    39793947          int iColumn = which[j] ;
    3980           double value = solution[iColumn] ;
     3948          double value = cbcColSolution_[iColumn] ;
    39813949#if CBC_DEBUG>1
    39823950          printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn],
    3983                  solution[iColumn],oldUpper[iColumn],values[j]) ;
     3951                 cbcColSolution_[iColumn],oldUpper[iColumn],values[j]) ;
    39843952#endif
    39853953          solver_->setColUpper(iColumn,values[j]) ;
    39863954          if (value>values[j]+integerTolerance)
    39873955            violated = -1 ;
    3988           if (values[j]<lower[iColumn]-integerTolerance) {
     3956          if (values[j]<cbcColLower_[iColumn]-integerTolerance) {
    39893957            // infeasible
    39903958            violated = -2 ;
     
    39963964      delete [] oldLower ;
    39973965      delete [] oldUpper ;
    3998       assert(lower == solver_->getColLower()) ;
    3999       assert(upper == solver_->getColUpper()) ;
    4000       assert(solution == solver_->getColSolution()) ;
    40013966#endif
    40023967    }
     
    41294094          }
    41304095      }
    4131       if (feasible)
    4132         { numberRowsAtStart = numberOldActiveCuts_+numberRowsAtContinuous_ ;
     4096      if (feasible) {
     4097        numberRowsAtStart = numberOldActiveCuts_+numberRowsAtContinuous_ ;
    41334098        lastNumberCuts = numberNewCuts_ ;
    41344099        if (direction*solver_->getObjValue() < lastObjective+minimumDrop &&
     
    41374102        if (numberRowCuts+numberColumnCuts == 0 || cutIterations == 0)
    41384103          { break ; }
    4139         if (numberTries > 0)
    4140           { reducedCostFix() ;
     4104        if (numberTries > 0) {
     4105          reducedCostFix() ;
    41414106          lastObjective = direction*solver_->getObjValue() ;
    4142           lower = solver_->getColLower() ;
    4143           upper = solver_->getColUpper() ;
    4144           solution = solver_->getColSolution() ; } } }
     4107        }
     4108      }
     4109    }
    41454110/*
    41464111  We've lost feasibility --- this node won't be referencing the cuts we've
Note: See TracChangeset for help on using the changeset viewer.