1/* $Id: ClpFactorization.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 ClpFactorization_H
7#define ClpFactorization_H
8
9
10#include "CoinPragma.hpp"
11
12#include "CoinFactorization.hpp"
13class ClpMatrixBase;
14class ClpSimplex;
15class ClpNetworkBasis;
16class CoinOtherFactorization;
17#ifndef CLP_MULTIPLE_FACTORIZATIONS
18#define CLP_MULTIPLE_FACTORIZATIONS 4
19#endif
20#ifdef CLP_MULTIPLE_FACTORIZATIONS
21#include "CoinDenseFactorization.hpp"
22#include "ClpSimplex.hpp"
23#endif
24#ifndef COIN_FAST_CODE
25#define COIN_FAST_CODE
26#endif
27
28/** This just implements CoinFactorization when an ClpMatrixBase object
29 is passed. If a network then has a dummy CoinFactorization and
30 a genuine ClpNetworkBasis object
31*/
32class ClpFactorization
33#ifndef CLP_MULTIPLE_FACTORIZATIONS
34 : public CoinFactorization
35#endif
36{
37
38 //friend class CoinFactorization;
39
40public:
41 /**@name factorization */
42 //@{
43 /** When part of LP - given by basic variables.
44 Actually does factorization.
45 Arrays passed in have non negative value to say basic.
46 If status is okay, basic variables have pivot row - this is only needed
47 if increasingRows_ >1.
48 Allows scaling
49 If status is singular, then basic variables have pivot row
50 and ones thrown out have -1
51 returns 0 -okay, -1 singular, -2 too many in basis, -99 memory */
52 int factorize (ClpSimplex * model, int solveType, bool valuesPass);
53 //@}
54
55
56 /**@name Constructors, destructor */
57 //@{
58 /** Default constructor. */
59 ClpFactorization();
60 /** Destructor */
61 ~ClpFactorization();
62 //@}
63
64 /**@name Copy method */
65 //@{
66 /** The copy constructor from an CoinFactorization. */
67 ClpFactorization(const CoinFactorization&);
68 /** The copy constructor. */
69 ClpFactorization(const ClpFactorization&, int denseIfSmaller = 0);
70#ifdef CLP_MULTIPLE_FACTORIZATIONS
71 /** The copy constructor from an CoinOtherFactorization. */
72 ClpFactorization(const CoinOtherFactorization&);
73#endif
74 ClpFactorization& operator=(const ClpFactorization&);
75 //@}
76
77 /* **** below here is so can use networkish basis */
78 /**@name rank one updates which do exist */
79 //@{
80
81 /** Replaces one Column to basis,
82 returns 0=OK, 1=Probably OK, 2=singular, 3=no room
83 If checkBeforeModifying is true will do all accuracy checks
84 before modifying factorization. Whether to set this depends on
85 speed considerations. You could just do this on first iteration
86 after factorization and thereafter re-factorize
87 partial update already in U */
88 int replaceColumn ( const ClpSimplex * model,
89 CoinIndexedVector * regionSparse,
90 CoinIndexedVector * tableauColumn,
91 int pivotRow,
92 double pivotCheck ,
93 bool checkBeforeModifying = false,
94 double acceptablePivot = 1.0e-8);
95 //@}
96
97 /**@name various uses of factorization (return code number elements)
98 which user may want to know about */
99 //@{
100 /** Updates one column (FTRAN) from region2
101 Tries to do FT update
102 number returned is negative if no room
103 region1 starts as zero and is zero at end */
104 int updateColumnFT ( CoinIndexedVector * regionSparse,
105 CoinIndexedVector * regionSparse2);
106 /** Updates one column (FTRAN) from region2
107 region1 starts as zero and is zero at end */
108 int updateColumn ( CoinIndexedVector * regionSparse,
109 CoinIndexedVector * regionSparse2,
110 bool noPermute = false) const;
111 /** Updates one column (FTRAN) from region2
112 Tries to do FT update
113 number returned is negative if no room.
114 Also updates region3
115 region1 starts as zero and is zero at end */
116 int updateTwoColumnsFT ( CoinIndexedVector * regionSparse1,
117 CoinIndexedVector * regionSparse2,
118 CoinIndexedVector * regionSparse3,
119 bool noPermuteRegion3 = false) ;
120 /// For debug (no statistics update)
121 int updateColumnForDebug ( CoinIndexedVector * regionSparse,
122 CoinIndexedVector * regionSparse2,
123 bool noPermute = false) const;
124 /** Updates one column (BTRAN) from region2
125 region1 starts as zero and is zero at end */
126 int updateColumnTranspose ( CoinIndexedVector * regionSparse,
127 CoinIndexedVector * regionSparse2) const;
128 //@}
129#ifdef CLP_MULTIPLE_FACTORIZATIONS
130 /**@name Lifted from CoinFactorization */
131 //@{
132 /// Total number of elements in factorization
133 inline int numberElements ( ) const {
134 if (coinFactorizationA_) return coinFactorizationA_->numberElements();
135 else return coinFactorizationB_->numberElements() ;
136 }
137 /// Returns address of permute region
138 inline int *permute ( ) const {
139 if (coinFactorizationA_) return coinFactorizationA_->permute();
140 else return coinFactorizationB_->permute() ;
141 }
142 /// Returns address of pivotColumn region (also used for permuting)
143 inline int *pivotColumn ( ) const {
144 if (coinFactorizationA_) return coinFactorizationA_->pivotColumn();
145 else return coinFactorizationB_->permute() ;
146 }
147 /// Maximum number of pivots between factorizations
148 inline int maximumPivots ( ) const {
149 if (coinFactorizationA_) return coinFactorizationA_->maximumPivots();
150 else return coinFactorizationB_->maximumPivots() ;
151 }
152 /// Set maximum number of pivots between factorizations
153 inline void maximumPivots ( int value) {
154 if (coinFactorizationA_) coinFactorizationA_->maximumPivots(value);
155 else coinFactorizationB_->maximumPivots(value);
156 }
157 /// Returns number of pivots since factorization
158 inline int pivots ( ) const {
159 if (coinFactorizationA_) return coinFactorizationA_->pivots();
160 else return coinFactorizationB_->pivots() ;
161 }
162 /// Whether larger areas needed
163 inline double areaFactor ( ) const {
164 if (coinFactorizationA_) return coinFactorizationA_->areaFactor();
165 else return 0.0 ;
166 }
167 /// Set whether larger areas needed
168 inline void areaFactor ( double value) {
169 if (coinFactorizationA_) coinFactorizationA_->areaFactor(value);
170 }
171 /// Zero tolerance
172 inline double zeroTolerance ( ) const {
173 if (coinFactorizationA_) return coinFactorizationA_->zeroTolerance();
174 else return coinFactorizationB_->zeroTolerance() ;
175 }
176 /// Set zero tolerance
177 inline void zeroTolerance ( double value) {
178 if (coinFactorizationA_) coinFactorizationA_->zeroTolerance(value);
179 else coinFactorizationB_->zeroTolerance(value);
180 }
181 /// Set tolerances to safer of existing and given
182 void saferTolerances ( double zeroTolerance, double pivotTolerance);
183 /** get sparse threshold */
184 inline int sparseThreshold ( ) const {
185 if (coinFactorizationA_) return coinFactorizationA_->sparseThreshold();
186 else return 0 ;
187 }
188 /** Set sparse threshold */
189 inline void sparseThreshold ( int value) {
190 if (coinFactorizationA_) coinFactorizationA_->sparseThreshold(value);
191 }
192 /// Returns status
193 inline int status ( ) const {
194 if (coinFactorizationA_) return coinFactorizationA_->status();
195 else return coinFactorizationB_->status() ;
196 }
197 /// Sets status
198 inline void setStatus ( int value) {
199 if (coinFactorizationA_) coinFactorizationA_->setStatus(value);
200 else coinFactorizationB_->setStatus(value) ;
201 }
202 /// Returns number of dense rows
203 inline int numberDense() const {
204 if (coinFactorizationA_) return coinFactorizationA_->numberDense();
205 else return 0 ;
206 }
207#if 1
208 /// Returns number in U area
209 inline CoinBigIndex numberElementsU ( ) const {
210 if (coinFactorizationA_) return coinFactorizationA_->numberElementsU();
211 else return -1 ;
212 }
213 /// Returns number in L area
214 inline CoinBigIndex numberElementsL ( ) const {
215 if (coinFactorizationA_) return coinFactorizationA_->numberElementsL();
216 else return -1 ;
217 }
218 /// Returns number in R area
219 inline CoinBigIndex numberElementsR ( ) const {
220 if (coinFactorizationA_) return coinFactorizationA_->numberElementsR();
221 else return 0 ;
222 }
223#endif
224 inline bool timeToRefactorize() const {
225 if (coinFactorizationA_) {
226 return (coinFactorizationA_->pivots() * 3 > coinFactorizationA_->maximumPivots() * 2 &&
227 coinFactorizationA_->numberElementsR() * 3 > (coinFactorizationA_->numberElementsL() +
228 coinFactorizationA_->numberElementsU()) * 2 + 1000 &&
229 !coinFactorizationA_->numberDense());
230 } else {
231 return coinFactorizationB_->pivots() > coinFactorizationB_->numberRows() / 2.45 + 20;
232 }
233 }
234 /// Level of detail of messages
235 inline int messageLevel ( ) const {
236 if (coinFactorizationA_) return coinFactorizationA_->messageLevel();
237 else return 1 ;
238 }
239 /// Set level of detail of messages
240 inline void messageLevel ( int value) {
241 if (coinFactorizationA_) coinFactorizationA_->messageLevel(value);
242 }
243 /// Get rid of all memory
244 inline void clearArrays() {
245 if (coinFactorizationA_)
246 coinFactorizationA_->clearArrays();
247 else if (coinFactorizationB_)
248 coinFactorizationB_->clearArrays();
249 }
250 /// Number of Rows after factorization
251 inline int numberRows ( ) const {
252 if (coinFactorizationA_) return coinFactorizationA_->numberRows();
253 else return coinFactorizationB_->numberRows() ;
254 }
255 /// Gets dense threshold
256 inline int denseThreshold() const {
257 if (coinFactorizationA_) return coinFactorizationA_->denseThreshold();
258 else return 0 ;
259 }
260 /// Sets dense threshold
261 inline void setDenseThreshold(int value) {
262 if (coinFactorizationA_) coinFactorizationA_->setDenseThreshold(value);
263 }
264 /// Pivot tolerance
265 inline double pivotTolerance ( ) const {
266 if (coinFactorizationA_) return coinFactorizationA_->pivotTolerance();
267 else if (coinFactorizationB_) return coinFactorizationB_->pivotTolerance();
268 return 1.0e-8 ;
269 }
270 /// Set pivot tolerance
271 inline void pivotTolerance ( double value) {
272 if (coinFactorizationA_) coinFactorizationA_->pivotTolerance(value);
273 else if (coinFactorizationB_) coinFactorizationB_->pivotTolerance(value);
274 }
275 /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed
276 inline void relaxAccuracyCheck(double value) {
277 if (coinFactorizationA_) coinFactorizationA_->relaxAccuracyCheck(value);
278 }
279 /** Array persistence flag
280 If 0 then as now (delete/new)
281 1 then only do arrays if bigger needed
282 2 as 1 but give a bit extra if bigger needed
283 */
284 inline int persistenceFlag() const {
285 if (coinFactorizationA_) return coinFactorizationA_->persistenceFlag();
286 else return 0 ;
287 }
288 inline void setPersistenceFlag(int value) {
289 if (coinFactorizationA_) coinFactorizationA_->setPersistenceFlag(value);
290 }
291 /// Delete all stuff (leaves as after CoinFactorization())
292 inline void almostDestructor() {
293 if (coinFactorizationA_)
294 coinFactorizationA_->almostDestructor();
295 else if (coinFactorizationB_)
296 coinFactorizationB_->clearArrays();
297 }
298 /// Returns areaFactor but adjusted for dense
299 inline double adjustedAreaFactor() const {
300 if (coinFactorizationA_) return coinFactorizationA_->adjustedAreaFactor();
301 else return 0.0 ;
302 }
303 inline void setBiasLU(int value) {
304 if (coinFactorizationA_) coinFactorizationA_->setBiasLU(value);
305 }
306 /// true if Forrest Tomlin update, false if PFI
307 inline void setForrestTomlin(bool value) {
308 if (coinFactorizationA_) coinFactorizationA_->setForrestTomlin(value);
309 }
310 /// Sets default values
311 inline void setDefaultValues() {
312 if (coinFactorizationA_) {
313 // row activities have negative sign
314#ifndef COIN_FAST_CODE
315 coinFactorizationA_->slackValue(-1.0);
316#endif
317 coinFactorizationA_->zeroTolerance(1.0e-13);
318 }
319 }
320 /// If nonzero force use of 1,dense 2,small 3,osl
321 void forceOtherFactorization(int which);
322 /// Get switch to osl if number rows <= this
323 inline int goOslThreshold() const {
324 return goOslThreshold_;
325 }
326 /// Set switch to osl if number rows <= this
327 inline void setGoOslThreshold(int value) {
328 goOslThreshold_ = value;
329 }
330 /// Get switch to dense if number rows <= this
331 inline int goDenseThreshold() const {
332 return goDenseThreshold_;
333 }
334 /// Set switch to dense if number rows <= this
335 inline void setGoDenseThreshold(int value) {
336 goDenseThreshold_ = value;
337 }
338 /// Get switch to small if number rows <= this
339 inline int goSmallThreshold() const {
340 return goSmallThreshold_;
341 }
342 /// Set switch to small if number rows <= this
343 inline void setGoSmallThreshold(int value) {
344 goSmallThreshold_ = value;
345 }
346 /// Go over to dense or small code if small enough
347 void goDenseOrSmall(int numberRows) ;
348 /// Sets factorization
349 void setFactorization(ClpFactorization & factorization);
350 /// Return 1 if dense code
351 inline int isDenseOrSmall() const {
352 return coinFactorizationB_ ? 1 : 0;
353 }
354#else
355 inline bool timeToRefactorize() const {
356 return (pivots() * 3 > maximumPivots() * 2 &&
357 numberElementsR() * 3 > (numberElementsL() + numberElementsU()) * 2 + 1000 &&
358 !numberDense());
359 }
360 /// Sets default values
361 inline void setDefaultValues() {
362 // row activities have negative sign
363#ifndef COIN_FAST_CODE
364 slackValue(-1.0);
365#endif
366 zeroTolerance(1.0e-13);
367 }
368 /// Go over to dense code
369 inline void goDense() {}
370#endif
371 //@}
372
373 /**@name other stuff */
374 //@{
375 /** makes a row copy of L for speed and to allow very sparse problems */
376 void goSparse();
377 /// Cleans up i.e. gets rid of network basis
378 void cleanUp();
379 /// Says whether to redo pivot order
380 bool needToReorder() const;
381#ifndef SLIM_CLP
382 /// Says if a network basis
383 inline bool networkBasis() const {
384 return (networkBasis_ != nullptr);
385 }
386#else
387 /// Says if a network basis
388 inline bool networkBasis() const {
389 return false;
390 }
391#endif
392 /// Fills weighted row list
393 void getWeights(int * weights) const;
394 //@}
395
396////////////////// data //////////////////
397private:
398
399 /**@name data */
400 //@{
401 /// Pointer to network basis
402#ifndef SLIM_CLP
403 ClpNetworkBasis * networkBasis_;
404#endif
405#ifdef CLP_MULTIPLE_FACTORIZATIONS
406 /// Pointer to CoinFactorization
407 CoinFactorization * coinFactorizationA_;
408 /// Pointer to CoinOtherFactorization
409 CoinOtherFactorization * coinFactorizationB_;
410#ifdef CLP_REUSE_ETAS
411 /// Pointer to model
412 ClpSimplex * model_;
413#endif
414 /// If nonzero force use of 1,dense 2,small 3,osl
415 int forceB_;
416 /// Switch to osl if number rows <= this
417 int goOslThreshold_;
418 /// Switch to small if number rows <= this
419 int goSmallThreshold_;
420 /// Switch to dense if number rows <= this
421 int goDenseThreshold_;
422#endif
423 //@}
424};
425
426#endif
427