1 /* $Id: ClpPrimalColumnSteepest.hpp 2385 2019-01-06 19:43:06Z unxusr $ */ 2 // Copyright (C) 2002, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef ClpPrimalColumnSteepest_H 7 #define ClpPrimalColumnSteepest_H 8 9 #include "ClpPrimalColumnPivot.hpp" 10 #include <bitset> 11 12 //############################################################################# 13 class CoinIndexedVector; 14 15 /** Primal Column Pivot Steepest Edge Algorithm Class 16 17 See Forrest-Goldfarb paper for algorithm 18 19 */ 20 21 class ClpPrimalColumnSteepest : public ClpPrimalColumnPivot { 22 23 public: 24 ///@name Algorithmic methods 25 //@{ 26 27 /** Returns pivot column, -1 if none. 28 The Packed CoinIndexedVector updates has cost updates - for normal LP 29 that is just +-weight where a feasibility changed. It also has 30 reduced cost from last iteration in pivot row 31 Parts of operation split out into separate functions for 32 profiling and speed 33 */ 34 virtual int pivotColumn(CoinIndexedVector *updates, 35 CoinIndexedVector *spareRow1, 36 CoinIndexedVector *spareRow2, 37 CoinIndexedVector *spareColumn1, 38 CoinIndexedVector *spareColumn2); 39 /// For quadratic or funny nonlinearities 40 int pivotColumnOldMethod(CoinIndexedVector *updates, 41 CoinIndexedVector *spareRow1, 42 CoinIndexedVector *spareRow2, 43 CoinIndexedVector *spareColumn1, 44 CoinIndexedVector *spareColumn2); 45 /// Just update djs 46 void justDjs(CoinIndexedVector *updates, 47 CoinIndexedVector *spareRow2, 48 CoinIndexedVector *spareColumn1, 49 CoinIndexedVector *spareColumn2); 50 /// Update djs doing partial pricing (dantzig) 51 int partialPricing(CoinIndexedVector *updates, 52 CoinIndexedVector *spareRow2, 53 int numberWanted, 54 int numberLook); 55 /// Update djs, weights for Devex using djs 56 void djsAndDevex(CoinIndexedVector *updates, 57 CoinIndexedVector *spareRow2, 58 CoinIndexedVector *spareColumn1, 59 CoinIndexedVector *spareColumn2); 60 /** Update djs, weights for Steepest using djs 61 sets best sequence (possibly) */ 62 void djsAndSteepest(CoinIndexedVector *updates, 63 CoinIndexedVector *spareRow2, 64 CoinIndexedVector *spareColumn1, 65 CoinIndexedVector *spareColumn2); 66 /// Update djs, weights for Devex using pivot row 67 void djsAndDevex2(CoinIndexedVector *updates, 68 CoinIndexedVector *spareRow2, 69 CoinIndexedVector *spareColumn1, 70 CoinIndexedVector *spareColumn2); 71 /// Update djs, weights for Steepest using pivot row 72 void djsAndSteepest2(CoinIndexedVector *updates, 73 CoinIndexedVector *spareRow2, 74 CoinIndexedVector *spareColumn1, 75 CoinIndexedVector *spareColumn2); 76 /// Update weights for Devex 77 void justDevex(CoinIndexedVector *updates, 78 CoinIndexedVector *spareRow2, 79 CoinIndexedVector *spareColumn1, 80 CoinIndexedVector *spareColumn2); 81 /// Update weights for Steepest 82 void justSteepest(CoinIndexedVector *updates, 83 CoinIndexedVector *spareRow2, 84 CoinIndexedVector *spareColumn1, 85 CoinIndexedVector *spareColumn2); 86 /// Updates two arrays for steepest 87 int transposeTimes2(const CoinIndexedVector *pi1, CoinIndexedVector *dj1, 88 const CoinIndexedVector *pi2, CoinIndexedVector *dj2, 89 CoinIndexedVector *spare, double scaleFactor); 90 91 /// Updates weights - part 1 - also checks accuracy 92 virtual void updateWeights(CoinIndexedVector *input); 93 94 /// Checks accuracy - just for debug 95 void checkAccuracy(int sequence, double relativeTolerance, 96 CoinIndexedVector *rowArray1, 97 CoinIndexedVector *rowArray2); 98 99 /// Initialize weights 100 void initializeWeights(); 101 102 /** Save weights - this may initialize weights as well 103 mode is - 104 1) before factorization 105 2) after factorization 106 3) just redo infeasibilities 107 4) restore weights 108 5) at end of values pass (so need initialization) 109 */ 110 virtual void saveWeights(ClpSimplex *model, int mode); 111 /// redo infeasibilities 112 void redoInfeasibilities(); 113 /// Gets rid of last update 114 virtual void unrollWeights(); 115 /// Gets rid of all arrays 116 virtual void clearArrays(); 117 /// Returns true if would not find any column 118 virtual bool looksOptimal() const; 119 /// Called when maximum pivots changes 120 virtual void maximumPivotsChanged(); 121 //@} 122 123 /**@name gets and sets */ 124 //@{ 125 /// Mode mode() const126 inline int mode() const 127 { 128 return mode_; 129 } 130 /// Set mode setMode(int mode)131 inline void setMode(int mode) 132 { 133 mode_ = mode; 134 } 135 /// square of infeasibility array (just for infeasible columns) infeasible() const136 inline CoinIndexedVector *infeasible() const 137 { 138 return infeasible_; 139 } 140 /// Weights weights() const141 inline const double *weights() const 142 { 143 return weights_; 144 } 145 /// alternate weight array alternateWeights() const146 inline CoinIndexedVector *alternateWeights() const 147 { 148 return alternateWeights_; 149 } 150 /** Returns number of extra columns for sprint algorithm - 0 means off. 151 Also number of iterations before recompute 152 */ 153 virtual int numberSprintColumns(int &numberIterations) const; 154 /// Switch off sprint idea 155 virtual void switchOffSprint(); 156 157 //@} 158 159 /** enums for persistence 160 */ 161 enum Persistence { 162 normal = 0x00, // create (if necessary) and destroy 163 keep = 0x01 // create (if necessary) and leave 164 }; 165 166 ///@name Constructors and destructors 167 //@{ 168 /** Default Constructor 169 0 is exact devex, 1 full steepest, 2 is partial exact devex 170 3 switches between 0 and 2 depending on factorization 171 4 starts as partial dantzig/devex but then may switch between 0 and 2. 172 By partial exact devex is meant that the weights are updated as normal 173 but only part of the nonbasic variables are scanned. 174 This can be faster on very easy problems. 175 */ 176 ClpPrimalColumnSteepest(int mode = 3); 177 178 /// Copy constructor 179 ClpPrimalColumnSteepest(const ClpPrimalColumnSteepest &rhs); 180 181 /// Assignment operator 182 ClpPrimalColumnSteepest &operator=(const ClpPrimalColumnSteepest &rhs); 183 184 /// Destructor 185 virtual ~ClpPrimalColumnSteepest(); 186 187 /// Clone 188 virtual ClpPrimalColumnPivot *clone(bool copyData = true) const; 189 190 //@} 191 192 ///@name Private functions to deal with devex 193 /** reference would be faster using ClpSimplex's status_, 194 but I prefer to keep modularity. 195 */ reference(int i) const196 inline bool reference(int i) const 197 { 198 return ((reference_[i >> 5] >> (i & 31)) & 1) != 0; 199 } setReference(int i,bool trueFalse)200 inline void setReference(int i, bool trueFalse) 201 { 202 unsigned int &value = reference_[i >> 5]; 203 int bit = i & 31; 204 if (trueFalse) 205 value |= (1 << bit); 206 else 207 value &= ~(1 << bit); 208 } 209 /// Set/ get persistence setPersistence(Persistence life)210 inline void setPersistence(Persistence life) 211 { 212 persistence_ = life; 213 } persistence() const214 inline Persistence persistence() const 215 { 216 return persistence_; 217 } 218 219 //@} 220 //--------------------------------------------------------------------------- 221 222 protected: 223 ///@name Protected member data 224 // Update weight 225 double devex_; 226 /// weight array 227 double *weights_; 228 /// square of infeasibility array (just for infeasible columns) 229 CoinIndexedVector *infeasible_; 230 /// alternate weight array (so we can unroll) 231 CoinIndexedVector *alternateWeights_; 232 /// save weight array (so we can use checkpoint) 233 double *savedWeights_; 234 // Array for exact devex to say what is in reference framework 235 unsigned int *reference_; 236 /** Status 237 0) Normal 238 -1) Needs initialization 239 1) Weights are stored by sequence number 240 */ 241 int state_; 242 /** 243 0 is exact devex, 1 full steepest, 2 is partial exact devex 244 3 switches between 0 and 2 depending on factorization 245 4 starts as partial dantzig/devex but then may switch between 0 and 2. 246 5 is always partial dantzig 247 By partial exact devex is meant that the weights are updated as normal 248 but only part of the nonbasic variables are scanned. 249 This can be faster on very easy problems. 250 251 New dubious option is >=10 which does mini-sprint 252 253 */ 254 int mode_; 255 /* Infeasibility state i.e. array of infeasibilities and sequenceIn- 256 0 - correct 257 1 - needs correcting 258 2 - not known but column sequence has been chosen 259 */ 260 int infeasibilitiesState_; 261 /// Life of weights 262 Persistence persistence_; 263 /// Number of times switched from partial dantzig to 0/2 264 int numberSwitched_; 265 // This is pivot row (or pivot sequence round re-factorization) 266 int pivotSequence_; 267 // This is saved pivot sequence 268 int savedPivotSequence_; 269 // This is saved outgoing variable 270 int savedSequenceOut_; 271 // Iteration when last rectified 272 int lastRectified_; 273 // Size of factorization at invert (used to decide algorithm) 274 int sizeFactorization_; 275 //@} 276 }; 277 278 #endif 279 280 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 281 */ 282