1 /* $Id: ClpSimplexOther.hpp 2385 2019-01-06 19:43:06Z unxusr $ */ 2 // Copyright (C) 2004, 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 Authors 7 8 John Forrest 9 10 */ 11 #ifndef ClpSimplexOther_H 12 #define ClpSimplexOther_H 13 14 #include "ClpSimplex.hpp" 15 16 /** This is for Simplex stuff which is neither dual nor primal 17 18 It inherits from ClpSimplex. It has no data of its own and 19 is never created - only cast from a ClpSimplex object at algorithm time. 20 21 */ 22 23 class ClpSimplexOther : public ClpSimplex { 24 25 public: 26 /**@name Methods */ 27 //@{ 28 /** Dual ranging. 29 This computes increase/decrease in cost for each given variable and corresponding 30 sequence numbers which would change basis. Sequence numbers are 0..numberColumns 31 and numberColumns.. for artificials/slacks. 32 For non-basic variables the information is trivial to compute and the change in cost is just minus the 33 reduced cost and the sequence number will be that of the non-basic variables. 34 For basic variables a ratio test is between the reduced costs for non-basic variables 35 and the row of the tableau corresponding to the basic variable. 36 The increase/decrease value is always >= 0.0 37 38 Up to user to provide correct length arrays where each array is of length numberCheck. 39 which contains list of variables for which information is desired. All other 40 arrays will be filled in by function. If fifth entry in which is variable 7 then fifth entry in output arrays 41 will be information for variable 7. 42 43 If valueIncrease/Decrease not NULL (both must be NULL or both non NULL) then these are filled with 44 the value of variable if such a change in cost were made (the existing bounds are ignored) 45 46 When here - guaranteed optimal 47 */ 48 void dualRanging(int numberCheck, const int *which, 49 double *costIncrease, int *sequenceIncrease, 50 double *costDecrease, int *sequenceDecrease, 51 double *valueIncrease = NULL, double *valueDecrease = NULL); 52 /** Primal ranging. 53 This computes increase/decrease in value for each given variable and corresponding 54 sequence numbers which would change basis. Sequence numbers are 0..numberColumns 55 and numberColumns.. for artificials/slacks. 56 This should only be used for non-basic variabls as otherwise information is pretty useless 57 For basic variables the sequence number will be that of the basic variables. 58 59 Up to user to provide correct length arrays where each array is of length numberCheck. 60 which contains list of variables for which information is desired. All other 61 arrays will be filled in by function. If fifth entry in which is variable 7 then fifth entry in output arrays 62 will be information for variable 7. 63 64 When here - guaranteed optimal 65 */ 66 void primalRanging(int numberCheck, const int *which, 67 double *valueIncrease, int *sequenceIncrease, 68 double *valueDecrease, int *sequenceDecrease); 69 /** Parametrics 70 This is an initial slow version. 71 The code uses current bounds + theta * change (if change array not NULL) 72 and similarly for objective. 73 It starts at startingTheta and returns ending theta in endingTheta. 74 If reportIncrement 0.0 it will report on any movement 75 If reportIncrement >0.0 it will report at startingTheta+k*reportIncrement. 76 If it can not reach input endingTheta return code will be 1 for infeasible, 77 2 for unbounded, if error on ranges -1, otherwise 0. 78 Normal report is just theta and objective but 79 if event handler exists it may do more 80 On exit endingTheta is maximum reached (can be used for next startingTheta) 81 */ 82 int parametrics(double startingTheta, double &endingTheta, double reportIncrement, 83 const double *changeLowerBound, const double *changeUpperBound, 84 const double *changeLowerRhs, const double *changeUpperRhs, 85 const double *changeObjective); 86 /** Version of parametrics which reads from file 87 See CbcClpParam.cpp for details of format 88 Returns -2 if unable to open file */ 89 int parametrics(const char *dataFile); 90 /** Parametrics 91 This is an initial slow version. 92 The code uses current bounds + theta * change (if change array not NULL) 93 It starts at startingTheta and returns ending theta in endingTheta. 94 If it can not reach input endingTheta return code will be 1 for infeasible, 95 2 for unbounded, if error on ranges -1, otherwise 0. 96 Event handler may do more 97 On exit endingTheta is maximum reached (can be used for next startingTheta) 98 */ 99 int parametrics(double startingTheta, double &endingTheta, 100 const double *changeLowerBound, const double *changeUpperBound, 101 const double *changeLowerRhs, const double *changeUpperRhs); 102 int parametricsObj(double startingTheta, double &endingTheta, 103 const double *changeObjective); 104 /// Finds best possible pivot 105 double bestPivot(bool justColumns = false); 106 typedef struct { 107 double startingTheta; 108 double endingTheta; 109 double maxTheta; 110 double acceptableMaxTheta; // if this far then within tolerances 111 double *lowerChange; // full array of lower bound changes 112 int *lowerList; // list of lower bound changes 113 double *upperChange; // full array of upper bound changes 114 int *upperList; // list of upper bound changes 115 char *markDone; // mark which ones looked at 116 int *backwardBasic; // from sequence to pivot row 117 int *lowerActive; 118 double *lowerGap; 119 double *lowerCoefficient; 120 int *upperActive; 121 double *upperGap; 122 double *upperCoefficient; 123 int unscaledChangesOffset; 124 bool firstIteration; // so can update rhs for accuracy 125 } parametricsData; 126 127 private: 128 /** Parametrics - inner loop 129 This first attempt is when reportIncrement non zero and may 130 not report endingTheta correctly 131 If it can not reach input endingTheta return code will be 1 for infeasible, 132 2 for unbounded, otherwise 0. 133 Normal report is just theta and objective but 134 if event handler exists it may do more 135 */ 136 int parametricsLoop(parametricsData ¶mData, double reportIncrement, 137 const double *changeLower, const double *changeUpper, 138 const double *changeObjective, ClpDataSave &data, 139 bool canTryQuick); 140 int parametricsLoop(parametricsData ¶mData, 141 ClpDataSave &data, bool canSkipFactorization = false); 142 int parametricsObjLoop(parametricsData ¶mData, 143 ClpDataSave &data, bool canSkipFactorization = false); 144 /** Refactorizes if necessary 145 Checks if finished. Updates status. 146 147 type - 0 initial so set up save arrays etc 148 - 1 normal -if good update save 149 - 2 restoring from saved 150 */ 151 void statusOfProblemInParametrics(int type, ClpDataSave &saveData); 152 void statusOfProblemInParametricsObj(int type, ClpDataSave &saveData); 153 /** This has the flow between re-factorizations 154 155 Reasons to come out: 156 -1 iterations etc 157 -2 inaccuracy 158 -3 slight inaccuracy (and done iterations) 159 +0 looks optimal (might be unbounded - but we will investigate) 160 +1 looks infeasible 161 +3 max iterations 162 */ 163 int whileIterating(parametricsData ¶mData, double reportIncrement, 164 const double *changeObjective); 165 /** Computes next theta and says if objective or bounds (0= bounds, 1 objective, -1 none). 166 theta is in theta_. 167 type 1 bounds, 2 objective, 3 both. 168 */ 169 int nextTheta(int type, double maxTheta, parametricsData ¶mData, 170 const double *changeObjective); 171 int whileIteratingObj(parametricsData ¶mData); 172 int nextThetaObj(double maxTheta, parametricsData ¶mData); 173 /// Restores bound to original bound 174 void originalBound(int iSequence, double theta, const double *changeLower, 175 const double *changeUpper); 176 /// Compute new rowLower_ etc (return negative if infeasible - otherwise largest change) 177 double computeRhsEtc(parametricsData ¶mData); 178 /// Redo lower_ from rowLower_ etc 179 void redoInternalArrays(); 180 /** 181 Row array has row part of pivot row 182 Column array has column part. 183 This is used in dual ranging 184 */ 185 void checkDualRatios(CoinIndexedVector *rowArray, 186 CoinIndexedVector *columnArray, 187 double &costIncrease, int &sequenceIncrease, double &alphaIncrease, 188 double &costDecrease, int &sequenceDecrease, double &alphaDecrease); 189 /** 190 Row array has pivot column 191 This is used in primal ranging 192 */ 193 void checkPrimalRatios(CoinIndexedVector *rowArray, 194 int direction); 195 /// Returns new value of whichOther when whichIn enters basis 196 double primalRanging1(int whichIn, int whichOther); 197 198 public: 199 /** Write the basis in MPS format to the specified file. 200 If writeValues true writes values of structurals 201 (and adds VALUES to end of NAME card) 202 203 Row and column names may be null. 204 formatType is 205 <ul> 206 <li> 0 - normal 207 <li> 1 - extra accuracy 208 <li> 2 - IEEE hex (later) 209 </ul> 210 211 Returns non-zero on I/O error 212 */ 213 int writeBasis(const char *filename, 214 bool writeValues = false, 215 int formatType = 0) const; 216 /// Read a basis from the given filename 217 int readBasis(const char *filename); 218 /** Creates dual of a problem if looks plausible 219 (defaults will always create model) 220 fractionRowRanges is fraction of rows allowed to have ranges 221 fractionColumnRanges is fraction of columns allowed to have ranges 222 */ 223 ClpSimplex *dualOfModel(double fractionRowRanges = 1.0, double fractionColumnRanges = 1.0) const; 224 /** Restores solution from dualized problem 225 non-zero return code indicates minor problems 226 */ 227 int restoreFromDual(const ClpSimplex *dualProblem, 228 bool checkAccuracy = false); 229 /** Sets solution in dualized problem 230 non-zero return code indicates minor problems 231 */ 232 int setInDual(ClpSimplex *dualProblem); 233 /** Does very cursory presolve. 234 rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns. 235 */ 236 ClpSimplex *crunch(double *rhs, int *whichRows, int *whichColumns, 237 int &nBound, bool moreBounds = false, bool tightenBounds = false); 238 /** After very cursory presolve. 239 rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns. 240 */ 241 void afterCrunch(const ClpSimplex &small, 242 const int *whichRows, const int *whichColumns, 243 int nBound); 244 /** Returns gub version of model or NULL 245 whichRows has to be numberRows 246 whichColumns has to be numberRows+numberColumns */ 247 ClpSimplex *gubVersion(int *whichRows, int *whichColumns, 248 int neededGub, 249 int factorizationFrequency = 50); 250 /// Sets basis from original 251 void setGubBasis(ClpSimplex &original, const int *whichRows, 252 const int *whichColumns); 253 /// Restores basis to original 254 void getGubBasis(ClpSimplex &original, const int *whichRows, 255 const int *whichColumns) const; 256 /// Quick try at cleaning up duals if postsolve gets wrong 257 void cleanupAfterPostsolve(); 258 /** Tightens integer bounds - returns number tightened or -1 if infeasible 259 */ 260 int tightenIntegerBounds(double *rhsSpace); 261 /** Expands out all possible combinations for a knapsack 262 If buildObj NULL then just computes space needed - returns number elements 263 On entry numberOutput is maximum allowed, on exit it is number needed or 264 -1 (as will be number elements) if maximum exceeded. numberOutput will have at 265 least space to return values which reconstruct input. 266 Rows returned will be original rows but no entries will be returned for 267 any rows all of whose entries are in knapsack. So up to user to allow for this. 268 If reConstruct >=0 then returns number of entrie which make up item "reConstruct" 269 in expanded knapsack. Values in buildRow and buildElement; 270 */ 271 int expandKnapsack(int knapsackRow, int &numberOutput, 272 double *buildObj, CoinBigIndex *buildStart, 273 int *buildRow, double *buildElement, int reConstruct = -1) const; 274 /// Create a string of commands to guess at best strategy for model 275 /// At present mode is ignored 276 char *guess(int mode) const; 277 //@} 278 }; 279 #endif 280 281 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 282 */ 283