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
bool usefulInfo() const
Returns true if copy has useful information.
ClpPackedMatrix3 * columnCopy_
Special column copy.
virtual void replaceVector(const int index, const int numReplace, const double *newElements)
Replace the elements of a vector.
int type() const
Returns type.
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.
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...
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 void scaleRowCopy(ClpModel *model) const
Scales rowCopy if column copy scaled Only called if scales already exist.
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 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.
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 int getNumRows() const
Number of rows.
void setMatrixNull()
Just sets matrix_ to NULL so it can be used elsewhere.
double reducedCost(ClpSimplex *model, int sequence) const
Returns reduced cost of a variable.
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 ClpMatrixBase * clone() const
Clone.
void createScaledMatrix(ClpSimplex *model) const
Creates scaled column copy if scales exist.
void setNumberActiveColumns(int value)
Set number of active columns (normally same as number of columns)
int * column_
Column indices and reverse lookup (within block)
int numberActiveColumns() const
number of active columns (normally same as number of columns)
double * element_
Elements.
virtual void times(double scalar, const double *x, double *y) const
Return y + A * scalar *x in y.
virtual CoinBigIndex getNumElements() const
Number of entries in the packed matrix.
virtual const CoinBigIndex * getVectorStarts() const
virtual void correctSequence(const ClpSimplex *model, int &sequenceIn, int &sequenceOut)
Correct sequence in and out to give true value.
CoinPackedMatrix * matrix_
Data.
virtual CoinPackedMatrix * getPackedMatrix() const
Return a complete CoinPackedMatrix.
unsigned short * column_
columns within block
virtual void copy(const ClpPackedMatrix *from)
Copy contents - resizing if necessary - otherwise re-use memory.
void specialColumnCopy(ClpSimplex *model)
make special column copy
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.
ClpPackedMatrix()
Default constructor.
virtual void appendRows(int number, const CoinPackedVectorBase *const *rows)
Append Rows.
virtual ClpMatrixBase * scaledColumnCopy(ClpModel *model) const
Realy really scales column copy Only called if scales already exist.
void transposeTimesByColumn(const ClpSimplex *model, double scalar, const CoinIndexedVector *x, CoinIndexedVector *y, CoinIndexedVector *z) const
Return x * scalar * A + y in z.
virtual void releasePackedMatrix() const
Allow any parts of a created CoinPackedMatrix to be deleted.
#define COIN_RESTRICT
virtual ClpMatrixBase * reverseOrderedCopy() const
Returns a new matrix in reverse order without gaps.
virtual bool canDoPartialPricing() const
Says whether it can do partial pricing.
virtual void rangeOfElements(double &smallestNegative, double &largestNegative, double &smallestPositive, double &largestPositive)
Returns largest and smallest elements of both signs.
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 countBasis(const int *whichColumn, int &numberColumnBasic)
Returns number of elements in column part of basis.
bool zeros() const
Are there zeros?
void checkGaps()
Sets flags_ correctly.
virtual int getVectorLength(int index) const
The length of a single major-dimension vector.
virtual void unpack(const ClpSimplex *model, CoinIndexedVector *rowArray, int column) const
Unpacks a column into an CoinIndexedvector.
virtual void transposeTimesByRow(const ClpSimplex *model, double scalar, const CoinIndexedVector *x, CoinIndexedVector *y, CoinIndexedVector *z) const
Return x * scalar * A + y in z.
int numberActiveColumns_
number of active columns (normally same as number of columns)
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)...
virtual void reallyScale(const double *rowScale, const double *columnScale)
int flags() const
Flags.
virtual void appendCols(int number, const CoinPackedVectorBase *const *columns)
Append Columns.
ClpPackedMatrix & operator=(const ClpPackedMatrix &)
virtual const double * getElements() const
A vector containing the elements in the packed matrix.
virtual bool isColOrdered() const
Whether the packed matrix is column major ordered or not.
int numberColumns_
Number of columns.
virtual void transposeTimes(double scalar, const double *x, double *y) const
Return y + x * scalar * A in y.
bool wantsSpecialColumnCopy() const
Do we want special column copy.
virtual void partialPricing(ClpSimplex *model, double start, double end, int &bestSequence, int &numberWanted)
Partial pricing.
virtual const int * getVectorLengths() const
The lengths of the major-dimension vectors.
unsigned short * count_
Counts of elements in each part of row.
CoinBigIndex startElements_
CoinPackedMatrix * matrix() const
Returns CoinPackedMatrix (non const)
virtual void setDimensions(int numrows, int numcols)
Set the dimensions of the matrix.
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 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 ClpMatrixBase * subsetClone(int numberRows, const int *whichRows, int numberColumns, const int *whichColumns) const
Subset clone (without gaps).
virtual int refresh(ClpSimplex *model)
makes sure active columns correct
ClpPackedMatrix2 * rowCopy_
Special row copy.
double * work_
work arrays
CoinBigIndex * rowStart_
Row starts.
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...
virtual const int * getIndices() const
A vector containing the minor indices of the elements in the packed matrix.
blockStruct * block_
Blocks (ordinary start at 0 and go to first block)
virtual int getNumCols() const
Number of columns.
double * getMutableElements() const
Mutable elements.
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 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...
void makeSpecialColumnCopy()
Say we want special column copy.