Clp  1.15.10
ClpPackedMatrix.hpp
Go to the documentation of this file.
1 /* $Id: ClpPackedMatrix.hpp 1836 2011-12-15 20:22:39Z 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 ClpPackedMatrix_H
7 #define ClpPackedMatrix_H
8 
9 #include "CoinPragma.hpp"
10 
11 #include "ClpMatrixBase.hpp"
12 
13 // Compilers can produce better code if they know about __restrict
14 #ifndef COIN_RESTRICT
15 #ifdef COIN_USE_RESTRICT
16 #define COIN_RESTRICT __restrict
17 #else
18 #define COIN_RESTRICT
19 #endif
20 #endif
21 
28 class ClpPackedMatrix2;
29 class ClpPackedMatrix3;
31 
32 public:
35  virtual CoinPackedMatrix * getPackedMatrix() const {
37  return matrix_;
38  }
40  virtual bool isColOrdered() const {
41  return matrix_->isColOrdered();
42  }
44  virtual CoinBigIndex getNumElements() const {
45  return matrix_->getNumElements();
46  }
48  virtual int getNumCols() const {
49  return matrix_->getNumCols();
50  }
52  virtual int getNumRows() const {
53  return matrix_->getNumRows();
54  }
55 
60  virtual const double * getElements() const {
61  return matrix_->getElements();
62  }
64  inline double * getMutableElements() const {
65  return matrix_->getMutableElements();
66  }
72  virtual const int * getIndices() const {
73  return matrix_->getIndices();
74  }
75 
76  virtual const CoinBigIndex * getVectorStarts() const {
77  return matrix_->getVectorStarts();
78  }
80  virtual const int * getVectorLengths() const {
81  return matrix_->getVectorLengths();
82  }
84  virtual int getVectorLength(int index) const {
85  return matrix_->getVectorSize(index);
86  }
87 
89  virtual void deleteCols(const int numDel, const int * indDel);
91  virtual void deleteRows(const int numDel, const int * indDel);
92 #ifndef CLP_NO_VECTOR
93  virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
96  virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
97 #endif
98 
102  virtual int appendMatrix(int number, int type,
103  const CoinBigIndex * starts, const int * index,
104  const double * element, int numberOther = -1);
109  virtual void replaceVector(const int index,
110  const int numReplace, const double * newElements) {
111  matrix_->replaceVector(index, numReplace, newElements);
112  }
116  virtual void modifyCoefficient(int row, int column, double newElement,
117  bool keepZero = false) {
118  matrix_->modifyCoefficient(row, column, newElement, keepZero);
119  }
121  virtual ClpMatrixBase * reverseOrderedCopy() const;
123  virtual CoinBigIndex countBasis(const int * whichColumn,
124  int & numberColumnBasic);
126  virtual void fillBasis(ClpSimplex * model,
127  const int * whichColumn,
128  int & numberColumnBasic,
129  int * row, int * start,
130  int * rowCount, int * columnCount,
131  CoinFactorizationDouble * element);
134  virtual int scale(ClpModel * model, const ClpSimplex * baseModel = NULL) const ;
137  virtual void scaleRowCopy(ClpModel * model) const ;
139  void createScaledMatrix(ClpSimplex * model) const;
143  virtual ClpMatrixBase * scaledColumnCopy(ClpModel * model) const ;
154  virtual bool allElementsInRange(ClpModel * model,
155  double smallest, double largest,
156  int check = 15);
160  virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
161  double & smallestPositive, double & largestPositive);
162 
165  virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray,
166  int column) const ;
171  virtual void unpackPacked(ClpSimplex * model,
172  CoinIndexedVector * rowArray,
173  int column) const;
176  virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray,
177  int column, double multiplier) const ;
179  virtual void add(const ClpSimplex * model, double * array,
180  int column, double multiplier) const;
182  virtual void releasePackedMatrix() const { }
187  virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model, int * inputWeights) const;
189  virtual bool canDoPartialPricing() const;
191  virtual void partialPricing(ClpSimplex * model, double start, double end,
192  int & bestSequence, int & numberWanted);
194  virtual int refresh(ClpSimplex * model);
195  // Really scale matrix
196  virtual void reallyScale(const double * rowScale, const double * columnScale);
202  virtual void setDimensions(int numrows, int numcols);
204 
210  virtual void times(double scalar,
211  const double * x, double * y) const;
213  virtual void times(double scalar,
214  const double * x, double * y,
215  const double * rowScale,
216  const double * columnScale) const;
220  virtual void transposeTimes(double scalar,
221  const double * x, double * y) const;
223  virtual void transposeTimes(double scalar,
224  const double * x, double * y,
225  const double * rowScale,
226  const double * columnScale,
227  double * spare = NULL) const;
232  void transposeTimesSubset( int number,
233  const int * which,
234  const double * pi, double * y,
235  const double * rowScale,
236  const double * columnScale,
237  double * spare = NULL) const;
242  virtual void transposeTimes(const ClpSimplex * model, double scalar,
243  const CoinIndexedVector * x,
244  CoinIndexedVector * y,
245  CoinIndexedVector * z) const;
250  void transposeTimesByColumn(const ClpSimplex * model, double scalar,
251  const CoinIndexedVector * x,
252  CoinIndexedVector * y,
253  CoinIndexedVector * z) const;
259  virtual void transposeTimesByRow(const ClpSimplex * model, double scalar,
260  const CoinIndexedVector * x,
261  CoinIndexedVector * y,
262  CoinIndexedVector * z) const;
266  virtual void subsetTransposeTimes(const ClpSimplex * model,
267  const CoinIndexedVector * x,
268  const CoinIndexedVector * y,
269  CoinIndexedVector * z) const;
272  virtual bool canCombine(const ClpSimplex * model,
273  const CoinIndexedVector * pi) const;
275  virtual void transposeTimes2(const ClpSimplex * model,
276  const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
277  const CoinIndexedVector * pi2,
278  CoinIndexedVector * spare,
279  double referenceIn, double devex,
280  // Array for exact devex to say what is in reference framework
281  unsigned int * reference,
282  double * weights, double scaleFactor);
284  virtual void subsetTimes2(const ClpSimplex * model,
285  CoinIndexedVector * dj1,
286  const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
287  double referenceIn, double devex,
288  // Array for exact devex to say what is in reference framework
289  unsigned int * reference,
290  double * weights, double scaleFactor);
292  void useEffectiveRhs(ClpSimplex * model);
293 #if COIN_LONG_WORK
294  // For long double versions
295  virtual void times(CoinWorkDouble scalar,
296  const CoinWorkDouble * x, CoinWorkDouble * y) const ;
297  virtual void transposeTimes(CoinWorkDouble scalar,
298  const CoinWorkDouble * x, CoinWorkDouble * y) const ;
299 #endif
300 
301 
304  inline CoinPackedMatrix * matrix() const {
306  return matrix_;
307  }
311  inline void setMatrixNull() {
312  matrix_ = NULL;
313  }
315  inline void makeSpecialColumnCopy() {
316  flags_ |= 16;
317  }
321  inline bool zeros() const {
322  return ((flags_ & 1) != 0);
323  }
325  inline bool wantsSpecialColumnCopy() const {
326  return ((flags_ & 16) != 0);
327  }
329  inline int flags() const {
330  return flags_;
331  }
333  inline void checkGaps() {
334  flags_ = (matrix_->hasGaps()) ? (flags_ | 2) : (flags_ & (~2));
335  }
337  inline int numberActiveColumns() const
338  { return numberActiveColumns_;}
340  inline void setNumberActiveColumns(int value)
341  { numberActiveColumns_ = value;}
343 
344 
348  ClpPackedMatrix();
350  virtual ~ClpPackedMatrix();
352 
358  ClpPackedMatrix(const CoinPackedMatrix&);
361  ClpPackedMatrix (const ClpPackedMatrix & wholeModel,
362  int numberRows, const int * whichRows,
363  int numberColumns, const int * whichColumns);
364  ClpPackedMatrix (const CoinPackedMatrix & wholeModel,
365  int numberRows, const int * whichRows,
366  int numberColumns, const int * whichColumns);
367 
369  ClpPackedMatrix(CoinPackedMatrix * matrix);
370 
373  virtual ClpMatrixBase * clone() const ;
375  virtual void copy(const ClpPackedMatrix * from);
378  virtual ClpMatrixBase * subsetClone (
379  int numberRows, const int * whichRows,
380  int numberColumns, const int * whichColumns) const ;
382  void specialRowCopy(ClpSimplex * model, const ClpMatrixBase * rowCopy);
384  void specialColumnCopy(ClpSimplex * model);
386  virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ;
388 private:
390  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
391  int * COIN_RESTRICT index,
392  double * COIN_RESTRICT array,
393  const double tolerance) const;
395  int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi,
396  const double * COIN_RESTRICT columnScale,
397  int * COIN_RESTRICT index,
398  double * COIN_RESTRICT array,
399  const double tolerance) const;
401  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
402  int * COIN_RESTRICT index,
403  double * COIN_RESTRICT array,
404  const unsigned char * status,
405  const double tolerance) const;
408  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
409  int * COIN_RESTRICT index,
410  double * COIN_RESTRICT array,
411  const unsigned char * status,
412  int * COIN_RESTRICT spareIndex,
413  double * COIN_RESTRICT spareArray,
414  const double * COIN_RESTRICT reducedCost,
415  double & upperTheta,
416  double & bestPossible,
417  double acceptablePivot,
418  double dualTolerance,
419  int & numberRemaining,
420  const double zeroTolerance) const;
422  int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi,
423  const double * COIN_RESTRICT columnScale,
424  int * COIN_RESTRICT index,
425  double * COIN_RESTRICT array,
426  const unsigned char * status,
427  const double tolerance) const;
429  int gutsOfTransposeTimesByRowGEK(const CoinIndexedVector * COIN_RESTRICT piVector,
430  int * COIN_RESTRICT index,
431  double * COIN_RESTRICT output,
432  int numberColumns,
433  const double tolerance,
434  const double scalar) const;
436  int gutsOfTransposeTimesByRowGE3(const CoinIndexedVector * COIN_RESTRICT piVector,
437  int * COIN_RESTRICT index,
438  double * COIN_RESTRICT output,
439  double * COIN_RESTRICT array2,
440  const double tolerance,
441  const double scalar) const;
443  int gutsOfTransposeTimesByRowGE3a(const CoinIndexedVector * COIN_RESTRICT piVector,
444  int * COIN_RESTRICT index,
445  double * COIN_RESTRICT output,
446  int * COIN_RESTRICT lookup,
447  char * COIN_RESTRICT marked,
448  const double tolerance,
449  const double scalar) const;
451  void gutsOfTransposeTimesByRowEQ2(const CoinIndexedVector * piVector, CoinIndexedVector * output,
452  CoinIndexedVector * spareVector, const double tolerance, const double scalar) const;
454  void gutsOfTransposeTimesByRowEQ1(const CoinIndexedVector * piVector, CoinIndexedVector * output,
455  const double tolerance, const double scalar) const;
457  void clearCopies();
458 
459 
460 protected:
462  void checkFlags(int type) const;
466  CoinPackedMatrix * matrix_;
477  mutable int flags_;
483 };
484 #ifdef THREAD
485 #include <pthread.h>
486 typedef struct {
487  double acceptablePivot;
488  const ClpSimplex * model;
489  double * spare;
490  int * spareIndex;
491  double * arrayTemp;
492  int * indexTemp;
493  int * numberInPtr;
494  double * bestPossiblePtr;
495  double * upperThetaPtr;
496  int * posFreePtr;
497  double * freePivotPtr;
498  int * numberOutPtr;
499  const unsigned short * count;
500  const double * pi;
501  const CoinBigIndex * rowStart;
502  const double * element;
503  const unsigned short * column;
504  int offset;
505  int numberInRowArray;
506  int numberLook;
507 } dualColumn0Struct;
508 #endif
510 
511 public:
517  void transposeTimes(const ClpSimplex * model,
518  const CoinPackedMatrix * rowCopy,
519  const CoinIndexedVector * x,
520  CoinIndexedVector * spareArray,
521  CoinIndexedVector * z) const;
523  inline bool usefulInfo() const {
524  return rowStart_ != NULL;
525  }
527 
528 
534  ClpPackedMatrix2(ClpSimplex * model, const CoinPackedMatrix * rowCopy);
536  virtual ~ClpPackedMatrix2();
538 
545 
546 
547 protected:
551  int numberBlocks_;
556  int * offset_;
558  mutable unsigned short * count_;
560  mutable CoinBigIndex * rowStart_;
562  unsigned short * column_;
564  double * work_;
565 #ifdef THREAD
566  pthread_t * threadId_;
567  dualColumn0Struct * info_;
568 #endif
569 
570 };
571 typedef struct {
572  CoinBigIndex startElements_; // point to data
573  int startIndices_; // point to column_
575  int numberPrice_; // at beginning
576  int numberElements_; // number elements per column
577 } blockStruct;
579 
580 public:
586  void transposeTimes(const ClpSimplex * model,
587  const double * pi,
588  CoinIndexedVector * output) const;
590  void transposeTimes2(const ClpSimplex * model,
591  const double * pi, CoinIndexedVector * dj1,
592  const double * piWeight,
593  double referenceIn, double devex,
594  // Array for exact devex to say what is in reference framework
595  unsigned int * reference,
596  double * weights, double scaleFactor);
598 
599 
605  ClpPackedMatrix3(ClpSimplex * model, const CoinPackedMatrix * columnCopy);
607  virtual ~ClpPackedMatrix3();
609 
616 
619  void sortBlocks(const ClpSimplex * model);
621  void swapOne(const ClpSimplex * model, const ClpPackedMatrix * matrix,
622  int iColumn);
624 
625 
626 protected:
630  int numberBlocks_;
635  int * column_;
637  CoinBigIndex * start_;
639  int * row_;
641  double * element_;
645 };
646 
647 #endif
virtual int getNumRows() const
Number of rows.
virtual int scale(ClpModel *model, const ClpSimplex *baseModel=NULL) const
Creates scales for column copy (rowCopy in model may be modified) returns non-zero if no scaling done...
virtual CoinBigIndex getNumElements() const
Number of entries in the packed matrix.
virtual void times(double scalar, const double *x, double *y) const
Return y + A * scalar *x in y.
ClpPackedMatrix3 * columnCopy_
Special column copy.
virtual bool isColOrdered() const
Whether the packed matrix is column major ordered or not.
virtual void replaceVector(const int index, const int numReplace, const double *newElements)
Replace the elements of a vector.
Abstract base class for Clp Matrices.
int flags_
Flags - 1 - has zero elements 2 - has gaps 4 - has special row copy 8 - has special column copy 16 - ...
virtual bool canDoPartialPricing() const
Says whether it can do partial pricing.
void specialRowCopy(ClpSimplex *model, const ClpMatrixBase *rowCopy)
make special row copy
virtual int appendMatrix(int number, int type, const CoinBigIndex *starts, const int *index, const double *element, int numberOther=-1)
Append a set of rows/columns to the end of the matrix.
void createScaledMatrix(ClpSimplex *model) const
Creates scaled column copy if scales exist.
virtual void subsetTransposeTimes(const ClpSimplex *model, const CoinIndexedVector *x, const CoinIndexedVector *y, CoinIndexedVector *z) const
Return x *A in z but just for indices in y.
int * offset_
Column offset for each block (plus one at end)
virtual void deleteCols(const int numDel, const int *indDel)
Delete the columns whose indices are listed in indDel.
virtual bool allElementsInRange(ClpModel *model, double smallest, double largest, int check=15)
Checks if all elements are in valid range.
virtual void add(const ClpSimplex *model, CoinIndexedVector *rowArray, int column, double multiplier) const
Adds multiple of a column into an CoinIndexedvector You can use quickAdd to add to vector...
void setMatrixNull()
Just sets matrix_ to NULL so it can be used elsewhere.
virtual void deleteRows(const int numDel, const int *indDel)
Delete the rows whose indices are listed in indDel.
void checkFlags(int type) const
Check validity.
virtual void unpackPacked(ClpSimplex *model, CoinIndexedVector *rowArray, int column) const
Unpacks a column into an CoinIndexedvector in packed foramt Note that model is NOT const...
void setNumberActiveColumns(int value)
Set number of active columns (normally same as number of columns)
int * column_
Column indices and reverse lookup (within block)
bool wantsSpecialColumnCopy() const
Do we want special column copy.
virtual void transposeTimes(double scalar, const double *x, double *y) const
Return y + x * scalar * A in y.
double * element_
Elements.
double reducedCost(ClpSimplex *model, int sequence) const
Returns reduced cost of a variable.
void transposeTimesByColumn(const ClpSimplex *model, double scalar, const CoinIndexedVector *x, CoinIndexedVector *y, CoinIndexedVector *z) const
Return x * scalar * A + y in z.
bool zeros() const
Are there zeros?
virtual void correctSequence(const ClpSimplex *model, int &sequenceIn, int &sequenceOut)
Correct sequence in and out to give true value.
CoinPackedMatrix * matrix_
Data.
virtual const CoinBigIndex * getVectorStarts() const
int flags() const
Flags.
virtual int getNumCols() const
Number of columns.
unsigned short * column_
columns within block
double * getMutableElements() const
Mutable elements.
virtual void copy(const ClpPackedMatrix *from)
Copy contents - resizing if necessary - otherwise re-use memory.
void specialColumnCopy(ClpSimplex *model)
make special column copy
virtual CoinPackedMatrix * getPackedMatrix() const
Return a complete CoinPackedMatrix.
virtual void fillBasis(ClpSimplex *model, const int *whichColumn, int &numberColumnBasic, int *row, int *start, int *rowCount, int *columnCount, CoinFactorizationDouble *element)
Fills in column part of basis.
This solves LPs using the simplex method.
Definition: ClpSimplex.hpp:55
CoinBigIndex * start_
Starts for odd/long vectors.
virtual const int * getIndices() const
A vector containing the minor indices of the elements in the packed matrix.
ClpPackedMatrix()
Default constructor.
virtual void appendRows(int number, const CoinPackedVectorBase *const *rows)
Append Rows.
virtual void releasePackedMatrix() const
Allow any parts of a created CoinPackedMatrix to be deleted.
#define COIN_RESTRICT
virtual const int * getVectorLengths() const
The lengths of the major-dimension vectors.
bool usefulInfo() const
Returns true if copy has useful information.
virtual void scaleRowCopy(ClpModel *model) const
Scales rowCopy if column copy scaled Only called if scales already exist.
virtual const double * getElements() const
A vector containing the elements in the packed matrix.
virtual void rangeOfElements(double &smallestNegative, double &largestNegative, double &smallestPositive, double &largestPositive)
Returns largest and smallest elements of both signs.
virtual CoinBigIndex countBasis(const int *whichColumn, int &numberColumnBasic)
Returns number of elements in column part of basis.
void checkGaps()
Sets flags_ correctly.
int numberActiveColumns_
number of active columns (normally same as number of columns)
virtual ClpMatrixBase * reverseOrderedCopy() const
Returns a new matrix in reverse order without gaps.
virtual void reallyScale(const double *rowScale, const double *columnScale)
int type() const
Returns type.
virtual void appendCols(int number, const CoinPackedVectorBase *const *columns)
Append Columns.
ClpPackedMatrix & operator=(const ClpPackedMatrix &)
int numberColumns_
Number of columns.
virtual void transposeTimesByRow(const ClpSimplex *model, double scalar, const CoinIndexedVector *x, CoinIndexedVector *y, CoinIndexedVector *z) const
Return x * scalar * A + y in z.
virtual void partialPricing(ClpSimplex *model, double start, double end, int &bestSequence, int &numberWanted)
Partial pricing.
void transposeTimesSubset(int number, const int *which, const double *pi, double *y, const double *rowScale, const double *columnScale, double *spare=NULL) const
Return y - pi * A in y.
unsigned short * count_
Counts of elements in each part of row.
CoinBigIndex startElements_
virtual void unpack(const ClpSimplex *model, CoinIndexedVector *rowArray, int column) const
Unpacks a column into an CoinIndexedvector.
virtual bool canCombine(const ClpSimplex *model, const CoinIndexedVector *pi) const
Returns true if can combine transposeTimes and subsetTransposeTimes and if it would be faster...
virtual CoinBigIndex * dubiousWeights(const ClpSimplex *model, int *inputWeights) const
Given positive integer weights for each row fills in sum of weights for each column (and slack)...
int numberActiveColumns() const
number of active columns (normally same as number of columns)
virtual void setDimensions(int numrows, int numcols)
Set the dimensions of the matrix.
virtual ClpMatrixBase * scaledColumnCopy(ClpModel *model) const
Realy really scales column copy Only called if scales already exist.
virtual ClpMatrixBase * clone() const
Clone.
void releaseSpecialColumnCopy()
Say we don&#39;t want special column copy.
void useEffectiveRhs(ClpSimplex *model)
Sets up an effective RHS.
virtual ~ClpPackedMatrix()
Destructor.
int numberRows_
Number of rows.
virtual int getVectorLength(int index) const
The length of a single major-dimension vector.
virtual void subsetTimes2(const ClpSimplex *model, CoinIndexedVector *dj1, const CoinIndexedVector *pi2, CoinIndexedVector *dj2, double referenceIn, double devex, unsigned int *reference, double *weights, double scaleFactor)
Updates second array for steepest and does devex weights.
virtual void modifyCoefficient(int row, int column, double newElement, bool keepZero=false)
Modify one element of packed matrix.
virtual int refresh(ClpSimplex *model)
makes sure active columns correct
ClpPackedMatrix2 * rowCopy_
Special row copy.
double * work_
work arrays
CoinBigIndex * rowStart_
Row starts.
blockStruct * block_
Blocks (ordinary start at 0 and go to first block)
CoinPackedMatrix * matrix() const
Returns CoinPackedMatrix (non const)
virtual void transposeTimes2(const ClpSimplex *model, const CoinIndexedVector *pi1, CoinIndexedVector *dj1, const CoinIndexedVector *pi2, CoinIndexedVector *spare, double referenceIn, double devex, unsigned int *reference, double *weights, double scaleFactor)
Updates two arrays for steepest.
virtual ClpMatrixBase * subsetClone(int numberRows, const int *whichRows, int numberColumns, const int *whichColumns) const
Subset clone (without gaps).
void makeSpecialColumnCopy()
Say we want special column copy.