Changeset 912


Ignore:
Timestamp:
Jan 17, 2007 9:22:29 AM (14 years ago)
Author:
forrest
Message:

ranging

Location:
trunk/Clp/src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/Clp/src/ClpSimplex.cpp

    r909 r912  
    45584558int ClpSimplex::dualRanging(int numberCheck,const int * which,
    45594559                            double * costIncrease, int * sequenceIncrease,
    4560                             double * costDecrease, int * sequenceDecrease)
     4560                            double * costDecrease, int * sequenceDecrease,
     4561                            double * valueIncrease, double * valueDecrease)
    45614562{
    45624563  int savePerturbation = perturbation_;
     
    45914592  ((ClpSimplexOther *) this)->dualRanging(numberCheck,which,
    45924593                                          costIncrease,sequenceIncrease,
    4593                                           costDecrease,sequenceDecrease);
     4594                                          costDecrease,sequenceDecrease,
     4595                                          valueIncrease, valueDecrease);
    45944596  finish(); // get rid of arrays
    45954597  return 0;
  • trunk/Clp/src/ClpSimplex.hpp

    r909 r912  
    279279      which contains list of variables for which information is desired.  All other
    280280      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
    281       will information for variable 7.
     281      will be information for variable 7.
     282
     283      If valueIncrease/Decrease not NULL (both must be NULL or both non NULL) then these are filled with
     284      the value of variable if such a change in cost were made (the existing bounds are ignored)
    282285
    283286      Returns non-zero if infeasible unbounded etc
     
    285288  int dualRanging(int numberCheck,const int * which,
    286289                  double * costIncrease, int * sequenceIncrease,
    287                   double * costDecrease, int * sequenceDecrease);
     290                  double * costDecrease, int * sequenceDecrease,
     291                  double * valueIncrease=NULL, double * valueDecrease=NULL);
     292
    288293  /** Primal ranging.
    289294      This computes increase/decrease in value for each given variable and corresponding
    290295      sequence numbers which would change basis.  Sequence numbers are 0..numberColumns
    291296      and numberColumns.. for artificials/slacks.
     297      This should only be used for non-basic variabls as otherwise information is pretty useless
    292298      For basic variables the sequence number will be that of the basic variables.
    293299
     
    295301      which contains list of variables for which information is desired.  All other
    296302      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
    297       will information for variable 7.
     303      will be information for variable 7.
    298304
    299305      Returns non-zero if infeasible unbounded etc
  • trunk/Clp/src/ClpSimplexOther.cpp

    r869 r912  
    3535void ClpSimplexOther::dualRanging(int numberCheck,const int * which,
    3636                            double * costIncreased, int * sequenceIncreased,
    37                             double * costDecreased, int * sequenceDecreased)
     37                                  double * costDecreased, int * sequenceDecreased,
     38                                  double * valueIncrease, double * valueDecrease)
    3839{
    3940  rowArray_[1]->clear();
     
    6869    int sequenceIncrease=-1;
    6970    int sequenceDecrease=-1;
     71    if (valueIncrease) {
     72      assert (valueDecrease);
     73      valueIncrease[i]=iSequence<numberColumns_ ? columnActivity_[iSequence] : rowActivity_[iSequence-numberColumns_];
     74      valueDecrease[i]=valueIncrease[i];
     75    }
    7076   
    7177    switch(getStatus(iSequence)) {
     
    8894        checkDualRatios(rowArray_[0],columnArray_[0],costIncrease,sequenceIncrease,alphaIncrease,
    8995                    costDecrease,sequenceDecrease,alphaDecrease);
     96        if (valueIncrease) {
     97          if (sequenceIncrease>=0)
     98            valueIncrease[i] = primalRanging1(sequenceIncrease,iSequence);
     99          if (sequenceDecrease>=0)
     100            valueDecrease[i] = primalRanging1(sequenceDecrease,iSequence);
     101        }
    90102        if (inCBC) {
    91103          if (sequenceIncrease>=0) {
     
    136148      costIncrease = CoinMax(0.0,-dj_[iSequence]);
    137149      sequenceIncrease = iSequence;
     150      if (valueIncrease)
     151        valueIncrease[i] = primalRanging1(iSequence,iSequence);
    138152      break;
    139153    case atLowerBound:
    140154      costDecrease = CoinMax(0.0,dj_[iSequence]);
    141155      sequenceDecrease = iSequence;
     156      if (valueIncrease)
     157        valueDecrease[i] = primalRanging1(iSequence,iSequence);
    142158      break;
    143159    }
     
    176192      costDecreased[i] = costIncrease;
    177193      sequenceDecreased[i] = sequenceIncrease;
     194      if (valueIncrease) {
     195        double temp = valueIncrease[i];
     196        valueIncrease[i]=valueDecrease[i];
     197        valueDecrease[i]=temp;
     198      }
    178199    } else if (optimizationDirection_==0.0) {
    179200      // !!!!!! ???
     
    354375        matrix_->extendUpdated(this,rowArray_[1],0);
    355376        // do ratio test
    356         checkPrimalRatios(rowArray_[1],-1);
     377        checkPrimalRatios(rowArray_[1],1);
    357378        if (pivotRow_>=0) {
    358379          valueIncrease = theta_;
    359380          sequenceIncrease=pivotVariable_[pivotRow_];
    360381        }
    361         directionIn_=-1; // down
    362         checkPrimalRatios(rowArray_[1],1);
     382        checkPrimalRatios(rowArray_[1],-1);
    363383        if (pivotRow_>=0) {
    364384          valueDecrease = theta_;
     
    391411    sequenceDecreased[i] = sequenceDecrease;
    392412  }
     413}
     414// Returns new value of whichOther when whichIn enters basis
     415double
     416ClpSimplexOther::primalRanging1(int whichIn, int whichOther)
     417{
     418  rowArray_[0]->clear();
     419  rowArray_[1]->clear();
     420  int iSequence = whichIn;
     421  double newValue=solution_[whichOther];
     422  double alphaOther=0.0;
     423  Status status = getStatus(iSequence);
     424  assert (status==atLowerBound||status==atUpperBound);
     425  int wayIn = (status==atLowerBound) ? 1 : -1;
     426 
     427  switch(getStatus(iSequence)) {
     428   
     429  case basic:
     430  case isFree:
     431  case superBasic:
     432    assert (whichIn==whichOther);
     433    // Easy
     434    newValue = wayIn>0 ? upper_[iSequence] : lower_[iSequence];
     435    break;
     436  case isFixed:
     437  case atUpperBound:
     438  case atLowerBound:
     439    // Non trivial
     440    {
     441      // Other bound is ignored
     442      unpackPacked(rowArray_[1],iSequence);
     443      factorization_->updateColumn(rowArray_[2],rowArray_[1]);
     444      // Get extra rows
     445      matrix_->extendUpdated(this,rowArray_[1],0);
     446      // do ratio test
     447      double acceptablePivot=1.0e-7;
     448      double * work=rowArray_[1]->denseVector();
     449      int number=rowArray_[1]->getNumElements();
     450      int * which=rowArray_[1]->getIndices();
     451     
     452      // we may need to swap sign
     453      double way = wayIn;
     454      double theta = 1.0e30;
     455      for (int iIndex=0;iIndex<number;iIndex++) {
     456       
     457        int iRow = which[iIndex];
     458        double alpha = work[iIndex]*way;
     459        int iPivot=pivotVariable_[iRow];
     460        if (iPivot==whichOther) {
     461          alphaOther=alpha;
     462          continue;
     463        }
     464        double oldValue = solution_[iPivot];
     465        if (fabs(alpha)>acceptablePivot) {
     466          if (alpha>0.0) {
     467            // basic variable going towards lower bound
     468            double bound = lower_[iPivot];
     469            oldValue -= bound;
     470            if (oldValue-theta*alpha<0.0) {
     471              theta = CoinMax(0.0,oldValue/alpha);
     472            }
     473          } else {
     474            // basic variable going towards upper bound
     475            double bound = upper_[iPivot];
     476            oldValue = oldValue-bound;
     477            if (oldValue-theta*alpha>0.0) {
     478              theta = CoinMax(0.0,oldValue/alpha);
     479            }
     480          }
     481        }
     482      }
     483      if (whichIn!=whichOther) {
     484        if (theta<1.0e30)
     485          newValue -= theta*alphaOther;
     486        else
     487          newValue = alphaOther>0.0 ? -1.0e30 : 1.0e30;
     488      } else {
     489        newValue += theta*wayIn;
     490      }
     491    }
     492    rowArray_[1]->clear();
     493    break;
     494  }
     495  double scaleFactor;
     496  if (rowScale_) {
     497    if (whichOther<numberColumns_)
     498      scaleFactor = columnScale_[whichOther]/rhsScale_;
     499    else
     500      scaleFactor = 1.0/(rowScale_[whichOther-numberColumns_]*rhsScale_);
     501  } else {
     502    scaleFactor = 1.0/rhsScale_;
     503  }
     504  if (newValue<1.0e29)
     505    if (newValue>-1.0e29)
     506      newValue *= scaleFactor;
     507    else
     508      newValue = -COIN_DBL_MAX;
     509  else
     510    newValue = COIN_DBL_MAX;
     511  return newValue;
    393512}
    394513/*
  • trunk/Clp/src/ClpSimplexOther.hpp

    r754 r912  
    3939      which contains list of variables for which information is desired.  All other
    4040      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
    41       will information for variable 7.
     41      will be information for variable 7.
     42
     43      If valueIncrease/Decrease not NULL (both must be NULL or both non NULL) then these are filled with
     44      the value of variable if such a change in cost were made (the existing bounds are ignored)
    4245
    4346      When here - guaranteed optimal
    4447  */
    4548  void dualRanging(int numberCheck,const int * which,
    46                   double * costIncrease, int * sequenceIncrease,
    47                   double * costDecrease, int * sequenceDecrease);
     49                   double * costIncrease, int * sequenceIncrease,
     50                   double * costDecrease, int * sequenceDecrease,
     51                   double * valueIncrease=NULL, double * valueDecrease=NULL);
     52
    4853  /** Primal ranging.
    4954      This computes increase/decrease in value for each given variable and corresponding
    5055      sequence numbers which would change basis.  Sequence numbers are 0..numberColumns
    5156      and numberColumns.. for artificials/slacks.
     57      This should only be used for non-basic variabls as otherwise information is pretty useless
    5258      For basic variables the sequence number will be that of the basic variables.
    5359
     
    5561      which contains list of variables for which information is desired.  All other
    5662      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
    57       will information for variable 7.
     63      will be information for variable 7.
    5864
    5965      When here - guaranteed optimal
     
    7985                  const double * changeLowerRhs, const double * changeUpperRhs,
    8086                  const double * changeObjective);
     87private:
    8188  /** Parametrics - inner loop
    8289      This first attempt is when reportIncrement non zero and may
     
    134141  void checkPrimalRatios(CoinIndexedVector * rowArray,
    135142                         int direction);
     143  /// Returns new value of whichOther when whichIn enters basis
     144  double primalRanging1(int whichIn, int whichOther);
     145
     146public:
    136147    /** Write the basis in MPS format to the specified file.
    137148        If writeValues true writes values of structurals
Note: See TracChangeset for help on using the changeset viewer.