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