Ignore:
Timestamp:
Jan 6, 2019 2:43:06 PM (3 months ago)
Author:
unxusr
Message:

formatting

File:
1 edited

Legend:

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

    r2149 r2385  
    2525//-------------------------------------------------------------------
    2626ClpPEDualRowDantzig::ClpPEDualRowDantzig(double psi)
    27 : ClpDualRowDantzig(), modelPE_(NULL), psi_(psi),
    28 iCurrent_(0), iInterval_(100), updateCompatibles_(true),
    29 coDegenCompatibles_(0), coConsecutiveCompatibles_(0)
     27  : ClpDualRowDantzig()
     28  , modelPE_(NULL)
     29  , psi_(psi)
     30  , iCurrent_(0)
     31  , iInterval_(100)
     32  , updateCompatibles_(true)
     33  , coDegenCompatibles_(0)
     34  , coConsecutiveCompatibles_(0)
    3035{
    3136}
     
    3439// Copy constructor
    3540//-------------------------------------------------------------------
    36 ClpPEDualRowDantzig::ClpPEDualRowDantzig(const ClpPEDualRowDantzig & source)
    37 : ClpDualRowDantzig(source)
    38 {
    39         modelPE_    = NULL;
    40         psi_        = source.psi_;
    41         iCurrent_  = source.iCurrent_;
    42         iInterval_ = source.iInterval_;
    43         updateCompatibles_ = source.updateCompatibles_;
    44         coDegenCompatibles_ = source.coDegenCompatibles_;
    45         coConsecutiveCompatibles_ = source.coConsecutiveCompatibles_;
     41ClpPEDualRowDantzig::ClpPEDualRowDantzig(const ClpPEDualRowDantzig &source)
     42  : ClpDualRowDantzig(source)
     43{
     44  modelPE_ = NULL;
     45  psi_ = source.psi_;
     46  iCurrent_ = source.iCurrent_;
     47  iInterval_ = source.iInterval_;
     48  updateCompatibles_ = source.updateCompatibles_;
     49  coDegenCompatibles_ = source.coDegenCompatibles_;
     50  coConsecutiveCompatibles_ = source.coConsecutiveCompatibles_;
    4651}
    4752
     
    4954// Destructor
    5055//-------------------------------------------------------------------
    51 ClpPEDualRowDantzig::~ClpPEDualRowDantzig ()
     56ClpPEDualRowDantzig::~ClpPEDualRowDantzig()
    5257{
    5358  delete modelPE_;
     
    5863//-------------------------------------------------------------------
    5964ClpPEDualRowDantzig &
    60 ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig& rhs)
    61 {
    62         if (this != &rhs) {
    63                 ClpDualRowDantzig::operator=(rhs);
    64                 delete modelPE_;
    65                 modelPE_=NULL;
    66         }
    67         return *this;
     65ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig &rhs)
     66{
     67  if (this != &rhs) {
     68    ClpDualRowDantzig::operator=(rhs);
     69    delete modelPE_;
     70    modelPE_ = NULL;
     71  }
     72  return *this;
    6873}
    6974
     
    7176// Clone
    7277//-------------------------------------------------------------------
    73 ClpDualRowPivot * ClpPEDualRowDantzig::clone(bool CopyData) const
    74 {
    75         if (CopyData) {
    76                 return new ClpPEDualRowDantzig(*this);
    77         } else {
    78                 return new ClpPEDualRowDantzig(psi_);
    79         }
    80 }
    81 
     78ClpDualRowPivot *ClpPEDualRowDantzig::clone(bool CopyData) const
     79{
     80  if (CopyData) {
     81    return new ClpPEDualRowDantzig(*this);
     82  } else {
     83    return new ClpPEDualRowDantzig(psi_);
     84  }
     85}
    8286
    8387// Returns pivot row, -1 if none
    84 int
    85 ClpPEDualRowDantzig::pivotRow()
    86 {
    87         assert(model_);
    88 
    89 /* Determine whether the set of compatible variables should be updated
     88int ClpPEDualRowDantzig::pivotRow()
     89{
     90  assert(model_);
     91
     92  /* Determine whether the set of compatible variables should be updated
    9093*/
    91 // store the number of degenerate pivots on compatible variables and the
    92 // overal number of degenerate pivots
    93         double progress = fabs(modelPE_->lastObjectiveValue() - model_->objectiveValue());
    94         bool isLastDegenerate = progress <= 1.0e-12*fabs(model_->objectiveValue()) ? true:false;
    95         if ( isLastDegenerate ) {
    96                 modelPE_->addDegeneratePivot();
    97                 modelPE_->addDegeneratePivotConsecutive();
    98 
    99                 if ( modelPE_->isLastPivotCompatible() ) {
    100                         modelPE_->addDegenerateCompatiblePivot();
    101                 }
    102         }
    103         else {
    104                 modelPE_->resetDegeneratePivotsConsecutive();
    105         }
    106 
    107 // the compatible variables are updated when the number of degenerate pivots
    108 // on compatible variables is more than 20% the overall number of degenerate pivots
    109         if ( modelPE_->isLastPivotCompatible() ) {
    110                 coConsecutiveCompatibles_++;
    111                 if (isLastDegenerate) {
    112                         coDegenCompatibles_++;
    113                         if ( coConsecutiveCompatibles_ >= 10 && 5*coDegenCompatibles_*model_->numberIterations() > modelPE_->coDegeneratePivots()*coConsecutiveCompatibles_ )  {
    114                                 updateCompatibles_ = true;
    115                         }
    116                 }
    117         }
    118 
    119         if (modelPE_->doStatistics()) {
    120 // For results comparison.
    121 // count the number of degenerate variables if psi==1
    122 // add the time spent in counting to the time limit
    123 
    124         modelPE_->startTimer();
    125         if (psi_ >= 1 && iCurrent_ >= 100)  {
    126                 modelPE_->updateDualDegenerates();
    127                 modelPE_->updateDualDegeneratesAvg(100);
    128                 model_->setMaximumSeconds(36000.0+modelPE_->timeCompatibility()-CoinCpuTime());
    129                 iCurrent_ = 0;
    130         }
    131         modelPE_->stopTimer();
    132         }
    133 
    134 // Update the set of compatible variables if necessary
    135 //
    136         if (modelPE_->doStatistics())
    137         modelPE_->startTimer();
    138         double psiTmp = psi_;
    139         if ( (psi_ < 1.0) && (iCurrent_ >= iInterval_) && (updateCompatibles_||iCurrent_ >= 1000) )
    140         {
    141 // the compatible variables are never updated if the last pivot is non degenerate
    142 // this could be counterproductive
    143                 if (isLastDegenerate) {
    144 
    145                         modelPE_->updateDualDegenerates();
    146                         modelPE_->identifyCompatibleRows(model_->rowArray(2),
    147                                                          model_->rowArray(1));
    148 
    149         if (modelPE_->doStatistics()) {
    150 // update the average number of degenerates and compatibles for statistics
    151                         modelPE_->updateDualDegeneratesAvg(iCurrent_);
    152                         modelPE_->updateCompatibleRowsAvg(iCurrent_);   
    153         }
     94  // store the number of degenerate pivots on compatible variables and the
     95  // overal number of degenerate pivots
     96  double progress = fabs(modelPE_->lastObjectiveValue() - model_->objectiveValue());
     97  bool isLastDegenerate = progress <= 1.0e-12 * fabs(model_->objectiveValue()) ? true : false;
     98  if (isLastDegenerate) {
     99    modelPE_->addDegeneratePivot();
     100    modelPE_->addDegeneratePivotConsecutive();
     101
     102    if (modelPE_->isLastPivotCompatible()) {
     103      modelPE_->addDegenerateCompatiblePivot();
     104    }
     105  } else {
     106    modelPE_->resetDegeneratePivotsConsecutive();
     107  }
     108
     109  // the compatible variables are updated when the number of degenerate pivots
     110  // on compatible variables is more than 20% the overall number of degenerate pivots
     111  if (modelPE_->isLastPivotCompatible()) {
     112    coConsecutiveCompatibles_++;
     113    if (isLastDegenerate) {
     114      coDegenCompatibles_++;
     115      if (coConsecutiveCompatibles_ >= 10 && 5 * coDegenCompatibles_ * model_->numberIterations() > modelPE_->coDegeneratePivots() * coConsecutiveCompatibles_) {
     116        updateCompatibles_ = true;
     117      }
     118    }
     119  }
     120
     121  if (modelPE_->doStatistics()) {
     122    // For results comparison.
     123    // count the number of degenerate variables if psi==1
     124    // add the time spent in counting to the time limit
     125
     126    modelPE_->startTimer();
     127    if (psi_ >= 1 && iCurrent_ >= 100) {
     128      modelPE_->updateDualDegenerates();
     129      modelPE_->updateDualDegeneratesAvg(100);
     130      model_->setMaximumSeconds(36000.0 + modelPE_->timeCompatibility() - CoinCpuTime());
     131      iCurrent_ = 0;
     132    }
     133    modelPE_->stopTimer();
     134  }
     135
     136  // Update the set of compatible variables if necessary
     137  //
     138  if (modelPE_->doStatistics())
     139    modelPE_->startTimer();
     140  double psiTmp = psi_;
     141  if ((psi_ < 1.0) && (iCurrent_ >= iInterval_) && (updateCompatibles_ || iCurrent_ >= 1000)) {
     142    // the compatible variables are never updated if the last pivot is non degenerate
     143    // this could be counterproductive
     144    if (isLastDegenerate) {
     145
     146      modelPE_->updateDualDegenerates();
     147      modelPE_->identifyCompatibleRows(model_->rowArray(2),
     148        model_->rowArray(1));
     149
     150      if (modelPE_->doStatistics()) {
     151        // update the average number of degenerates and compatibles for statistics
     152        modelPE_->updateDualDegeneratesAvg(iCurrent_);
     153        modelPE_->updateCompatibleRowsAvg(iCurrent_);
     154      }
    154155
    155156#if PE_DEBUG >= 1
    156                         std::cout << "Number of compatible rows = " << modelPE_->coCompatibleRows() << " ; average  = " << modelPE_->coCompatibleRowsAvg() <<  std::endl;
    157                         std::cout << "Number of degenerates = " << modelPE_->coDualDegenerates() << " ; average  = " << modelPE_->coDualDegeneratesAvg() <<  std::endl;
    158 #endif
    159 
    160 // the checking frequency is modified to reflect what appears to be needed
    161                         if (iCurrent_ == iInterval_) iInterval_ = std::max(50, iInterval_-50);
    162                         else                                                              iInterval_ = std::min(300, iInterval_+50);
    163 
    164 // reset all the indicators that are used to decide whether the compatible
    165 // variables must be updated
    166                         iCurrent_ = 0;
    167                         updateCompatibles_ = false;
    168                         coConsecutiveCompatibles_ = 0;
    169                         coDegenCompatibles_ = 0;
    170                 }
    171                 else    iInterval_++;
    172         }
    173 // otherwise, update the value of the priority factor depending on the number of
    174 // consecutive degenerate pivots
    175 //
    176         else {
    177 // the idea is that when a lot of consecutive pivots are degenerate, there is
    178 // a potentially hign added value in putting a very high priroity on compatible
    179 // variables
    180                 if (modelPE_->coDegeneratePivotsConsecutive() >= 10) {
    181                         psiTmp = 0.01;
     157      std::cout << "Number of compatible rows = " << modelPE_->coCompatibleRows() << " ; average  = " << modelPE_->coCompatibleRowsAvg() << std::endl;
     158      std::cout << "Number of degenerates = " << modelPE_->coDualDegenerates() << " ; average  = " << modelPE_->coDualDegeneratesAvg() << std::endl;
     159#endif
     160
     161      // the checking frequency is modified to reflect what appears to be needed
     162      if (iCurrent_ == iInterval_)
     163        iInterval_ = std::max(50, iInterval_ - 50);
     164      else
     165        iInterval_ = std::min(300, iInterval_ + 50);
     166
     167      // reset all the indicators that are used to decide whether the compatible
     168      // variables must be updated
     169      iCurrent_ = 0;
     170      updateCompatibles_ = false;
     171      coConsecutiveCompatibles_ = 0;
     172      coDegenCompatibles_ = 0;
     173    } else
     174      iInterval_++;
     175  }
     176  // otherwise, update the value of the priority factor depending on the number of
     177  // consecutive degenerate pivots
     178  //
     179  else {
     180    // the idea is that when a lot of consecutive pivots are degenerate, there is
     181    // a potentially hign added value in putting a very high priroity on compatible
     182    // variables
     183    if (modelPE_->coDegeneratePivotsConsecutive() >= 10) {
     184      psiTmp = 0.01;
    182185
    183186#if PE_DEBUG >= 1
    184                         std::cout << "Lower the priority factor to " << psiTmp << std::endl;
    185                         std::cout << "Consecutive degenerate pivots=" << modelPE_->coDegeneratePivotsConsecutive() << std::endl;
    186 #endif
    187                 }
    188         }
    189         iCurrent_++;
    190         if (modelPE_->doStatistics())
    191         modelPE_->stopTimer();
    192 
    193 
    194 // Do the pricing and give priority to dual compatible variables
    195 //
    196         int iRow;
    197         const int * pivotVariable = model_->pivotVariable();
    198         double tolerance = model_->currentPrimalTolerance();
    199 // we can't really trust infeasibilities if there is primal error
    200         if (model_->largestPrimalError() > 1.0e-8)
    201                 tolerance *= model_->largestPrimalError() / 1.0e-8;
    202         double largest = 0.0;
    203         double largestComp = 0.0;
    204         int chosenRow = -1;
    205         int chosenRowComp = -1;
    206         int numberRows = model_->numberRows();
     187      std::cout << "Lower the priority factor to " << psiTmp << std::endl;
     188      std::cout << "Consecutive degenerate pivots=" << modelPE_->coDegeneratePivotsConsecutive() << std::endl;
     189#endif
     190    }
     191  }
     192  iCurrent_++;
     193  if (modelPE_->doStatistics())
     194    modelPE_->stopTimer();
     195
     196  // Do the pricing and give priority to dual compatible variables
     197  //
     198  int iRow;
     199  const int *pivotVariable = model_->pivotVariable();
     200  double tolerance = model_->currentPrimalTolerance();
     201  // we can't really trust infeasibilities if there is primal error
     202  if (model_->largestPrimalError() > 1.0e-8)
     203    tolerance *= model_->largestPrimalError() / 1.0e-8;
     204  double largest = 0.0;
     205  double largestComp = 0.0;
     206  int chosenRow = -1;
     207  int chosenRowComp = -1;
     208  int numberRows = model_->numberRows();
    207209#ifdef CLP_DUAL_COLUMN_MULTIPLIER
    208         int numberColumns = model_->numberColumns();
    209 #endif
    210 
    211 // only check the compatible variables when the bidimensional factor is less than 1
    212 // and the ratio of compatible variables is larger than 0.01
    213 // the percentage of compatible variables is computed as the ratio to the
    214 // smallest number among columns and rows
    215         bool checkCompatibles = true;
    216         double ratioCompatibles = static_cast<double> ( modelPE_->coCompatibleRows())/
    217           static_cast<double> (std::min(model_->numberRows(),model_->numberColumns()));
    218 
    219         if (psi_ >= 1.0|| ratioCompatibles < 0.01) checkCompatibles = false;
    220 
    221 // check the infeasibility of the variables (there is no partial pricing!)
    222         for (iRow = 0; iRow < numberRows; iRow++) {
    223                 int iSequence = pivotVariable[iRow];
    224                 double value = model_->solution(iSequence);
    225                 double lower = model_->lower(iSequence);
    226                 double upper = model_->upper(iSequence);
    227                 double infeas = CoinMax(value - upper , lower - value);
    228                 double largestMax = std::max(psi_*largest, largestComp);
    229                 if (infeas > tolerance) {
     210  int numberColumns = model_->numberColumns();
     211#endif
     212
     213  // only check the compatible variables when the bidimensional factor is less than 1
     214  // and the ratio of compatible variables is larger than 0.01
     215  // the percentage of compatible variables is computed as the ratio to the
     216  // smallest number among columns and rows
     217  bool checkCompatibles = true;
     218  double ratioCompatibles = static_cast< double >(modelPE_->coCompatibleRows()) / static_cast< double >(std::min(model_->numberRows(), model_->numberColumns()));
     219
     220  if (psi_ >= 1.0 || ratioCompatibles < 0.01)
     221    checkCompatibles = false;
     222
     223  // check the infeasibility of the variables (there is no partial pricing!)
     224  for (iRow = 0; iRow < numberRows; iRow++) {
     225    int iSequence = pivotVariable[iRow];
     226    double value = model_->solution(iSequence);
     227    double lower = model_->lower(iSequence);
     228    double upper = model_->upper(iSequence);
     229    double infeas = CoinMax(value - upper, lower - value);
     230    double largestMax = std::max(psi_ * largest, largestComp);
     231    if (infeas > tolerance) {
    230232#ifdef CLP_DUAL_COLUMN_MULTIPLIER
    231                         if (iSequence < numberColumns)
    232                                 infeas *= CLP_DUAL_COLUMN_MULTIPLIER;
    233 #endif
    234                         if (infeas > largestMax ) {
    235                                 if (model_->flagged(iSequence)) {
    236                                 }
    237                                 else if (checkCompatibles && modelPE_->isCompatibleRow(iRow) && infeas > largestComp)   {
    238                                         chosenRowComp = iRow;
    239                                         largestComp = infeas;
    240                                 }
    241                                 else if ( infeas > largest ) {
    242                                         chosenRow = iRow;
    243                                         largest = infeas;
    244                                 }
    245                         }
    246                 }
    247         }
    248 
    249 // choose a compatible or an incompatible row depending on the
    250 // largest values and on the factor of preference psi_
    251         if (modelPE_->doStatistics())
    252         modelPE_->startTimer();
    253         if ( chosenRowComp >= 0 && largestComp >= psiTmp * largest)  {
    254                 chosenRow = chosenRowComp;
    255 
    256         if (modelPE_->doStatistics()) {
    257 // record the number of pivots done on compatible variables
    258 // that would not have been done without positive edge
    259                 if (largestComp < largest)
    260                         modelPE_->addPriorityPivot();
    261         }
     233      if (iSequence < numberColumns)
     234        infeas *= CLP_DUAL_COLUMN_MULTIPLIER;
     235#endif
     236      if (infeas > largestMax) {
     237        if (model_->flagged(iSequence)) {
     238        } else if (checkCompatibles && modelPE_->isCompatibleRow(iRow) && infeas > largestComp) {
     239          chosenRowComp = iRow;
     240          largestComp = infeas;
     241        } else if (infeas > largest) {
     242          chosenRow = iRow;
     243          largest = infeas;
     244        }
     245      }
     246    }
     247  }
     248
     249  // choose a compatible or an incompatible row depending on the
     250  // largest values and on the factor of preference psi_
     251  if (modelPE_->doStatistics())
     252    modelPE_->startTimer();
     253  if (chosenRowComp >= 0 && largestComp >= psiTmp * largest) {
     254    chosenRow = chosenRowComp;
     255
     256    if (modelPE_->doStatistics()) {
     257      // record the number of pivots done on compatible variables
     258      // that would not have been done without positive edge
     259      if (largestComp < largest)
     260        modelPE_->addPriorityPivot();
     261    }
    262262#if PE_DEBUG >= 1
    263                 modelPE_->checkCompatibilityRow(chosenRow);
    264 #endif
    265         }
    266         if ( psi_ < 1 && modelPE_->isCompatibleRow(chosenRow) )  {
    267                 modelPE_->isLastPivotCompatible(true);
    268                 modelPE_->addCompatiblePivot();
    269         }
    270         else
    271                 modelPE_->isLastPivotCompatible(false);
    272         if (modelPE_->doStatistics())
    273         modelPE_->stopTimer();
    274 
    275         modelPE_->updateLastObjectiveValue();
    276         return chosenRow;
    277 }
    278 
    279 
     263    modelPE_->checkCompatibilityRow(chosenRow);
     264#endif
     265  }
     266  if (psi_ < 1 && modelPE_->isCompatibleRow(chosenRow)) {
     267    modelPE_->isLastPivotCompatible(true);
     268    modelPE_->addCompatiblePivot();
     269  } else
     270    modelPE_->isLastPivotCompatible(false);
     271  if (modelPE_->doStatistics())
     272    modelPE_->stopTimer();
     273
     274  modelPE_->updateLastObjectiveValue();
     275  return chosenRow;
     276}
    280277
    281278//-------------------------------------------------------------------
    282279// updateWeights
    283 // Update the compatible variables and 
    284 // call the base class method to update weights 
    285 //-------------------------------------------------------------------   
    286 
    287 double ClpPEDualRowDantzig::updateWeights(CoinIndexedVector * input,
    288         CoinIndexedVector * spare,
    289         CoinIndexedVector * spare2,
    290         CoinIndexedVector * updatedColumn)
    291 {
    292         double value = ClpDualRowDantzig::updateWeights(input, spare, spare2, updatedColumn);
    293 
    294         return value;
     280// Update the compatible variables and
     281// call the base class method to update weights
     282//-------------------------------------------------------------------
     283
     284double ClpPEDualRowDantzig::updateWeights(CoinIndexedVector *input,
     285  CoinIndexedVector *spare,
     286  CoinIndexedVector *spare2,
     287  CoinIndexedVector *updatedColumn)
     288{
     289  double value = ClpDualRowDantzig::updateWeights(input, spare, spare2, updatedColumn);
     290
     291  return value;
    295292}
    296293/* Save weights - this may initialize weights as well
    297294   This is as parent but may initialize ClpPESimplex
    298295*/
    299 void
    300 ClpPEDualRowDantzig::saveWeights(ClpSimplex * model, int mode)
     296void ClpPEDualRowDantzig::saveWeights(ClpSimplex *model, int mode)
    301297{
    302298  // See if we need to initialize ClpPESimplex
    303   if (!modelPE_||model!=modelPE_->clpModel()) {
     299  if (!modelPE_ || model != modelPE_->clpModel()) {
    304300    delete modelPE_;
    305301    modelPE_ = new ClpPESimplex(model);
    306302  }
    307   ClpDualRowDantzig::saveWeights(model,mode);
    308 }
    309 
    310 
    311 
     303  ClpDualRowDantzig::saveWeights(model, mode);
     304}
     305
     306/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
     307*/
Note: See TracChangeset for help on using the changeset viewer.