Changeset 299
 Timestamp:
 Apr 6, 2006 3:46:14 PM (14 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/CbcModel.cpp
r295 r299 3204 3204 /* 3205 3205 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. 3216 3210 */ 3217 3211 int CbcModel::addCuts (CbcNode *node, CoinWarmStartBasis *&lastws,bool canFix) … … 3280 3274 /* 3281 3275 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. 3283 3278 */ 3284 3279 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 3292 3282 printf("addCuts: expanded basis; rows %d+%d\n", 3293 3283 numberRowsAtContinuous_,currentNumberCuts); … … 3297 3287 Adjust the basis and constraint system so that we retain only active cuts. 3298 3288 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::basicaddedCuts_[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 */ 3338 3342 solver_>setWarmStart(lastws); 3339 3340 3343 #if 0 3341 3344 if ((numberNodes_%printFrequency_)==0) { … … 3348 3351 Clean up and we're out of here. 3349 3352 */ 3350 for (i=0;i<numberToAdd;i++)3351 delete addCuts[i];3352 delete [] addCuts;3353 3353 numberNodes_++; 3354 3354 return 0; … … 3498 3498 Resolve the problem. If we've lost feasibility, might as well bail out right 3499 3499 after the debug stuff. The resolve will also refresh cached copies of the 3500 solver solution (cbcColLower_, ...) 3500 solver solution (cbcColLower_, ...) held by CbcModel. 3501 3501 */ 3502 3502 double objectiveValue = solver_>getObjValue()*solver_>getObjSense(); … … 3616 3616 OsiCuts theseCuts ; 3617 3617 /* 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 /*3625 3618 Scan previously generated global column and row cuts to see if any are 3626 3619 useful. … … 3635 3628 for ( i = 0 ; i < numberCuts ; i++) 3636 3629 { const OsiColCut *thisCut = globalCuts_.colCutPtr(i) ; 3637 if (thisCut>violated( solution)>primalTolerance) {3630 if (thisCut>violated(cbcColSolution_)>primalTolerance) { 3638 3631 printf("Global cut added  violation %g\n", 3639 thisCut>violated( solution)) ;3632 thisCut>violated(cbcColSolution_)) ; 3640 3633 whichGenerator_[numberViolated++]=1; 3641 3634 theseCuts.insert(*thisCut) ; … … 3647 3640 for ( i = 0;i<numberCuts;i++) { 3648 3641 const OsiRowCut * thisCut = globalCuts_.rowCutPtr(i) ; 3649 if (thisCut>violated( solution)>primalTolerance) {3642 if (thisCut>violated(cbcColSolution_)>primalTolerance) { 3650 3643 //printf("Global cut added  violation %g\n", 3651 // thisCut>violated( solution)) ;3644 // thisCut>violated(cbcColSolution_)) ; 3652 3645 whichGenerator_[numberViolated++]=1; 3653 3646 theseCuts.insert(*thisCut) ; … … 3667 3660 3668 3661 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 */ 3674 3665 if (solverCharacteristics_>warmStart()&& 3675 3666 !solver_>optimalBasisIsAvailable()) { 3676 3667 //printf("XXXXYY no opt basis\n"); 3677 3668 resolve(node ? node>nodeInfo() : NULL,3); 3678 /* dylp bug3679 3680 Need to reload cached solution pointers after resolve. Solver not required3681 to use same vector for revised solution. cbcColLower_, etc., set by3682 CbcModel::setPointers() in CbcModel::resolve(). Any reason not to convert3683 this routine to use cbcColLower_, etc.?3684 */3685 lower = cbcColLower_ ;3686 upper = cbcColUpper_ ;3687 solution = cbcColSolution_ ;3688 3669 } 3689 3670 if (nextRowCut_) { … … 3693 3674 nextRowCut_>print(); 3694 3675 const OsiRowCut * cut=nextRowCut_; 3695 // const double * solution = solver_>getColSolution();3696 3676 double lb = cut>lb(); 3697 3677 double ub = cut>ub(); … … 3703 3683 int iColumn = column[i]; 3704 3684 double value = element[i]; 3705 //if ( solution[iColumn]>1.0e7)3706 //printf("value of %d is %g\n",iColumn, solution[iColumn]);3707 sum += value * solution[iColumn];3685 //if (cbcColSolution_[iColumn]>1.0e7) 3686 //printf("value of %d is %g\n",iColumn,cbcColSolution_[iColumn]); 3687 sum += value * cbcColSolution_[iColumn]; 3708 3688 } 3709 3689 delete nextRowCut_; … … 3753 3733 if (mustResolve) { 3754 3734 int returncode = resolve(node ? node>nodeInfo() : NULL,2); 3755 /* dylp bug3756 3757 Need to reload cached solution pointers after resolve. Solver not required3758 to use same vector for revised solution.3759 */3760 lower = cbcColLower_ ;3761 upper = cbcColUpper_ ;3762 solution = cbcColSolution_ ;3763 3735 feasible = returnCode != 0 ; 3764 3736 if (returncode<0) … … 3807 3779 } 3808 3780 } 3809 assert(lower == solver_>getColLower()) ;3810 assert(upper == solver_>getColUpper()) ;3811 assert(solution == solver_>getColSolution()) ;3812 3813 3781 /* 3814 3782 The cut generator/heuristic has done its thing, and maybe it generated some … … 3886 3854 for ( i = 0;i<numberCuts;i++) { 3887 3855 const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ; 3888 if (thisCut>violated( solution)>100.0*primalTolerance) {3856 if (thisCut>violated(cbcColSolution_)>100.0*primalTolerance) { 3889 3857 if (messageHandler()>logLevel()>2) 3890 3858 printf("Old cut added  violation %g\n", 3891 thisCut>violated( solution)) ;3859 thisCut>violated(cbcColSolution_)) ; 3892 3860 whichGenerator_[numberOld++]=1; 3893 3861 theseCuts.insert(*thisCut) ; … … 3941 3909 double * oldLower = new double [numberColumns] ; 3942 3910 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)) ; 3945 3913 #endif 3946 3914 … … 3959 3927 for (j = 0;j<n;j++) { 3960 3928 int iColumn = which[j] ; 3961 double value = solution[iColumn] ;3929 double value = cbcColSolution_[iColumn] ; 3962 3930 #if CBC_DEBUG>1 3963 3931 printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn], 3964 solution[iColumn],oldUpper[iColumn],values[j]) ;3932 cbcColSolution_[iColumn],oldUpper[iColumn],values[j]) ; 3965 3933 #endif 3966 3934 solver_>setColLower(iColumn,values[j]) ; 3967 3935 if (value<values[j]integerTolerance) 3968 3936 violated = 1 ; 3969 if (values[j]> upper[iColumn]+integerTolerance) {3937 if (values[j]>cbcColUpper_[iColumn]+integerTolerance) { 3970 3938 // infeasible 3971 3939 violated = 2 ; … … 3978 3946 for (j = 0;j<n;j++) { 3979 3947 int iColumn = which[j] ; 3980 double value = solution[iColumn] ;3948 double value = cbcColSolution_[iColumn] ; 3981 3949 #if CBC_DEBUG>1 3982 3950 printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn], 3983 solution[iColumn],oldUpper[iColumn],values[j]) ;3951 cbcColSolution_[iColumn],oldUpper[iColumn],values[j]) ; 3984 3952 #endif 3985 3953 solver_>setColUpper(iColumn,values[j]) ; 3986 3954 if (value>values[j]+integerTolerance) 3987 3955 violated = 1 ; 3988 if (values[j]< lower[iColumn]integerTolerance) {3956 if (values[j]<cbcColLower_[iColumn]integerTolerance) { 3989 3957 // infeasible 3990 3958 violated = 2 ; … … 3996 3964 delete [] oldLower ; 3997 3965 delete [] oldUpper ; 3998 assert(lower == solver_>getColLower()) ;3999 assert(upper == solver_>getColUpper()) ;4000 assert(solution == solver_>getColSolution()) ;4001 3966 #endif 4002 3967 } … … 4129 4094 } 4130 4095 } 4131 if (feasible) 4132 {numberRowsAtStart = numberOldActiveCuts_+numberRowsAtContinuous_ ;4096 if (feasible) { 4097 numberRowsAtStart = numberOldActiveCuts_+numberRowsAtContinuous_ ; 4133 4098 lastNumberCuts = numberNewCuts_ ; 4134 4099 if (direction*solver_>getObjValue() < lastObjective+minimumDrop && … … 4137 4102 if (numberRowCuts+numberColumnCuts == 0  cutIterations == 0) 4138 4103 { break ; } 4139 if (numberTries > 0) 4140 {reducedCostFix() ;4104 if (numberTries > 0) { 4105 reducedCostFix() ; 4141 4106 lastObjective = direction*solver_>getObjValue() ; 4142 lower = solver_>getColLower() ;4143 upper = solver_>getColUpper() ; 4144 solution = solver_>getColSolution() ; } }}4107 } 4108 } 4109 } 4145 4110 /* 4146 4111 We've lost feasibility  this node won't be referencing the cuts we've
Note: See TracChangeset
for help on using the changeset viewer.