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