1/* $Id: ClpMatrixBase.hpp 1753 2011-06-19 16:27:26Z stefan $ */
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 ClpMatrixBase_H
7#define ClpMatrixBase_H
8
9#include "CoinPragma.hpp"
10#include "CoinTypes.hpp"
11
12#include "CoinPackedMatrix.hpp"
13class CoinIndexedVector;
14class ClpSimplex;
15class ClpModel;
16
17/** Abstract base class for Clp Matrices
18
19Since this class is abstract, no object of this type can be created.
20
21If a derived class provides all methods then all Clp algorithms
22should work. Some can be very inefficient e.g. getElements etc is
23only used for tightening bounds for dual and the copies are
24deleted. Many methods can just be dummy i.e. abort(); if not
25all features are being used. So if column generation was being done
26then it makes no sense to do steepest edge so there would be
27no point providing subsetTransposeTimes.
28*/
29
30class ClpMatrixBase {
31
32public:
33 /**@name Virtual methods that the derived classes must provide */
34 //@{
35 /// Return a complete CoinPackedMatrix
36 virtual CoinPackedMatrix * getPackedMatrix() const = 0;
37 /** Whether the packed matrix is column major ordered or not. */
38 virtual bool isColOrdered() const = 0;
39 /** Number of entries in the packed matrix. */
40 virtual CoinBigIndex getNumElements() const = 0;
41 /** Number of columns. */
42 virtual int getNumCols() const = 0;
43 /** Number of rows. */
44 virtual int getNumRows() const = 0;
45
46 /** A vector containing the elements in the packed matrix. Note that there
47 might be gaps in this list, entries that do not belong to any
48 major-dimension vector. To get the actual elements one should look at
49 this vector together with vectorStarts and vectorLengths. */
50 virtual const double * getElements() const = 0;
51 /** A vector containing the minor indices of the elements in the packed
52 matrix. Note that there might be gaps in this list, entries that do not
53 belong to any major-dimension vector. To get the actual elements one
54 should look at this vector together with vectorStarts and
55 vectorLengths. */
56 virtual const int * getIndices() const = 0;
57
58 virtual const CoinBigIndex * getVectorStarts() const = 0;
59 /** The lengths of the major-dimension vectors. */
60 virtual const int * getVectorLengths() const = 0 ;
61 /** The length of a single major-dimension vector. */
62 virtual int getVectorLength(int index) const ;
63 /** Delete the columns whose indices are listed in <code>indDel</code>. */
64 virtual void deleteCols(const int numDel, const int * indDel) = 0;
65 /** Delete the rows whose indices are listed in <code>indDel</code>. */
66 virtual void deleteRows(const int numDel, const int * indDel) = 0;
67#ifndef CLP_NO_VECTOR
68 /// Append Columns
69 virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
70 /// Append Rows
71 virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
72#endif
73 /** Modify one element of packed matrix. An element may be added.
74 This works for either ordering If the new element is zero it will be
75 deleted unless keepZero true */
76 virtual void modifyCoefficient(int row, int column, double newElement,
77 bool keepZero = false);
78 /** Append a set of rows/columns to the end of the matrix. Returns number of errors
79 i.e. if any of the new rows/columns contain an index that's larger than the
80 number of columns-1/rows-1 (if numberOther>0) or duplicates
81 If 0 then rows, 1 if columns */
82 virtual int appendMatrix(int number, int type,
83 const CoinBigIndex * starts, const int * index,
84 const double * element, int numberOther = -1);
85
86 /** Returns a new matrix in reverse order without gaps
87 Is allowed to return NULL if doesn't want to have row copy */
88 virtual ClpMatrixBase * reverseOrderedCopy() const {
89 return nullptr;
90 }
91
92 /// Returns number of elements in column part of basis
93 virtual CoinBigIndex countBasis(const int * whichColumn,
94 int & numberColumnBasic) = 0;
95 /// Fills in column part of basis
96 virtual void fillBasis(ClpSimplex * model,
97 const int * whichColumn,
98 int & numberColumnBasic,
99 int * row, int * start,
100 int * rowCount, int * columnCount,
101 CoinFactorizationDouble * element) = 0;
102 /** Creates scales for column copy (rowCopy in model may be modified)
103 default does not allow scaling
104 returns non-zero if no scaling done */
105 virtual int scale(ClpModel * , const ClpSimplex * = nullptr) const {
106 return 1;
107 }
108 /** Scales rowCopy if column copy scaled
109 Only called if scales already exist */
110 virtual void scaleRowCopy(ClpModel * ) const { }
111 /// Returns true if can create row copy
112 virtual bool canGetRowCopy() const {
113 return true;
114 }
115 /** Realy really scales column copy
116 Only called if scales already exist.
117 Up to user to delete */
118 inline virtual ClpMatrixBase * scaledColumnCopy(ClpModel * ) const {
119 return this->clone();
120 }
121
122 /** Checks if all elements are in valid range. Can just
123 return true if you are not paranoid. For Clp I will
124 probably expect no zeros. Code can modify matrix to get rid of
125 small elements.
126 check bits (can be turned off to save time) :
127 1 - check if matrix has gaps
128 2 - check if zero elements
129 4 - check and compress duplicates
130 8 - report on large and small
131 */
132 virtual bool allElementsInRange(ClpModel * ,
133 double , double ,
134 int = 15) {
135 return true;
136 }
137 /** Set the dimensions of the matrix. In effect, append new empty
138 columns/rows to the matrix. A negative number for either dimension
139 means that that dimension doesn't change. Otherwise the new dimensions
140 MUST be at least as large as the current ones otherwise an exception
141 is thrown. */
142 virtual void setDimensions(int numrows, int numcols);
143 /** Returns largest and smallest elements of both signs.
144 Largest refers to largest absolute value.
145 If returns zeros then can't tell anything */
146 virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
147 double & smallestPositive, double & largestPositive);
148
149 /** Unpacks a column into an CoinIndexedvector
150 */
151 virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray,
152 int column) const = 0;
153 /** Unpacks a column into an CoinIndexedvector
154 ** in packed format
155 Note that model is NOT const. Bounds and objective could
156 be modified if doing column generation (just for this variable) */
157 virtual void unpackPacked(ClpSimplex * model,
158 CoinIndexedVector * rowArray,
159 int column) const = 0;
160 /** Purely for column generation and similar ideas. Allows
161 matrix and any bounds or costs to be updated (sensibly).
162 Returns non-zero if any changes.
163 */
164 virtual int refresh(ClpSimplex * ) {
165 return 0;
166 }
167
168 // Really scale matrix
169 virtual void reallyScale(const double * rowScale, const double * columnScale);
170 /** Given positive integer weights for each row fills in sum of weights
171 for each column (and slack).
172 Returns weights vector
173 Default returns vector of ones
174 */
175 virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model, int * inputWeights) const;
176 /** Adds multiple of a column into an CoinIndexedvector
177 You can use quickAdd to add to vector */
178 virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray,
179 int column, double multiplier) const = 0;
180 /** Adds multiple of a column into an array */
181 virtual void add(const ClpSimplex * model, double * array,
182 int column, double multiplier) const = 0;
183 /// Allow any parts of a created CoinPackedMatrix to be deleted
184 virtual void releasePackedMatrix() const = 0;
185 /// Says whether it can do partial pricing
186 virtual bool canDoPartialPricing() const;
187 /// Returns number of hidden rows e.g. gub
188 virtual int hiddenRows() const;
189 /// Partial pricing
190 virtual void partialPricing(ClpSimplex * model, double start, double end,
191 int & bestSequence, int & numberWanted);
192 /** expands an updated column to allow for extra rows which the main
193 solver does not know about and returns number added.
194
195 This will normally be a no-op - it is in for GUB but may get extended to
196 general non-overlapping and embedded networks.
197
198 mode 0 - extend
199 mode 1 - delete etc
200 */
201 virtual int extendUpdated(ClpSimplex * model, CoinIndexedVector * update, int mode);
202 /**
203 utility primal function for dealing with dynamic constraints
204 mode=0 - Set up before "update" and "times" for primal solution using extended rows
205 mode=1 - Cleanup primal solution after "times" using extended rows.
206 mode=2 - Check (or report on) primal infeasibilities
207 */
208 virtual void primalExpanded(ClpSimplex * model, int mode);
209 /**
210 utility dual function for dealing with dynamic constraints
211 mode=0 - Set up before "updateTranspose" and "transposeTimes" for duals using extended
212 updates array (and may use other if dual values pass)
213 mode=1 - Update dual solution after "transposeTimes" using extended rows.
214 mode=2 - Compute all djs and compute key dual infeasibilities
215 mode=3 - Report on key dual infeasibilities
216 mode=4 - Modify before updateTranspose in partial pricing
217 */
218 virtual void dualExpanded(ClpSimplex * model, CoinIndexedVector * array,
219 double * other, int mode);
220 /**
221 general utility function for dealing with dynamic constraints
222 mode=0 - Create list of non-key basics in pivotVariable_ using
223 number as numberBasic in and out
224 mode=1 - Set all key variables as basic
225 mode=2 - return number extra rows needed, number gives maximum number basic
226 mode=3 - before replaceColumn
227 mode=4 - return 1 if can do primal, 2 if dual, 3 if both
228 mode=5 - save any status stuff (when in good state)
229 mode=6 - restore status stuff
230 mode=7 - flag given variable (normally sequenceIn)
231 mode=8 - unflag all variables
232 mode=9 - synchronize costs and bounds
233 mode=10 - return 1 if there may be changing bounds on variable (column generation)
234 mode=11 - make sure set is clean (used when a variable rejected - but not flagged)
235 mode=12 - after factorize but before permute stuff
236 mode=13 - at end of simplex to delete stuff
237
238 */
239 virtual int generalExpanded(ClpSimplex * model, int mode, int & number);
240 /**
241 update information for a pivot (and effective rhs)
242 */
243 virtual int updatePivot(ClpSimplex * model, double oldInValue, double oldOutValue);
244 /** Creates a variable. This is called after partial pricing and may modify matrix.
245 May update bestSequence.
246 */
247 virtual void createVariable(ClpSimplex * model, int & bestSequence);
248 /** Just for debug if odd type matrix.
249 Returns number of primal infeasibilities. */
250 virtual int checkFeasible(ClpSimplex * model, double & sum) const ;
251 /// Returns reduced cost of a variable
252 double reducedCost(ClpSimplex * model, int sequence) const;
253 /// Correct sequence in and out to give true value (if both -1 maybe do whole matrix)
254 virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ;
255 //@}
256
257 //---------------------------------------------------------------------------
258 /**@name Matrix times vector methods
259 They can be faster if scalar is +- 1
260 Also for simplex I am not using basic/non-basic split */
261 //@{
262 /** Return <code>y + A * x * scalar</code> in <code>y</code>.
263 @pre <code>x</code> must be of size <code>numColumns()</code>
264 @pre <code>y</code> must be of size <code>numRows()</code> */
265 virtual void times(double scalar,
266 const double * x, double * y) const = 0;
267 /** And for scaling - default aborts for when scaling not supported
268 (unless pointers NULL when as normal)
269 */
270 virtual void times(double scalar,
271 const double * x, double * y,
272 const double * rowScale,
273 const double * columnScale) const;
274 /** Return <code>y + x * scalar * A</code> in <code>y</code>.
275 @pre <code>x</code> must be of size <code>numRows()</code>
276 @pre <code>y</code> must be of size <code>numColumns()</code> */
277 virtual void transposeTimes(double scalar,
278 const double * x, double * y) const = 0;
279 /** And for scaling - default aborts for when scaling not supported
280 (unless pointers NULL when as normal)
281 */
282 virtual void transposeTimes(double scalar,
283 const double * x, double * y,
284 const double * rowScale,
285 const double * columnScale,
286 double * spare = nullptr) const;
287#if COIN_LONG_WORK
288 // For long double versions (aborts if not supported)
289 virtual void times(CoinWorkDouble scalar,
290 const CoinWorkDouble * x, CoinWorkDouble * y) const ;
291 virtual void transposeTimes(CoinWorkDouble scalar,
292 const CoinWorkDouble * x, CoinWorkDouble * y) const ;
293#endif
294 /** Return <code>x * scalar *A + y</code> in <code>z</code>.
295 Can use y as temporary array (will be empty at end)
296 Note - If x packed mode - then z packed mode
297 Squashes small elements and knows about ClpSimplex */
298 virtual void transposeTimes(const ClpSimplex * model, double scalar,
299 const CoinIndexedVector * x,
300 CoinIndexedVector * y,
301 CoinIndexedVector * z) const = 0;
302 /** Return <code>x *A</code> in <code>z</code> but
303 just for indices in y.
304 This is only needed for primal steepest edge.
305 Note - z always packed mode */
306 virtual void subsetTransposeTimes(const ClpSimplex * model,
307 const CoinIndexedVector * x,
308 const CoinIndexedVector * y,
309 CoinIndexedVector * z) const = 0;
310 /** Returns true if can combine transposeTimes and subsetTransposeTimes
311 and if it would be faster */
312 virtual bool canCombine(const ClpSimplex * ,
313 const CoinIndexedVector * ) const {
314 return false;
315 }
316 /// Updates two arrays for steepest and does devex weights (need not be coded)
317 virtual void transposeTimes2(const ClpSimplex * model,
318 const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
319 const CoinIndexedVector * pi2,
320 CoinIndexedVector * spare,
321 double referenceIn, double devex,
322 // Array for exact devex to say what is in reference framework
323 unsigned int * reference,
324 double * weights, double scaleFactor);
325 /// Updates second array for steepest and does devex weights (need not be coded)
326 virtual void subsetTimes2(const ClpSimplex * model,
327 CoinIndexedVector * dj1,
328 const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
329 double referenceIn, double devex,
330 // Array for exact devex to say what is in reference framework
331 unsigned int * reference,
332 double * weights, double scaleFactor);
333 /** Return <code>x *A</code> in <code>z</code> but
334 just for number indices in y.
335 Default cheats with fake CoinIndexedVector and
336 then calls subsetTransposeTimes */
337 virtual void listTransposeTimes(const ClpSimplex * model,
338 double * x,
339 int * y,
340 int number,
341 double * z) const;
342 //@}
343 //@{
344 ///@name Other
345 /// Clone
346 virtual ClpMatrixBase * clone() const = 0;
347 /** Subset clone (without gaps). Duplicates are allowed
348 and order is as given.
349 Derived classes need not provide this as it may not always make
350 sense */
351 virtual ClpMatrixBase * subsetClone (
352 int numberRows, const int * whichRows,
353 int numberColumns, const int * whichColumns) const;
354 /// Gets rid of any mutable by products
355 virtual void backToBasics() {}
356 /** Returns type.
357 The types which code may need to know about are:
358 1 - ClpPackedMatrix
359 11 - ClpNetworkMatrix
360 12 - ClpPlusMinusOneMatrix
361 */
362 inline int type() const {
363 return type_;
364 }
365 /// Sets type
366 void setType(int newtype) {
367 type_ = newtype;
368 }
369 /// Sets up an effective RHS
370 void useEffectiveRhs(ClpSimplex * model);
371 /** Returns effective RHS offset if it is being used. This is used for long problems
372 or big gub or anywhere where going through full columns is
373 expensive. This may re-compute */
374 virtual double * rhsOffset(ClpSimplex * model, bool forceRefresh = false,
375 bool check = false);
376 /// If rhsOffset used this is iteration last refreshed
377 inline int lastRefresh() const {
378 return lastRefresh_;
379 }
380 /// If rhsOffset used this is refresh frequency (0==off)
381 inline int refreshFrequency() const {
382 return refreshFrequency_;
383 }
384 inline void setRefreshFrequency(int value) {
385 refreshFrequency_ = value;
386 }
387 /// whether to skip dual checks most of time
388 inline bool skipDualCheck() const {
389 return skipDualCheck_;
390 }
391 inline void setSkipDualCheck(bool yes) {
392 skipDualCheck_ = yes;
393 }
394 /** Partial pricing tuning parameter - minimum number of "objects" to scan.
395 e.g. number of Gub sets but could be number of variables */
396 inline int minimumObjectsScan() const {
397 return minimumObjectsScan_;
398 }
399 inline void setMinimumObjectsScan(int value) {
400 minimumObjectsScan_ = value;
401 }
402 /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
403 inline int minimumGoodReducedCosts() const {
404 return minimumGoodReducedCosts_;
405 }
406 inline void setMinimumGoodReducedCosts(int value) {
407 minimumGoodReducedCosts_ = value;
408 }
409 /// Current start of search space in matrix (as fraction)
410 inline double startFraction() const {
411 return startFraction_;
412 }
413 inline void setStartFraction(double value) {
414 startFraction_ = value;
415 }
416 /// Current end of search space in matrix (as fraction)
417 inline double endFraction() const {
418 return endFraction_;
419 }
420 inline void setEndFraction(double value) {
421 endFraction_ = value;
422 }
423 /// Current best reduced cost
424 inline double savedBestDj() const {
425 return savedBestDj_;
426 }
427 inline void setSavedBestDj(double value) {
428 savedBestDj_ = value;
429 }
430 /// Initial number of negative reduced costs wanted
431 inline int originalWanted() const {
432 return originalWanted_;
433 }
434 inline void setOriginalWanted(int value) {
435 originalWanted_ = value;
436 }
437 /// Current number of negative reduced costs which we still need
438 inline int currentWanted() const {
439 return currentWanted_;
440 }
441 inline void setCurrentWanted(int value) {
442 currentWanted_ = value;
443 }
444 /// Current best sequence
445 inline int savedBestSequence() const {
446 return savedBestSequence_;
447 }
448 inline void setSavedBestSequence(int value) {
449 savedBestSequence_ = value;
450 }
451 //@}
452
453
454protected:
455
456 /**@name Constructors, destructor<br>
457 <strong>NOTE</strong>: All constructors are protected. There's no need
458 to expose them, after all, this is an abstract class. */
459 //@{
460 /** Default constructor. */
461 ClpMatrixBase();
462 /** Destructor (has to be public) */
463public:
464 virtual ~ClpMatrixBase();
465protected:
466 // Copy
467 ClpMatrixBase(const ClpMatrixBase&);
468 // Assignment
469 ClpMatrixBase& operator=(const ClpMatrixBase&);
470 //@}
471
472
473protected:
474 /**@name Data members
475 The data members are protected to allow access for derived classes. */
476 //@{
477 /** Effective RHS offset if it is being used. This is used for long problems
478 or big gub or anywhere where going through full columns is
479 expensive */
480 double * rhsOffset_;
481 /// Current start of search space in matrix (as fraction)
482 double startFraction_;
483 /// Current end of search space in matrix (as fraction)
484 double endFraction_;
485 /// Best reduced cost so far
486 double savedBestDj_;
487 /// Initial number of negative reduced costs wanted
488 int originalWanted_;
489 /// Current number of negative reduced costs which we still need
490 int currentWanted_;
491 /// Saved best sequence in pricing
492 int savedBestSequence_;
493 /// type (may be useful)
494 int type_;
495 /// If rhsOffset used this is iteration last refreshed
496 int lastRefresh_;
497 /// If rhsOffset used this is refresh frequency (0==off)
498 int refreshFrequency_;
499 /// Partial pricing tuning parameter - minimum number of "objects" to scan
500 int minimumObjectsScan_;
501 /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
502 int minimumGoodReducedCosts_;
503 /// True sequence in (i.e. from larger problem)
504 int trueSequenceIn_;
505 /// True sequence out (i.e. from larger problem)
506 int trueSequenceOut_;
507 /// whether to skip dual checks most of time
508 bool skipDualCheck_;
509 //@}
510};
511// bias for free variables
512#define FREE_BIAS 1.0e1
513// Acceptance criteria for free variables
514#define FREE_ACCEPT 1.0e2
515
516#endif
517