source: trunk/Clp/src/ClpPEDualRowDantzig.cpp @ 2470

Last change on this file since 2470 was 2385, checked in by unxusr, 10 months ago

formatting

File size: 10.2 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3/*
4   Authors
5
6   Jeremy Omer
7
8   Last update: april 10, 2015
9
10 */
11
12#include "CoinPragma.hpp"
13#include "ClpPEDualRowDantzig.hpp"
14#include "CoinHelperFunctions.hpp"
15#ifndef CLP_DUAL_COLUMN_MULTIPLIER
16#define CLP_DUAL_COLUMN_MULTIPLIER 1.01
17#endif
18
19//#############################################################################
20// Constructors / Destructor / Assignment
21//#############################################################################
22
23//-------------------------------------------------------------------
24// Default Constructor
25//-------------------------------------------------------------------
26ClpPEDualRowDantzig::ClpPEDualRowDantzig(double psi)
27  : ClpDualRowDantzig()
28  , modelPE_(NULL)
29  , psi_(psi)
30  , iCurrent_(0)
31  , iInterval_(100)
32  , updateCompatibles_(true)
33  , coDegenCompatibles_(0)
34  , coConsecutiveCompatibles_(0)
35{
36}
37
38//-------------------------------------------------------------------
39// Copy constructor
40//-------------------------------------------------------------------
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_;
51}
52
53//-------------------------------------------------------------------
54// Destructor
55//-------------------------------------------------------------------
56ClpPEDualRowDantzig::~ClpPEDualRowDantzig()
57{
58  delete modelPE_;
59}
60
61//----------------------------------------------------------------
62// Assignment operator
63//-------------------------------------------------------------------
64ClpPEDualRowDantzig &
65ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig &rhs)
66{
67  if (this != &rhs) {
68    ClpDualRowDantzig::operator=(rhs);
69    delete modelPE_;
70    modelPE_ = NULL;
71  }
72  return *this;
73}
74
75//-------------------------------------------------------------------
76// Clone
77//-------------------------------------------------------------------
78ClpDualRowPivot *ClpPEDualRowDantzig::clone(bool CopyData) const
79{
80  if (CopyData) {
81    return new ClpPEDualRowDantzig(*this);
82  } else {
83    return new ClpPEDualRowDantzig(psi_);
84  }
85}
86
87// Returns pivot row, -1 if none
88int ClpPEDualRowDantzig::pivotRow()
89{
90  assert(model_);
91
92  /* Determine whether the set of compatible variables should be updated
93*/
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      }
155
156#if PE_DEBUG >= 1
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;
185
186#if PE_DEBUG >= 1
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();
209#ifdef CLP_DUAL_COLUMN_MULTIPLIER
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) {
232#ifdef CLP_DUAL_COLUMN_MULTIPLIER
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    }
262#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  } else
270    modelPE_->isLastPivotCompatible(false);
271  if (modelPE_->doStatistics())
272    modelPE_->stopTimer();
273
274  modelPE_->updateLastObjectiveValue();
275  return chosenRow;
276}
277
278//-------------------------------------------------------------------
279// updateWeights
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;
292}
293/* Save weights - this may initialize weights as well
294   This is as parent but may initialize ClpPESimplex
295*/
296void ClpPEDualRowDantzig::saveWeights(ClpSimplex *model, int mode)
297{
298  // See if we need to initialize ClpPESimplex
299  if (!modelPE_ || model != modelPE_->clpModel()) {
300    delete modelPE_;
301    modelPE_ = new ClpPESimplex(model);
302  }
303  ClpDualRowDantzig::saveWeights(model, mode);
304}
305
306/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
307*/
Note: See TracBrowser for help on using the repository browser.