Changeset 1502 for trunk/Clp/src/ClpDynamicMatrix.hpp
 Timestamp:
 Jan 29, 2010 9:25:07 AM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Clp/src/ClpDynamicMatrix.hpp
r1402 r1502 11 11 class ClpSimplex; 12 12 /** This implements a dynamic matrix when we have a limit on the number of 13 "interesting rows". This version inherits from ClpPackedMatrix and knows that 13 "interesting rows". This version inherits from ClpPackedMatrix and knows that 14 14 the real matrix is gub. A later version could use shortest path to generate columns. 15 15 … … 17 17 18 18 class ClpDynamicMatrix : public ClpPackedMatrix { 19 19 20 20 public: 21 /// enums for status of various sorts22 enum DynamicStatus {23 soloKey = 0x00,24 inSmall = 0x01,25 atUpperBound = 0x02,26 atLowerBound = 0x0327 };28 /**@name Main functions provided */29 //@{30 /// Partial pricing31 virtual void partialPricing(ClpSimplex * model, double start, double end,32 33 34 /**35 update information for a pivot (and effective rhs)36 */37 virtual int updatePivot(ClpSimplex * model,double oldInValue, double oldOutValue);38 /** Returns effective RHS offset if it is being used. This is used for long problems39 or big dynamic or anywhere where going through full columns is40 expensive. This may recompute */41 virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,42 bool check=false);43 44 using ClpPackedMatrix::times ;21 /// enums for status of various sorts 22 enum DynamicStatus { 23 soloKey = 0x00, 24 inSmall = 0x01, 25 atUpperBound = 0x02, 26 atLowerBound = 0x03 27 }; 28 /**@name Main functions provided */ 29 //@{ 30 /// Partial pricing 31 virtual void partialPricing(ClpSimplex * model, double start, double end, 32 int & bestSequence, int & numberWanted); 33 34 /** 35 update information for a pivot (and effective rhs) 36 */ 37 virtual int updatePivot(ClpSimplex * model, double oldInValue, double oldOutValue); 38 /** Returns effective RHS offset if it is being used. This is used for long problems 39 or big dynamic or anywhere where going through full columns is 40 expensive. This may recompute */ 41 virtual double * rhsOffset(ClpSimplex * model, bool forceRefresh = false, 42 bool check = false); 43 44 using ClpPackedMatrix::times ; 45 45 /** Return <code>y + A * scalar *x</code> in <code>y</code>. 46 46 @pre <code>x</code> must be of size <code>numColumns()</code> 47 47 @pre <code>y</code> must be of size <code>numRows()</code> */ 48 virtual void times(double scalar, 49 const double * x, double * y) const; 50 /// Modifies rhs offset 51 void modifyOffset(int sequence, double amount); 52 /// Gets key value when none in small 53 double keyValue(int iSet) const; 54 /** 55 mode=0  Set up before "updateTranspose" and "transposeTimes" for duals using extended 56 updates array (and may use other if dual values pass) 57 mode=1  Update dual solution after "transposeTimes" using extended rows. 58 mode=2  Compute all djs and compute key dual infeasibilities 59 mode=3  Report on key dual infeasibilities 60 mode=4  Modify before updateTranspose in partial pricing 61 */ 62 virtual void dualExpanded(ClpSimplex * model,CoinIndexedVector * array, 63 double * other,int mode); 64 /** 65 mode=0  Create list of nonkey basics in pivotVariable_ using 66 number as numberBasic in and out 67 mode=1  Set all key variables as basic 68 mode=2  return number extra rows needed, number gives maximum number basic 69 mode=3  before replaceColumn 70 mode=4  return 1 if can do primal, 2 if dual, 3 if both 71 mode=5  save any status stuff (when in good state) 72 mode=6  restore status stuff 73 mode=7  flag given variable (normally sequenceIn) 74 mode=8  unflag all variables 75 mode=9  synchronize costs 76 mode=10  return 1 if there may be changing bounds on variable (column generation) 77 mode=11  make sure set is clean (used when a variable rejected  but not flagged) 78 mode=12  after factorize but before permute stuff 79 mode=13  at end of simplex to delete stuff 80 */ 81 virtual int generalExpanded(ClpSimplex * model,int mode,int & number); 82 /** Purely for column generation and similar ideas. Allows 83 matrix and any bounds or costs to be updated (sensibly). 84 Returns nonzero if any changes. 85 */ 86 virtual int refresh(ClpSimplex * model); 87 /** Creates a variable. This is called after partial pricing and will modify matrix. 88 Will update bestSequence. 89 */ 90 virtual void createVariable(ClpSimplex * model, int & bestSequence); 91 /// Returns reduced cost of a variable 92 virtual double reducedCost( ClpSimplex * model,int sequence) const; 93 /// Does gub crash 94 void gubCrash(); 95 /// Populates initial matrix from dynamic status 96 void initialProblem(); 97 /** Adds in a column to gub structure (called from descendant) and returns sequence */ 98 int addColumn(int numberEntries,const int * row, const double * element, 99 double cost, double lower, double upper, int iSet, 100 DynamicStatus status); 101 /** If addColumn forces compression then this allows descendant to know what to do. 102 If >=0 then entry stayed in, if 1 then entry went out to lower bound.of zero. 103 Entries at upper bound (really nonzero) never go out (at present). 104 */ 105 virtual void packDown(const int * , int ) {} 106 /// Gets lower bound (to simplify coding) 107 inline double columnLower(int sequence) const 108 { if (columnLower_) return columnLower_[sequence]; else return 0.0;} 109 /// Gets upper bound (to simplify coding) 110 inline double columnUpper(int sequence) const 111 { if (columnUpper_) return columnUpper_[sequence]; else return COIN_DBL_MAX;} 112 113 //@} 114 115 116 117 /**@name Constructors, destructor */ 118 //@{ 119 /** Default constructor. */ 120 ClpDynamicMatrix(); 121 /** This is the real constructor. 122 It assumes factorization frequency will not be changed. 123 This resizes model !!!! 124 The contents of original matrix in model will be taken over and original matrix 125 will be sanitized so can be deleted (to avoid a very small memory leak) 126 */ 127 ClpDynamicMatrix(ClpSimplex * model, int numberSets, 128 int numberColumns, const int * starts, 129 const double * lower, const double * upper, 130 const int * startColumn, const int * row, 131 const double * element, const double * cost, 132 const double * columnLower=NULL, const double * columnUpper=NULL, 133 const unsigned char * status=NULL, 134 const unsigned char * dynamicStatus=NULL); 135 136 /** Destructor */ 137 virtual ~ClpDynamicMatrix(); 138 //@} 139 140 /**@name Copy method */ 141 //@{ 142 /** The copy constructor. */ 143 ClpDynamicMatrix(const ClpDynamicMatrix&); 144 /** The copy constructor from an CoinPackedMatrix. */ 145 ClpDynamicMatrix(const CoinPackedMatrix&); 146 147 ClpDynamicMatrix& operator=(const ClpDynamicMatrix&); 148 /// Clone 149 virtual ClpMatrixBase * clone() const ; 150 //@} 151 /**@name gets and sets */ 152 //@{ 153 /// Status of row slacks 154 inline ClpSimplex::Status getStatus(int sequence) const 155 {return static_cast<ClpSimplex::Status> (status_[sequence]&7);} 156 inline void setStatus(int sequence, ClpSimplex::Status status) 157 { 158 unsigned char & st_byte = status_[sequence]; 159 st_byte = static_cast<unsigned char>(st_byte & ~7); 160 st_byte = static_cast<unsigned char>(st_byte  status); 161 } 162 /// Number of sets (dynamic rows) 163 inline int numberSets() const 164 { return numberSets_;} 165 /// Whether flagged 166 inline bool flagged(int i) const { 167 return (dynamicStatus_[i]&8)!=0; 168 } 169 inline void setFlagged(int i) { 170 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i]  8); 171 } 172 inline void unsetFlagged(int i) { 173 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i] & ~8); 174 } 175 inline void setDynamicStatus(int sequence, DynamicStatus status) 176 { 177 unsigned char & st_byte = dynamicStatus_[sequence]; 178 st_byte = static_cast<unsigned char>(st_byte & ~7); 179 st_byte = static_cast<unsigned char>(st_byte  status); 180 } 181 inline DynamicStatus getDynamicStatus(int sequence) const 182 {return static_cast<DynamicStatus> (dynamicStatus_[sequence]&7);} 183 /// Saved value of objective offset 184 inline double objectiveOffset() const 185 { return objectiveOffset_;} 186 /// Starts of each column 187 inline CoinBigIndex * startColumn() const 188 { return startColumn_;} 189 /// rows 190 inline int * row() const 191 { return row_;} 192 /// elements 193 inline double * element() const 194 { return element_;} 195 /// costs 196 inline double * cost() const 197 { return cost_;} 198 /// ids of active columns (just index here) 199 inline int * id() const 200 { return id_;} 201 /// Optional lower bounds on columns 202 inline double * columnLower() const 203 { return columnLower_;} 204 /// Optional upper bounds on columns 205 inline double * columnUpper() const 206 { return columnUpper_;} 207 /// Lower bounds on sets 208 inline double * lowerSet() const 209 { return lowerSet_;} 210 /// Upper bounds on sets 211 inline double * upperSet() const 212 { return upperSet_;} 213 /// size 214 inline int numberGubColumns() const 215 { return numberGubColumns_;} 216 /// first free 217 inline int firstAvailable() const 218 { return firstAvailable_;} 219 /// first dynamic 220 inline int firstDynamic() const 221 { return firstDynamic_;} 222 /// number of columns in dynamic model 223 inline int lastDynamic() const 224 { return lastDynamic_;} 225 /// number of rows in original model 226 inline int numberStaticRows() const 227 { return numberStaticRows_;} 228 /// size of working matrix (max) 229 inline int numberElements() const 230 { return numberElements_;} 231 inline int * keyVariable() const 232 { return keyVariable_;} 233 /// Switches off dj checking each factorization (for BIG models) 234 void switchOffCheck(); 235 /// Status region for gub slacks 236 inline unsigned char * gubRowStatus() const 237 { return status_;} 238 /// Status region for gub variables 239 inline unsigned char * dynamicStatus() const 240 { return dynamicStatus_;} 241 /// Returns which set a variable is in 242 int whichSet (int sequence) const; 243 //@} 244 245 48 virtual void times(double scalar, 49 const double * x, double * y) const; 50 /// Modifies rhs offset 51 void modifyOffset(int sequence, double amount); 52 /// Gets key value when none in small 53 double keyValue(int iSet) const; 54 /** 55 mode=0  Set up before "updateTranspose" and "transposeTimes" for duals using extended 56 updates array (and may use other if dual values pass) 57 mode=1  Update dual solution after "transposeTimes" using extended rows. 58 mode=2  Compute all djs and compute key dual infeasibilities 59 mode=3  Report on key dual infeasibilities 60 mode=4  Modify before updateTranspose in partial pricing 61 */ 62 virtual void dualExpanded(ClpSimplex * model, CoinIndexedVector * array, 63 double * other, int mode); 64 /** 65 mode=0  Create list of nonkey basics in pivotVariable_ using 66 number as numberBasic in and out 67 mode=1  Set all key variables as basic 68 mode=2  return number extra rows needed, number gives maximum number basic 69 mode=3  before replaceColumn 70 mode=4  return 1 if can do primal, 2 if dual, 3 if both 71 mode=5  save any status stuff (when in good state) 72 mode=6  restore status stuff 73 mode=7  flag given variable (normally sequenceIn) 74 mode=8  unflag all variables 75 mode=9  synchronize costs 76 mode=10  return 1 if there may be changing bounds on variable (column generation) 77 mode=11  make sure set is clean (used when a variable rejected  but not flagged) 78 mode=12  after factorize but before permute stuff 79 mode=13  at end of simplex to delete stuff 80 */ 81 virtual int generalExpanded(ClpSimplex * model, int mode, int & number); 82 /** Purely for column generation and similar ideas. Allows 83 matrix and any bounds or costs to be updated (sensibly). 84 Returns nonzero if any changes. 85 */ 86 virtual int refresh(ClpSimplex * model); 87 /** Creates a variable. This is called after partial pricing and will modify matrix. 88 Will update bestSequence. 89 */ 90 virtual void createVariable(ClpSimplex * model, int & bestSequence); 91 /// Returns reduced cost of a variable 92 virtual double reducedCost( ClpSimplex * model, int sequence) const; 93 /// Does gub crash 94 void gubCrash(); 95 /// Populates initial matrix from dynamic status 96 void initialProblem(); 97 /** Adds in a column to gub structure (called from descendant) and returns sequence */ 98 int addColumn(int numberEntries, const int * row, const double * element, 99 double cost, double lower, double upper, int iSet, 100 DynamicStatus status); 101 /** If addColumn forces compression then this allows descendant to know what to do. 102 If >=0 then entry stayed in, if 1 then entry went out to lower bound.of zero. 103 Entries at upper bound (really nonzero) never go out (at present). 104 */ 105 virtual void packDown(const int * , int ) {} 106 /// Gets lower bound (to simplify coding) 107 inline double columnLower(int sequence) const { 108 if (columnLower_) return columnLower_[sequence]; 109 else return 0.0; 110 } 111 /// Gets upper bound (to simplify coding) 112 inline double columnUpper(int sequence) const { 113 if (columnUpper_) return columnUpper_[sequence]; 114 else return COIN_DBL_MAX; 115 } 116 117 //@} 118 119 120 121 /**@name Constructors, destructor */ 122 //@{ 123 /** Default constructor. */ 124 ClpDynamicMatrix(); 125 /** This is the real constructor. 126 It assumes factorization frequency will not be changed. 127 This resizes model !!!! 128 The contents of original matrix in model will be taken over and original matrix 129 will be sanitized so can be deleted (to avoid a very small memory leak) 130 */ 131 ClpDynamicMatrix(ClpSimplex * model, int numberSets, 132 int numberColumns, const int * starts, 133 const double * lower, const double * upper, 134 const int * startColumn, const int * row, 135 const double * element, const double * cost, 136 const double * columnLower = NULL, const double * columnUpper = NULL, 137 const unsigned char * status = NULL, 138 const unsigned char * dynamicStatus = NULL); 139 140 /** Destructor */ 141 virtual ~ClpDynamicMatrix(); 142 //@} 143 144 /**@name Copy method */ 145 //@{ 146 /** The copy constructor. */ 147 ClpDynamicMatrix(const ClpDynamicMatrix&); 148 /** The copy constructor from an CoinPackedMatrix. */ 149 ClpDynamicMatrix(const CoinPackedMatrix&); 150 151 ClpDynamicMatrix& operator=(const ClpDynamicMatrix&); 152 /// Clone 153 virtual ClpMatrixBase * clone() const ; 154 //@} 155 /**@name gets and sets */ 156 //@{ 157 /// Status of row slacks 158 inline ClpSimplex::Status getStatus(int sequence) const { 159 return static_cast<ClpSimplex::Status> (status_[sequence]&7); 160 } 161 inline void setStatus(int sequence, ClpSimplex::Status status) { 162 unsigned char & st_byte = status_[sequence]; 163 st_byte = static_cast<unsigned char>(st_byte & ~7); 164 st_byte = static_cast<unsigned char>(st_byte  status); 165 } 166 /// Number of sets (dynamic rows) 167 inline int numberSets() const { 168 return numberSets_; 169 } 170 /// Whether flagged 171 inline bool flagged(int i) const { 172 return (dynamicStatus_[i]&8) != 0; 173 } 174 inline void setFlagged(int i) { 175 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i]  8); 176 } 177 inline void unsetFlagged(int i) { 178 dynamicStatus_[i] = static_cast<unsigned char>(dynamicStatus_[i] & ~8); 179 } 180 inline void setDynamicStatus(int sequence, DynamicStatus status) { 181 unsigned char & st_byte = dynamicStatus_[sequence]; 182 st_byte = static_cast<unsigned char>(st_byte & ~7); 183 st_byte = static_cast<unsigned char>(st_byte  status); 184 } 185 inline DynamicStatus getDynamicStatus(int sequence) const { 186 return static_cast<DynamicStatus> (dynamicStatus_[sequence]&7); 187 } 188 /// Saved value of objective offset 189 inline double objectiveOffset() const { 190 return objectiveOffset_; 191 } 192 /// Starts of each column 193 inline CoinBigIndex * startColumn() const { 194 return startColumn_; 195 } 196 /// rows 197 inline int * row() const { 198 return row_; 199 } 200 /// elements 201 inline double * element() const { 202 return element_; 203 } 204 /// costs 205 inline double * cost() const { 206 return cost_; 207 } 208 /// ids of active columns (just index here) 209 inline int * id() const { 210 return id_; 211 } 212 /// Optional lower bounds on columns 213 inline double * columnLower() const { 214 return columnLower_; 215 } 216 /// Optional upper bounds on columns 217 inline double * columnUpper() const { 218 return columnUpper_; 219 } 220 /// Lower bounds on sets 221 inline double * lowerSet() const { 222 return lowerSet_; 223 } 224 /// Upper bounds on sets 225 inline double * upperSet() const { 226 return upperSet_; 227 } 228 /// size 229 inline int numberGubColumns() const { 230 return numberGubColumns_; 231 } 232 /// first free 233 inline int firstAvailable() const { 234 return firstAvailable_; 235 } 236 /// first dynamic 237 inline int firstDynamic() const { 238 return firstDynamic_; 239 } 240 /// number of columns in dynamic model 241 inline int lastDynamic() const { 242 return lastDynamic_; 243 } 244 /// number of rows in original model 245 inline int numberStaticRows() const { 246 return numberStaticRows_; 247 } 248 /// size of working matrix (max) 249 inline int numberElements() const { 250 return numberElements_; 251 } 252 inline int * keyVariable() const { 253 return keyVariable_; 254 } 255 /// Switches off dj checking each factorization (for BIG models) 256 void switchOffCheck(); 257 /// Status region for gub slacks 258 inline unsigned char * gubRowStatus() const { 259 return status_; 260 } 261 /// Status region for gub variables 262 inline unsigned char * dynamicStatus() const { 263 return dynamicStatus_; 264 } 265 /// Returns which set a variable is in 266 int whichSet (int sequence) const; 267 //@} 268 269 246 270 protected: 247 /**@name Data members248 The data members are protected to allow access for derived classes. */249 //@{250 /// Sum of dual infeasibilities251 double sumDualInfeasibilities_;252 /// Sum of primal infeasibilities253 double sumPrimalInfeasibilities_;254 /// Sum of Dual infeasibilities using tolerance based on error in duals255 double sumOfRelaxedDualInfeasibilities_;256 /// Sum of Primal infeasibilities using tolerance based on error in primals257 double sumOfRelaxedPrimalInfeasibilities_;258 /// Saved best dual on gub row in pricing259 double savedBestGubDual_;260 /// Saved best set in pricing261 int savedBestSet_;262 /// Backward pointer to pivot row !!!263 int * backToPivotRow_;264 /// Key variable of set (only accurate if none in small problem)265 mutable int * keyVariable_;266 /// Backward pointer to extra row267 int * toIndex_;268 // Reverse pointer from index to set269 int * fromIndex_;270 /// Number of sets (dynamic rows)271 int numberSets_;272 /// Number of active sets273 int numberActiveSets_;274 /// Saved value of objective offset275 double objectiveOffset_;276 /// Lower bounds on sets277 double * lowerSet_;278 /// Upper bounds on sets279 double * upperSet_;280 /// Status of slack on set281 unsigned char * status_;282 /// Pointer back to model283 ClpSimplex * model_;284 /// first free285 int firstAvailable_;286 /// first free when iteration started287 int firstAvailableBefore_;288 /// first dynamic289 int firstDynamic_;290 /// number of columns in dynamic model291 int lastDynamic_;292 /// number of rows in original model293 int numberStaticRows_;294 /// size of working matrix (max)295 int numberElements_;296 /// Number of dual infeasibilities297 int numberDualInfeasibilities_;298 /// Number of primal infeasibilities299 int numberPrimalInfeasibilities_;300 /** If pricing will declare victory (i.e. no check every factorization).301 1  always check302 0  don't check303 1  in don't check mode but looks optimal304 */305 int noCheck_;306 /// Infeasibility weight when last full pass done307 double infeasibilityWeight_;308 /// size309 int numberGubColumns_;310 /// current maximum number of columns (then compress)311 int maximumGubColumns_;312 /// current maximum number of elemnts (then compress)313 int maximumElements_;314 /// Start of each set315 int * startSet_;316 /// next in chain317 int * next_;318 /// Starts of each column319 CoinBigIndex * startColumn_;320 /// rows321 int * row_;322 /// elements323 double * element_;324 /// costs325 double * cost_;326 /// ids of active columns (just index here)327 int * id_;328 /// for status and which bound329 unsigned char * dynamicStatus_;330 /// Optional lower bounds on columns331 double * columnLower_;332 /// Optional upper bounds on columns333 double * columnUpper_;334 //@}271 /**@name Data members 272 The data members are protected to allow access for derived classes. */ 273 //@{ 274 /// Sum of dual infeasibilities 275 double sumDualInfeasibilities_; 276 /// Sum of primal infeasibilities 277 double sumPrimalInfeasibilities_; 278 /// Sum of Dual infeasibilities using tolerance based on error in duals 279 double sumOfRelaxedDualInfeasibilities_; 280 /// Sum of Primal infeasibilities using tolerance based on error in primals 281 double sumOfRelaxedPrimalInfeasibilities_; 282 /// Saved best dual on gub row in pricing 283 double savedBestGubDual_; 284 /// Saved best set in pricing 285 int savedBestSet_; 286 /// Backward pointer to pivot row !!! 287 int * backToPivotRow_; 288 /// Key variable of set (only accurate if none in small problem) 289 mutable int * keyVariable_; 290 /// Backward pointer to extra row 291 int * toIndex_; 292 // Reverse pointer from index to set 293 int * fromIndex_; 294 /// Number of sets (dynamic rows) 295 int numberSets_; 296 /// Number of active sets 297 int numberActiveSets_; 298 /// Saved value of objective offset 299 double objectiveOffset_; 300 /// Lower bounds on sets 301 double * lowerSet_; 302 /// Upper bounds on sets 303 double * upperSet_; 304 /// Status of slack on set 305 unsigned char * status_; 306 /// Pointer back to model 307 ClpSimplex * model_; 308 /// first free 309 int firstAvailable_; 310 /// first free when iteration started 311 int firstAvailableBefore_; 312 /// first dynamic 313 int firstDynamic_; 314 /// number of columns in dynamic model 315 int lastDynamic_; 316 /// number of rows in original model 317 int numberStaticRows_; 318 /// size of working matrix (max) 319 int numberElements_; 320 /// Number of dual infeasibilities 321 int numberDualInfeasibilities_; 322 /// Number of primal infeasibilities 323 int numberPrimalInfeasibilities_; 324 /** If pricing will declare victory (i.e. no check every factorization). 325 1  always check 326 0  don't check 327 1  in don't check mode but looks optimal 328 */ 329 int noCheck_; 330 /// Infeasibility weight when last full pass done 331 double infeasibilityWeight_; 332 /// size 333 int numberGubColumns_; 334 /// current maximum number of columns (then compress) 335 int maximumGubColumns_; 336 /// current maximum number of elemnts (then compress) 337 int maximumElements_; 338 /// Start of each set 339 int * startSet_; 340 /// next in chain 341 int * next_; 342 /// Starts of each column 343 CoinBigIndex * startColumn_; 344 /// rows 345 int * row_; 346 /// elements 347 double * element_; 348 /// costs 349 double * cost_; 350 /// ids of active columns (just index here) 351 int * id_; 352 /// for status and which bound 353 unsigned char * dynamicStatus_; 354 /// Optional lower bounds on columns 355 double * columnLower_; 356 /// Optional upper bounds on columns 357 double * columnUpper_; 358 //@} 335 359 }; 336 360
Note: See TracChangeset
for help on using the changeset viewer.