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

Last change on this file since 2271 was 2149, checked in by forrest, 4 years ago

add PE code

File size: 9.7 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(), modelPE_(NULL), psi_(psi),
28iCurrent_(0), iInterval_(100), updateCompatibles_(true),
29coDegenCompatibles_(0), coConsecutiveCompatibles_(0)
30{
31}
32
33//-------------------------------------------------------------------
34// Copy constructor
35//-------------------------------------------------------------------
36ClpPEDualRowDantzig::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_;
46}
47
48//-------------------------------------------------------------------
49// Destructor
50//-------------------------------------------------------------------
51ClpPEDualRowDantzig::~ClpPEDualRowDantzig ()
52{
53  delete modelPE_;
54}
55
56//----------------------------------------------------------------
57// Assignment operator
58//-------------------------------------------------------------------
59ClpPEDualRowDantzig &
60ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig& rhs)
61{
62        if (this != &rhs) {
63                ClpDualRowDantzig::operator=(rhs);
64                delete modelPE_;
65                modelPE_=NULL;
66        }
67        return *this;
68}
69
70//-------------------------------------------------------------------
71// Clone
72//-------------------------------------------------------------------
73ClpDualRowPivot * ClpPEDualRowDantzig::clone(bool CopyData) const
74{
75        if (CopyData) {
76                return new ClpPEDualRowDantzig(*this);
77        } else {
78                return new ClpPEDualRowDantzig(psi_);
79        }
80}
81
82
83// Returns pivot row, -1 if none
84int
85ClpPEDualRowDantzig::pivotRow()
86{
87        assert(model_);
88
89/* Determine whether the set of compatible variables should be updated
90*/
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        }
154
155#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;
182
183#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();
207#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) {
230#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        }
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        }
270        else
271                modelPE_->isLastPivotCompatible(false);
272        if (modelPE_->doStatistics()) 
273        modelPE_->stopTimer();
274
275        modelPE_->updateLastObjectiveValue();
276        return chosenRow;
277}
278
279
280
281//-------------------------------------------------------------------
282// updateWeights
283// Update the compatible variables and
284// call the base class method to update weights
285//-------------------------------------------------------------------   
286
287double 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;
295}
296/* Save weights - this may initialize weights as well
297   This is as parent but may initialize ClpPESimplex
298*/
299void
300ClpPEDualRowDantzig::saveWeights(ClpSimplex * model, int mode)
301{
302  // See if we need to initialize ClpPESimplex
303  if (!modelPE_||model!=modelPE_->clpModel()) {
304    delete modelPE_;
305    modelPE_ = new ClpPESimplex(model);
306  }
307  ClpDualRowDantzig::saveWeights(model,mode);
308}
309
310
311
Note: See TracBrowser for help on using the repository browser.