# Changeset 92

Ignore:
Timestamp:
Jan 13, 2003 10:05:41 AM (18 years ago)
Message:

Free variables done better (I hope)

Location:
trunk
Files:
6 edited

Unmodified
Removed
• ## trunk/ClpPrimalColumnSteepest.cpp

 r89 case ClpSimplex::isFree: case ClpSimplex::superBasic: if (fabs(value)>tolerance) { // we are going to bias towards free value *= 10.0; if (fabs(value)>1.0e2*tolerance) { // we are going to bias towards free (but only if reasonable) value *= 1000.0; // store square in list if (infeas[iSequence+addSequence]) case ClpSimplex::isFree: case ClpSimplex::superBasic: if (fabs(value)>tolerance) { // we are going to bias towards free value *= 10.0; if (fabs(value)>1.0e2*tolerance) { // we are going to bias towards free (but only if reasonable) value *= 1000.0; // store square in list if (infeas[sequenceOut]) case ClpSimplex::isFree: if (fabs(value)>tolerance) { // we are going to bias towards free value *= 10.0; // we are going to bias towards free (but only if reasonable) value *= 1000.0; // store square in list if (infeas[iSequence+addSequence]) case ClpSimplex::isFree: case ClpSimplex::superBasic: if (fabs(value)>tolerance) { if (fabs(value)>1.0e2*tolerance) { // we are going to bias towards free (but only if reasonable) // store square in list infeasible_->quickAdd(iSequence,value*value); infeasible_->quickAdd(iSequence,1.0e6*value*value); } break;
• ## trunk/ClpSimplex.cpp

 r85 numberFake_(0), progressFlag_(0), firstFree_(-1), sumOfRelaxedDualInfeasibilities_(0.0), sumOfRelaxedPrimalInfeasibilities_(0.0) solveType -= 10; } #ifdef CLP_DEBUG if (solveType==1) { int numberFreeIn=0,numberFreeOut=0; double biggestDj=0.0; for (iColumn=0;iColumnlargeValue_) numberFreeIn++; break; default: if (columnLower_[iColumn]<-largeValue_ &&columnUpper_[iColumn]>largeValue_) { numberFreeOut++; biggestDj = max(fabs(dj_[iColumn]),biggestDj); } break; } } if (numberFreeIn+numberFreeOut) printf("%d in basis, %d out - largest dj %g\n", numberFreeIn,numberFreeOut,biggestDj); } #endif if (!solveType) { if (!valuesPass) { } totalSlacks=numberBasic; for (iColumn=0;iColumnprimalTolerance_) { // Check if "free" if (firstFree_<0&&distanceDown>primalTolerance_) { if (algorithm_>0) { // primal firstFree_ = iColumn; } else if (fabs(value)>1.0e2*relaxedTolerance) { // dual with dj firstFree_ = iColumn; } } // should not be negative if (value<0.0) { value = - value; if (value>columnDualInfeasibility_) { columnDualInfeasibility_=value; columnDualSequence_=iColumn; } if (value>dualTolerance_) { if (getColumnStatus(iColumn) != isFree) { numberDualInfeasibilitiesWithoutFree_ ++; sumDualInfeasibilities_ += value-dualTolerance_; if (value>relaxedTolerance) sumOfRelaxedDualInfeasibilities_ += value-relaxedTolerance; numberDualInfeasibilities_ ++; } else { // free so relax a lot value *= 0.01; if (value>dualTolerance_) { sumDualInfeasibilities_ += value-dualTolerance_; if (value>relaxedTolerance) sumOfRelaxedDualInfeasibilities_ += value-relaxedTolerance; numberDualInfeasibilities_ ++; } } // maybe we can make feasible by increasing tolerance if (distanceUpprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distanceUp; } else { //gap too big for any tolerance remainingDualInfeasibility_= max(remainingDualInfeasibility_,value); } } } } if (distanceDown>primalTolerance_) { // should not be positive if (value>0.0) { if (value>columnDualInfeasibility_) { columnDualInfeasibility_=value; columnDualSequence_=iColumn; } if (value>dualTolerance_) { sumDualInfeasibilities_ += value-dualTolerance_; if (value>relaxedTolerance) sumOfRelaxedDualInfeasibilities_ += value-relaxedTolerance; numberDualInfeasibilities_ ++; if (getColumnStatus(iColumn) != isFree) numberDualInfeasibilitiesWithoutFree_ ++; // maybe we can make feasible by increasing tolerance if (distanceDownprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distanceDown; } } } } } for (iRow=0;iRowprimalTolerance_) { double distanceUp = rowUpperWork_[iRow]-rowActivityWork_[iRow]; double distanceDown = rowActivityWork_[iRow] -rowLowerWork_[iRow]; if (distanceUp>primalTolerance_) { // Check if "free" if (firstFree_<0&&distanceDown>primalTolerance_) { if (algorithm_>0) { // primal firstFree_ = iRow+numberColumns_; } else if (fabs(value)>1.0e2*relaxedTolerance) { // dual with dj firstFree_ = iRow+numberColumns_; } } // should not be negative if (value<0.0) { numberDualInfeasibilitiesWithoutFree_ ++; // maybe we can make feasible by increasing tolerance if (distanceprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distance; if (distanceUpprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distanceUp; } else { //gap too big for any tolerance } } distance = solution[iRow] -rowLowerWork_[iRow]; if (distance>primalTolerance_) { if (distanceDown>primalTolerance_) { // should not be positive if (value>0.0) { numberDualInfeasibilitiesWithoutFree_ ++; // maybe we can make feasible by increasing tolerance if (distanceprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distance; } } } } } solution = columnActivityWork_; for (iColumn=0;iColumnprimalTolerance_) { // should not be negative if (value<0.0) { value = - value; if (value>columnDualInfeasibility_) { columnDualInfeasibility_=value; columnDualSequence_=iColumn; } if (value>dualTolerance_) { sumDualInfeasibilities_ += value-dualTolerance_; if (value>relaxedTolerance) sumOfRelaxedDualInfeasibilities_ += value-relaxedTolerance; numberDualInfeasibilities_ ++; if (getColumnStatus(iColumn) != isFree) numberDualInfeasibilitiesWithoutFree_ ++; // maybe we can make feasible by increasing tolerance if (distanceprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distance; } else { //gap too big for any tolerance remainingDualInfeasibility_= max(remainingDualInfeasibility_,value); } } } } distance = solution[iColumn] -columnLowerWork_[iColumn]; if (distance>primalTolerance_) { // should not be positive if (value>0.0) { if (value>columnDualInfeasibility_) { columnDualInfeasibility_=value; columnDualSequence_=iColumn; } if (value>dualTolerance_) { sumDualInfeasibilities_ += value-dualTolerance_; if (value>relaxedTolerance) sumOfRelaxedDualInfeasibilities_ += value-relaxedTolerance; numberDualInfeasibilities_ ++; if (getColumnStatus(iColumn) != isFree) numberDualInfeasibilitiesWithoutFree_ ++; // maybe we can make feasible by increasing tolerance if (distanceprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distance; if (distanceDownprimalToleranceToGetOptimal_) primalToleranceToGetOptimal_=distanceDown; } }
• ## trunk/ClpSimplexDual.cpp

 r90 factorization_->slackValue(-1.0); factorization_->zeroTolerance(1.0e-13); // might want to do first time - factorization_->pivotTolerance(0.99); // Do Initial factorization int factorizationStatus = internalFactorize(0); if (factorizationStatus<0) return 1; // some error perturb(); double objectiveChange; // for dual we will change bounds using dualBound_ // for this we need clean basis so it is after factorize gutsOfSolution(rowActivityWork_,columnActivityWork_); double objectiveChange; numberFake_ =0; // Number of variables at fake bounds changeBounds(true,NULL,objectiveChange); perturbation_ = savePerturbation; dualBound_ = saveDualBound_; factorization_->relaxAccuracyCheck(1.0); return problemStatus_; } int debugIteration=-1; #endif // if can't trust much and long way from optimal then relax if (largestPrimalError_>10.0) factorization_->relaxAccuracyCheck(min(1.0e2,largestPrimalError_/10.0)); else factorization_->relaxAccuracyCheck(1.0); // status stays at -1 while iterating, >=0 finished, -2 to invert // status -3 to go to top without an invert printf("btran alpha %g, ftran alpha %g\n",btranAlpha,alpha_); #endif double checkValue=1.0e-7; // if can't trust much and long way from optimal then relax if (largestPrimalError_>10.0) checkValue = min(1.0e-4,1.0e-8*largestPrimalError_); if (fabs(btranAlpha)<1.0e-12||fabs(alpha_)<1.0e-12|| fabs(btranAlpha-alpha_)>1.0e-7*(1.0+fabs(alpha_))) { fabs(btranAlpha-alpha_)>checkValue*(1.0+fabs(alpha_))) { handler_->message(CLP_DUAL_CHECK,messages_) <unrollWeights(); if (factorization_->pivots()) { dualRowPivot_->unrollWeights(); problemStatus_=-2; // factorize now rowArray_[0]->clear(); if (fabs(btranAlpha)<1.0e-12||fabs(alpha_)<1.0e-12|| fabs(btranAlpha-alpha_)>1.0e-4*(1.0+fabs(alpha_))) { dualRowPivot_->unrollWeights(); // need to reject something char x = isColumn(sequenceOut_) ? 'C' :'R'; assert(dualOut_<=oldOut); #endif if(dualOut_<0.0&&factorization_->pivots()) { if(dualOut_<0.0&&factorization_->pivots()&& getStatus(sequenceIn_)!=isFree) { // going backwards - factorize dualRowPivot_->unrollWeights(); } } assert(fabs(dualOut_)<1.0e30); assert(fabs(dualOut_)<1.0e50); // if stable replace in basis int updateStatus = factorization_->replaceColumn(rowArray_[2], upper_[iSequence]=newUpperValue; if (newLowerValue > lowerValue) { if (newUpperValue < upperValue) if (newUpperValue < upperValue) { setFakeBound(iSequence,ClpSimplexDual::bothFake); else } else { setFakeBound(iSequence,ClpSimplexDual::lowerFake); } } else { if (newUpperValue < upperValue) setFakeBound(iSequence,ClpSimplexDual::bothFake); } } else { // set non basic free variables to fake bounds // I don't think we should ever get here assert(!("should not be here")); lower_[iSequence]=-0.5*dualBound_; upper_[iSequence]= 0.5*dualBound_; setFakeBound(iSequence,ClpSimplexDual::bothFake); setStatus(iSequence,atUpperBound); solution_[iSequence]=0.5*dualBound_; } } } return 1; } keep = 2; } else { if (alpha>=acceptablePivot) if (fabs(alpha)>10.0*acceptablePivot) keep = 2; else if (-alpha>=acceptablePivot) keep = 2; } break; marker[0][0] = numberRemaining; if (!numberRemaining) if (!numberRemaining&&sequenceIn_<0) return; // Looks infeasible oldValue = dj_[sequenceIn_]; theta_ = oldValue/alpha; #if 0 if (numberIterations_>2000) exit(99); if (numberIterations_>2000-20) handler_->setLogLevel(63); if (numberIterations_>2000-20) printf("theta %g oldValue %g tol %g %g\n",theta_,oldValue,dualTolerance_, newTolerance); #endif if (theta_2000-20) printf("%d alpha %g value %g\n",iSequence,alpha,value); #endif // can't be free here dj_[iSequence] += modification; cost_[iSequence] +=  modification; #if 0 if (numberIterations_>2000-20) printf("%d acost %g mod %g\n",iSequence,cost_[iSequence], modification); #endif #endif } dj_[iSequence] += modification; cost_[iSequence] +=  modification; #if 0 if (numberIterations_>2000-20) printf("%d bcost %g mod %g\n",iSequence,cost_[iSequence], modification); #endif #endif } handler_->printing(numberDualInfeasibilitiesWithoutFree_ message()<
• ## trunk/ClpSimplexPrimal.cpp

 r66 handler_->printing(numberDualInfeasibilitiesWithoutFree_ message()<
• ## trunk/Test/ClpMain.cpp

 r86 ClpDualRowSteepest steep; models[0].setDualRowPivotAlgorithm(steep); models[0].setPrimalTolerance(1.0e-8); models[0].setPrimalTolerance(1.0e-7); ClpPrimalColumnSteepest steepP; models[0].setPrimalColumnPivotAlgorithm(steepP);
• ## trunk/include/ClpSimplex.hpp

 r80 /// Progress flag - at present 0 bit says artificials out int progressFlag_; /// First free/super-basic variable (-1 if none) int firstFree_; /// Sum of Dual infeasibilities using tolerance based on error in duals double sumOfRelaxedDualInfeasibilities_;
Note: See TracChangeset for help on using the changeset viewer.