1 /* $Id: ClpGubMatrix.hpp 2385 2019-01-06 19:43:06Z unxusr $ */ 2 // Copyright (C) 2003, 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 ClpGubMatrix_H 7 #define ClpGubMatrix_H 8 9 #include "CoinPragma.hpp" 10 11 #include "ClpPackedMatrix.hpp" 12 class ClpSimplex; 13 /** This implements Gub rows plus a ClpPackedMatrix. 14 15 There will be a version using ClpPlusMinusOne matrix but 16 there is no point doing one with ClpNetworkMatrix (although 17 an embedded network is attractive). 18 19 */ 20 21 class ClpGubMatrix : public ClpPackedMatrix { 22 23 public: 24 /**@name Main functions provided */ 25 //@{ 26 /** Returns a new matrix in reverse order without gaps (GUB wants NULL) */ 27 virtual ClpMatrixBase *reverseOrderedCopy() const; 28 /// Returns number of elements in column part of basis 29 virtual int countBasis(const int *whichColumn, 30 int &numberColumnBasic); 31 /// Fills in column part of basis 32 virtual void fillBasis(ClpSimplex *model, 33 const int *whichColumn, 34 int &numberColumnBasic, 35 int *row, int *start, 36 int *rowCount, int *columnCount, 37 CoinFactorizationDouble *element); 38 /** Unpacks a column into an CoinIndexedvector 39 */ 40 virtual void unpack(const ClpSimplex *model, CoinIndexedVector *rowArray, 41 int column) const; 42 /** Unpacks a column into an CoinIndexedvector 43 ** in packed foramt 44 Note that model is NOT const. Bounds and objective could 45 be modified if doing column generation (just for this variable) */ 46 virtual void unpackPacked(ClpSimplex *model, 47 CoinIndexedVector *rowArray, 48 int column) const; 49 /** Adds multiple of a column into an CoinIndexedvector 50 You can use quickAdd to add to vector */ 51 virtual void add(const ClpSimplex *model, CoinIndexedVector *rowArray, 52 int column, double multiplier) const; 53 /** Adds multiple of a column into an array */ 54 virtual void add(const ClpSimplex *model, double *array, 55 int column, double multiplier) const; 56 /// Partial pricing 57 virtual void partialPricing(ClpSimplex *model, double start, double end, 58 int &bestSequence, int &numberWanted); 59 /// Returns number of hidden rows e.g. gub 60 virtual int hiddenRows() const; 61 //@} 62 63 /**@name Matrix times vector methods */ 64 //@{ 65 66 using ClpPackedMatrix::transposeTimes; 67 /** Return <code>x * scalar * A + y</code> in <code>z</code>. 68 Can use y as temporary array (will be empty at end) 69 Note - If x packed mode - then z packed mode 70 Squashes small elements and knows about ClpSimplex */ 71 virtual void transposeTimes(const ClpSimplex *model, double scalar, 72 const CoinIndexedVector *x, 73 CoinIndexedVector *y, 74 CoinIndexedVector *z) const; 75 /** Return <code>x * scalar * A + y</code> in <code>z</code>. 76 Can use y as temporary array (will be empty at end) 77 Note - If x packed mode - then z packed mode 78 Squashes small elements and knows about ClpSimplex. 79 This version uses row copy*/ 80 virtual void transposeTimesByRow(const ClpSimplex *model, double scalar, 81 const CoinIndexedVector *x, 82 CoinIndexedVector *y, 83 CoinIndexedVector *z) const; 84 /** Return <code>x *A</code> in <code>z</code> but 85 just for indices in y. 86 Note - z always packed mode */ 87 virtual void subsetTransposeTimes(const ClpSimplex *model, 88 const CoinIndexedVector *x, 89 const CoinIndexedVector *y, 90 CoinIndexedVector *z) const; 91 /** expands an updated column to allow for extra rows which the main 92 solver does not know about and returns number added if mode 0. 93 If mode 1 deletes extra entries 94 95 This active in Gub 96 */ 97 virtual int extendUpdated(ClpSimplex *model, CoinIndexedVector *update, int mode); 98 /** 99 mode=0 - Set up before "update" and "times" for primal solution using extended rows 100 mode=1 - Cleanup primal solution after "times" using extended rows. 101 mode=2 - Check (or report on) primal infeasibilities 102 */ 103 virtual void primalExpanded(ClpSimplex *model, int mode); 104 /** 105 mode=0 - Set up before "updateTranspose" and "transposeTimes" for duals using extended 106 updates array (and may use other if dual values pass) 107 mode=1 - Update dual solution after "transposeTimes" using extended rows. 108 mode=2 - Compute all djs and compute key dual infeasibilities 109 mode=3 - Report on key dual infeasibilities 110 mode=4 - Modify before updateTranspose in partial pricing 111 */ 112 virtual void dualExpanded(ClpSimplex *model, CoinIndexedVector *array, 113 double *other, int mode); 114 /** 115 mode=0 - Create list of non-key basics in pivotVariable_ using 116 number as numberBasic in and out 117 mode=1 - Set all key variables as basic 118 mode=2 - return number extra rows needed, number gives maximum number basic 119 mode=3 - before replaceColumn 120 mode=4 - return 1 if can do primal, 2 if dual, 3 if both 121 mode=5 - save any status stuff (when in good state) 122 mode=6 - restore status stuff 123 mode=7 - flag given variable (normally sequenceIn) 124 mode=8 - unflag all variables 125 mode=9 - synchronize costs 126 mode=10 - return 1 if there may be changing bounds on variable (column generation) 127 mode=11 - make sure set is clean (used when a variable rejected - but not flagged) 128 mode=12 - after factorize but before permute stuff 129 mode=13 - at end of simplex to delete stuff 130 */ 131 virtual int generalExpanded(ClpSimplex *model, int mode, int &number); 132 /** 133 update information for a pivot (and effective rhs) 134 */ 135 virtual int updatePivot(ClpSimplex *model, double oldInValue, double oldOutValue); 136 /// Sets up an effective RHS and does gub crash if needed 137 virtual void useEffectiveRhs(ClpSimplex *model, bool cheapest = true); 138 /** Returns effective RHS offset if it is being used. This is used for long problems 139 or big gub or anywhere where going through full columns is 140 expensive. This may re-compute */ 141 virtual double *rhsOffset(ClpSimplex *model, bool forceRefresh = false, 142 bool check = false); 143 /** This is local to Gub to allow synchronization: 144 mode=0 when status of basis is good 145 mode=1 when variable is flagged 146 mode=2 when all variables unflagged (returns number flagged) 147 mode=3 just reset costs (primal) 148 mode=4 correct number of dual infeasibilities 149 mode=5 return 4 if time to re-factorize 150 mode=6 - return 1 if there may be changing bounds on variable (column generation) 151 mode=7 - do extra restores for column generation 152 mode=8 - make sure set is clean 153 mode=9 - adjust lower, upper on set by incoming 154 */ 155 virtual int synchronize(ClpSimplex *model, int mode); 156 /// Correct sequence in and out to give true value 157 virtual void correctSequence(const ClpSimplex *model, int &sequenceIn, int &sequenceOut); 158 //@} 159 160 /**@name Constructors, destructor */ 161 //@{ 162 /** Default constructor. */ 163 ClpGubMatrix(); 164 /** Destructor */ 165 virtual ~ClpGubMatrix(); 166 //@} 167 168 /**@name Copy method */ 169 //@{ 170 /** The copy constructor. */ 171 ClpGubMatrix(const ClpGubMatrix &); 172 /** The copy constructor from an CoinPackedMatrix. */ 173 ClpGubMatrix(const CoinPackedMatrix &); 174 /** Subset constructor (without gaps). Duplicates are allowed 175 and order is as given */ 176 ClpGubMatrix(const ClpGubMatrix &wholeModel, 177 int numberRows, const int *whichRows, 178 int numberColumns, const int *whichColumns); 179 ClpGubMatrix(const CoinPackedMatrix &wholeModel, 180 int numberRows, const int *whichRows, 181 int numberColumns, const int *whichColumns); 182 183 /** This takes over ownership (for space reasons) */ 184 ClpGubMatrix(CoinPackedMatrix *matrix); 185 186 /** This takes over ownership (for space reasons) and is the 187 real constructor*/ 188 ClpGubMatrix(ClpPackedMatrix *matrix, int numberSets, 189 const int *start, const int *end, 190 const double *lower, const double *upper, 191 const unsigned char *status = NULL); 192 193 ClpGubMatrix &operator=(const ClpGubMatrix &); 194 /// Clone 195 virtual ClpMatrixBase *clone() const; 196 /** Subset clone (without gaps). Duplicates are allowed 197 and order is as given */ 198 virtual ClpMatrixBase *subsetClone( 199 int numberRows, const int *whichRows, 200 int numberColumns, const int *whichColumns) const; 201 /** redoes next_ for a set. */ 202 void redoSet(ClpSimplex *model, int newKey, int oldKey, int iSet); 203 //@} 204 /**@name gets and sets */ 205 //@{ 206 /// Status getStatus(int sequence) const207 inline ClpSimplex::Status getStatus(int sequence) const 208 { 209 return static_cast< ClpSimplex::Status >(status_[sequence] & 7); 210 } setStatus(int sequence,ClpSimplex::Status status)211 inline void setStatus(int sequence, ClpSimplex::Status status) 212 { 213 unsigned char &st_byte = status_[sequence]; 214 st_byte = static_cast< unsigned char >(st_byte & ~7); 215 st_byte = static_cast< unsigned char >(st_byte | status); 216 } 217 /// To flag a variable setFlagged(int sequence)218 inline void setFlagged(int sequence) 219 { 220 status_[sequence] = static_cast< unsigned char >(status_[sequence] | 64); 221 } clearFlagged(int sequence)222 inline void clearFlagged(int sequence) 223 { 224 status_[sequence] = static_cast< unsigned char >(status_[sequence] & ~64); 225 } flagged(int sequence) const226 inline bool flagged(int sequence) const 227 { 228 return ((status_[sequence] & 64) != 0); 229 } 230 /// To say key is above ub setAbove(int sequence)231 inline void setAbove(int sequence) 232 { 233 unsigned char iStat = status_[sequence]; 234 iStat = static_cast< unsigned char >(iStat & ~24); 235 status_[sequence] = static_cast< unsigned char >(iStat | 16); 236 } 237 /// To say key is feasible setFeasible(int sequence)238 inline void setFeasible(int sequence) 239 { 240 unsigned char iStat = status_[sequence]; 241 iStat = static_cast< unsigned char >(iStat & ~24); 242 status_[sequence] = static_cast< unsigned char >(iStat | 8); 243 } 244 /// To say key is below lb setBelow(int sequence)245 inline void setBelow(int sequence) 246 { 247 unsigned char iStat = status_[sequence]; 248 iStat = static_cast< unsigned char >(iStat & ~24); 249 status_[sequence] = iStat; 250 } weight(int sequence) const251 inline double weight(int sequence) const 252 { 253 int iStat = status_[sequence] & 31; 254 iStat = iStat >> 3; 255 return static_cast< double >(iStat - 1); 256 } 257 /// Starts start() const258 inline int *start() const 259 { 260 return start_; 261 } 262 /// End end() const263 inline int *end() const 264 { 265 return end_; 266 } 267 /// Lower bounds on sets lower() const268 inline double *lower() const 269 { 270 return lower_; 271 } 272 /// Upper bounds on sets upper() const273 inline double *upper() const 274 { 275 return upper_; 276 } 277 /// Key variable of set keyVariable() const278 inline int *keyVariable() const 279 { 280 return keyVariable_; 281 } 282 /// Backward pointer to set number backward() const283 inline int *backward() const 284 { 285 return backward_; 286 } 287 /// Number of sets (gub rows) numberSets() const288 inline int numberSets() const 289 { 290 return numberSets_; 291 } 292 /// Switches off dj checking each factorization (for BIG models) 293 void switchOffCheck(); 294 //@} 295 296 protected: 297 /**@name Data members 298 The data members are protected to allow access for derived classes. */ 299 //@{ 300 /// Sum of dual infeasibilities 301 double sumDualInfeasibilities_; 302 /// Sum of primal infeasibilities 303 double sumPrimalInfeasibilities_; 304 /// Sum of Dual infeasibilities using tolerance based on error in duals 305 double sumOfRelaxedDualInfeasibilities_; 306 /// Sum of Primal infeasibilities using tolerance based on error in primals 307 double sumOfRelaxedPrimalInfeasibilities_; 308 /// Infeasibility weight when last full pass done 309 double infeasibilityWeight_; 310 /// Starts 311 int *start_; 312 /// End 313 int *end_; 314 /// Lower bounds on sets 315 double *lower_; 316 /// Upper bounds on sets 317 double *upper_; 318 /// Status of slacks 319 mutable unsigned char *status_; 320 /// Saved status of slacks 321 unsigned char *saveStatus_; 322 /// Saved key variables 323 int *savedKeyVariable_; 324 /// Backward pointer to set number 325 int *backward_; 326 /// Backward pointer to pivot row !!! 327 int *backToPivotRow_; 328 /// Change in costs for keys 329 double *changeCost_; 330 /// Key variable of set 331 mutable int *keyVariable_; 332 /** Next basic variable in set - starts at key and end with -(set+1). 333 Now changes to -(nonbasic+1). 334 next_ has extra space for 2* longest set */ 335 mutable int *next_; 336 /// Backward pointer to index in CoinIndexedVector 337 int *toIndex_; 338 // Reverse pointer from index to set 339 int *fromIndex_; 340 /// Pointer back to model 341 ClpSimplex *model_; 342 /// Number of dual infeasibilities 343 int numberDualInfeasibilities_; 344 /// Number of primal infeasibilities 345 int numberPrimalInfeasibilities_; 346 /** If pricing will declare victory (i.e. no check every factorization). 347 -1 - always check 348 0 - don't check 349 1 - in don't check mode but looks optimal 350 */ 351 int noCheck_; 352 /// Number of sets (gub rows) 353 int numberSets_; 354 /// Number in vector without gub extension 355 int saveNumber_; 356 /// Pivot row of possible next key 357 int possiblePivotKey_; 358 /// Gub slack in (set number or -1) 359 int gubSlackIn_; 360 /// First gub variables (same as start_[0] at present) 361 int firstGub_; 362 /// last gub variable (same as end_[numberSets_-1] at present) 363 int lastGub_; 364 /** type of gub - 0 not contiguous, 1 contiguous 365 add 8 bit to say no ubs on individual variables */ 366 int gubType_; 367 //@} 368 }; 369 370 #endif 371 372 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 373 */ 374