Clp  1.16.6
ClpPackedMatrix.hpp
Go to the documentation of this file.
1 /* $Id: ClpPackedMatrix.hpp 2078 2015-01-05 12:39:49Z forrest $ */
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 
19 class ClpPackedMatrix2;
20 class ClpPackedMatrix3;
22 
23 public:
26  virtual CoinPackedMatrix * getPackedMatrix() const {
28  return matrix_;
29  }
31  virtual bool isColOrdered() const {
32  return matrix_->isColOrdered();
33  }
35  virtual CoinBigIndex getNumElements() const {
36  return matrix_->getNumElements();
37  }
39  virtual int getNumCols() const {
40  return matrix_->getNumCols();
41  }
43  virtual int getNumRows() const {
44  return matrix_->getNumRows();
45  }
46 
51  virtual const double * getElements() const {
52  return matrix_->getElements();
53  }
55  inline double * getMutableElements() const {
56  return matrix_->getMutableElements();
57  }
63  virtual const int * getIndices() const {
64  return matrix_->getIndices();
65  }
66 
67  virtual const CoinBigIndex * getVectorStarts() const {
68  return matrix_->getVectorStarts();
69  }
71  virtual const int * getVectorLengths() const {
72  return matrix_->getVectorLengths();
73  }
75  virtual int getVectorLength(int index) const {
76  return matrix_->getVectorSize(index);
77  }
78 
80  virtual void deleteCols(const int numDel, const int * indDel);
82  virtual void deleteRows(const int numDel, const int * indDel);
83 #ifndef CLP_NO_VECTOR
84  virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
87  virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
88 #endif
89 
93  virtual int appendMatrix(int number, int type,
94  const CoinBigIndex * starts, const int * index,
95  const double * element, int numberOther = -1);
100  virtual void replaceVector(const int index,
101  const int numReplace, const double * newElements) {
102  matrix_->replaceVector(index, numReplace, newElements);
103  }
107  virtual void modifyCoefficient(int row, int column, double newElement,
108  bool keepZero = false) {
109  matrix_->modifyCoefficient(row, column, newElement, keepZero);
110  }
112  virtual ClpMatrixBase * reverseOrderedCopy() const;
114  virtual CoinBigIndex countBasis(const int * whichColumn,
115  int & numberColumnBasic);
117  virtual void fillBasis(ClpSimplex * model,
118  const int * whichColumn,
119  int & numberColumnBasic,
120  int * row, int * start,
121  int * rowCount, int * columnCount,
122  CoinFactorizationDouble * element);
125  virtual int scale(ClpModel * model, const ClpSimplex * baseModel = NULL) const ;
128  virtual void scaleRowCopy(ClpModel * model) const ;
130  void createScaledMatrix(ClpSimplex * model) const;
134  virtual ClpMatrixBase * scaledColumnCopy(ClpModel * model) const ;
145  virtual bool allElementsInRange(ClpModel * model,
146  double smallest, double largest,
147  int check = 15);
151  virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
152  double & smallestPositive, double & largestPositive);
153 
156  virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray,
157  int column) const ;
162  virtual void unpackPacked(ClpSimplex * model,
163  CoinIndexedVector * rowArray,
164  int column) const;
167  virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray,
168  int column, double multiplier) const ;
170  virtual void add(const ClpSimplex * model, double * array,
171  int column, double multiplier) const;
173  virtual void releasePackedMatrix() const { }
178  virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model, int * inputWeights) const;
180  virtual bool canDoPartialPricing() const;
182  virtual void partialPricing(ClpSimplex * model, double start, double end,
183  int & bestSequence, int & numberWanted);
185  virtual int refresh(ClpSimplex * model);
186  // Really scale matrix
187  virtual void reallyScale(const double * rowScale, const double * columnScale);
193  virtual void setDimensions(int numrows, int numcols);
195 
201  virtual void times(double scalar,
202  const double * x, double * y) const;
204  virtual void times(double scalar,
205  const double * x, double * y,
206  const double * rowScale,
207  const double * columnScale) const;
211  virtual void transposeTimes(double scalar,
212  const double * x, double * y) const;
214  virtual void transposeTimes(double scalar,
215  const double * x, double * y,
216  const double * rowScale,
217  const double * columnScale,
218  double * spare = NULL) const;
223  void transposeTimesSubset( int number,
224  const int * which,
225  const double * pi, double * y,
226  const double * rowScale,
227  const double * columnScale,
228  double * spare = NULL) const;
233  virtual void transposeTimes(const ClpSimplex * model, double scalar,
234  const CoinIndexedVector * x,
235  CoinIndexedVector * y,
236  CoinIndexedVector * z) const;
241  void transposeTimesByColumn(const ClpSimplex * model, double scalar,
242  const CoinIndexedVector * x,
243  CoinIndexedVector * y,
244  CoinIndexedVector * z) const;
250  virtual void transposeTimesByRow(const ClpSimplex * model, double scalar,
251  const CoinIndexedVector * x,
252  CoinIndexedVector * y,
253  CoinIndexedVector * z) const;
257  virtual void subsetTransposeTimes(const ClpSimplex * model,
258  const CoinIndexedVector * x,
259  const CoinIndexedVector * y,
260  CoinIndexedVector * z) const;
263  virtual bool canCombine(const ClpSimplex * model,
264  const CoinIndexedVector * pi) const;
266  virtual void transposeTimes2(const ClpSimplex * model,
267  const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
268  const CoinIndexedVector * pi2,
269  CoinIndexedVector * spare,
270  double referenceIn, double devex,
271  // Array for exact devex to say what is in reference framework
272  unsigned int * reference,
273  double * weights, double scaleFactor);
275  virtual void subsetTimes2(const ClpSimplex * model,
276  CoinIndexedVector * dj1,
277  const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
278  double referenceIn, double devex,
279  // Array for exact devex to say what is in reference framework
280  unsigned int * reference,
281  double * weights, double scaleFactor);
283  void useEffectiveRhs(ClpSimplex * model);
284 #if COIN_LONG_WORK
285  // For long double versions
286  virtual void times(CoinWorkDouble scalar,
287  const CoinWorkDouble * x, CoinWorkDouble * y) const ;
288  virtual void transposeTimes(CoinWorkDouble scalar,
289  const CoinWorkDouble * x, CoinWorkDouble * y) const ;
290 #endif
291 
292 
295  inline CoinPackedMatrix * matrix() const {
297  return matrix_;
298  }
302  inline void setMatrixNull() {
303  matrix_ = NULL;
304  }
306  inline void makeSpecialColumnCopy() {
307  flags_ |= 16;
308  }
312  inline bool zeros() const {
313  return ((flags_ & 1) != 0);
314  }
316  inline bool wantsSpecialColumnCopy() const {
317  return ((flags_ & 16) != 0);
318  }
320  inline int flags() const {
321  return flags_;
322  }
324  inline void checkGaps() {
325  flags_ = (matrix_->hasGaps()) ? (flags_ | 2) : (flags_ & (~2));
326  }
328  inline int numberActiveColumns() const
329  { return numberActiveColumns_;}
331  inline void setNumberActiveColumns(int value)
332  { numberActiveColumns_ = value;}
334 
335 
339  ClpPackedMatrix();
341  virtual ~ClpPackedMatrix();
343 
349  ClpPackedMatrix(const CoinPackedMatrix&);
352  ClpPackedMatrix (const ClpPackedMatrix & wholeModel,
353  int numberRows, const int * whichRows,
354  int numberColumns, const int * whichColumns);
355  ClpPackedMatrix (const CoinPackedMatrix & wholeModel,
356  int numberRows, const int * whichRows,
357  int numberColumns, const int * whichColumns);
358 
360  ClpPackedMatrix(CoinPackedMatrix * matrix);
361 
364  virtual ClpMatrixBase * clone() const ;
366  virtual void copy(const ClpPackedMatrix * from);
369  virtual ClpMatrixBase * subsetClone (
370  int numberRows, const int * whichRows,
371  int numberColumns, const int * whichColumns) const ;
373  void specialRowCopy(ClpSimplex * model, const ClpMatrixBase * rowCopy);
375  void specialColumnCopy(ClpSimplex * model);
377  virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ;
379 private:
381  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
382  int * COIN_RESTRICT index,
383  double * COIN_RESTRICT array,
384  const double tolerance) const;
386  int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi,
387  const double * COIN_RESTRICT columnScale,
388  int * COIN_RESTRICT index,
389  double * COIN_RESTRICT array,
390  const double tolerance) const;
392  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
393  int * COIN_RESTRICT index,
394  double * COIN_RESTRICT array,
395  const unsigned char * status,
396  const double tolerance) const;
399  int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi,
400  int * COIN_RESTRICT index,
401  double * COIN_RESTRICT array,
402  const unsigned char * status,
403  int * COIN_RESTRICT spareIndex,
404  double * COIN_RESTRICT spareArray,
405  const double * COIN_RESTRICT reducedCost,
406  double & upperTheta,
407  double & bestPossible,
408  double acceptablePivot,
409  double dualTolerance,
410  int & numberRemaining,
411  const double zeroTolerance) const;
413  int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi,
414  const double * COIN_RESTRICT columnScale,
415  int * COIN_RESTRICT index,
416  double * COIN_RESTRICT array,
417  const unsigned char * status,
418  const double tolerance) const;
420  int gutsOfTransposeTimesByRowGEK(const CoinIndexedVector * COIN_RESTRICT piVector,
421  int * COIN_RESTRICT index,
422  double * COIN_RESTRICT output,
423  int numberColumns,
424  const double tolerance,
425  const double scalar) const;
427  int gutsOfTransposeTimesByRowGE3(const CoinIndexedVector * COIN_RESTRICT piVector,
428  int * COIN_RESTRICT index,
429  double * COIN_RESTRICT output,
430  double * COIN_RESTRICT array2,
431  const double tolerance,
432  const double scalar) const;
434  int gutsOfTransposeTimesByRowGE3a(const CoinIndexedVector * COIN_RESTRICT piVector,
435  int * COIN_RESTRICT index,
436  double * COIN_RESTRICT output,
437  int * COIN_RESTRICT lookup,
438  char * COIN_RESTRICT marked,
439  const double tolerance,
440  const double scalar) const;
442  void gutsOfTransposeTimesByRowEQ2(const CoinIndexedVector * piVector, CoinIndexedVector * output,
443  CoinIndexedVector * spareVector, const double tolerance, const double scalar) const;
445  void gutsOfTransposeTimesByRowEQ1(const CoinIndexedVector * piVector, CoinIndexedVector * output,
446  const double tolerance, const double scalar) const;
448  void clearCopies();
449 
450 
451 protected:
453  void checkFlags(int type) const;
457  CoinPackedMatrix * matrix_;
468  mutable int flags_;
474 };
475 #ifdef THREAD
476 #include <pthread.h>
477 typedef struct {
478  double acceptablePivot;
479  const ClpSimplex * model;
480  double * spare;
481  int * spareIndex;
482  double * arrayTemp;
483  int * indexTemp;
484  int * numberInPtr;
485  double * bestPossiblePtr;
486  double * upperThetaPtr;
487  int * posFreePtr;
488  double * freePivotPtr;
489  int * numberOutPtr;
490  const unsigned short * count;
491  const double * pi;
492  const CoinBigIndex * rowStart;
493  const double * element;
494  const unsigned short * column;
495  int offset;
496  int numberInRowArray;
497  int numberLook;
498 } dualColumn0Struct;
499 #endif
501 
502 public:
508  void transposeTimes(const ClpSimplex * model,
509  const CoinPackedMatrix * rowCopy,
510  const CoinIndexedVector * x,
511  CoinIndexedVector * spareArray,
512  CoinIndexedVector * z) const;
514  inline bool usefulInfo() const {
515  return rowStart_ != NULL;
516  }
518 
519 
525  ClpPackedMatrix2(ClpSimplex * model, const CoinPackedMatrix * rowCopy);
527  virtual ~ClpPackedMatrix2();
529 
536 
537 
538 protected:
542  int numberBlocks_;
547  int * offset_;
549  mutable unsigned short * count_;
551  mutable CoinBigIndex * rowStart_;
553  unsigned short * column_;
555  double * work_;
556 #ifdef THREAD
557  pthread_t * threadId_;
558  dualColumn0Struct * info_;
559 #endif
560 
561 };
562 typedef struct {
563  CoinBigIndex startElements_; // point to data
564  int startIndices_; // point to column_
566  int numberPrice_; // at beginning
567  int numberElements_; // number elements per column
568 } blockStruct;
570 
571 public:
577  void transposeTimes(const ClpSimplex * model,
578  const double * pi,
579  CoinIndexedVector * output) const;
581  void transposeTimes2(const ClpSimplex * model,
582  const double * pi, CoinIndexedVector * dj1,
583  const double * piWeight,
584  double referenceIn, double devex,
585  // Array for exact devex to say what is in reference framework
586  unsigned int * reference,
587  double * weights, double scaleFactor);
589 
590 
596  ClpPackedMatrix3(ClpSimplex * model, const CoinPackedMatrix * columnCopy);
598  virtual ~ClpPackedMatrix3();
600 
607 
610  void sortBlocks(const ClpSimplex * model);
612  void swapOne(const ClpSimplex * model, const ClpPackedMatrix * matrix,
613  int iColumn);
615 
616 
617 protected:
621  int numberBlocks_;
626  int * column_;
628  CoinBigIndex * start_;
630  int * row_;
632  double * element_;
636 };
637 
638 #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.
ClpPackedMatrix2 & operator=(const ClpPackedMatrix2 &)
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 transposeTimes(const ClpSimplex *model, const CoinPackedMatrix *rowCopy, const CoinIndexedVector *x, CoinIndexedVector *spareArray, CoinIndexedVector *z) const
Return x * -1 * A in z.
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.
void swapOne(const ClpSimplex *model, const ClpPackedMatrix *matrix, int iColumn)
Swap one variable.
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.
#define COIN_RESTRICT
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:70
CoinBigIndex * start_
Starts for odd/long vectors.
virtual ~ClpPackedMatrix3()
Destructor.
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.
virtual ClpMatrixBase * reverseOrderedCopy() const
Returns a new matrix in reverse order without gaps.
virtual ~ClpPackedMatrix2()
Destructor.
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.
int numberBlocks_
Number of blocks.
void transposeTimes2(const ClpSimplex *model, const double *pi, CoinIndexedVector *dj1, const double *piWeight, double referenceIn, double devex, unsigned int *reference, double *weights, double scaleFactor)
Updates two arrays for steepest.
void releaseSpecialColumnCopy()
Say we don't want special column copy.
void useEffectiveRhs(ClpSimplex *model)
Sets up an effective RHS.
void transposeTimes(const ClpSimplex *model, const double *pi, CoinIndexedVector *output) const
Return x * -1 * A in z.
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).
void sortBlocks(const ClpSimplex *model)
Sort blocks.
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)
ClpPackedMatrix3 & operator=(const ClpPackedMatrix3 &)
ClpPackedMatrix2()
Default constructor.
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.
int numberBlocks_
Number of blocks.
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...
ClpPackedMatrix3()
Default constructor.
void makeSpecialColumnCopy()
Say we want special column copy.