source: trunk/Clp/src/ClpPackedMatrix.hpp @ 1034

Last change on this file since 1034 was 1034, checked in by forrest, 13 years ago

moving branches/devel to trunk

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.7 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpPackedMatrix_H
4#define ClpPackedMatrix_H
5
6#include "CoinPragma.hpp"
7
8#include "ClpMatrixBase.hpp"
9
10/** This implements CoinPackedMatrix as derived from ClpMatrixBase.
11
12    It adds a few methods that know about model as well as matrix
13
14    For details see CoinPackedMatrix */
15
16class ClpPackedMatrix2;
17class ClpPackedMatrix3;
18class ClpPackedMatrix : public ClpMatrixBase {
19 
20public:
21  /**@name Useful methods */
22   //@{
23   /// Return a complete CoinPackedMatrix
24  virtual CoinPackedMatrix * getPackedMatrix() const { return matrix_;};
25    /** Whether the packed matrix is column major ordered or not. */
26    virtual bool isColOrdered() const { return matrix_->isColOrdered(); }
27   /** Number of entries in the packed matrix. */
28  virtual  CoinBigIndex getNumElements() const 
29  { return matrix_->getNumElements(); }
30   /** Number of columns. */
31   virtual int getNumCols() const { return matrix_->getNumCols(); }
32   /** Number of rows. */
33  virtual int getNumRows() const { return matrix_->getNumRows(); };
34
35   /** A vector containing the elements in the packed matrix. Note that there
36        might be gaps in this list, entries that do not belong to any
37        major-dimension vector. To get the actual elements one should look at
38        this vector together with vectorStarts and vectorLengths. */
39   virtual const double * getElements() const 
40  { return matrix_->getElements();};
41   /** A vector containing the minor indices of the elements in the packed
42        matrix. Note that there might be gaps in this list, entries that do not
43        belong to any major-dimension vector. To get the actual elements one
44        should look at this vector together with vectorStarts and
45        vectorLengths. */
46   virtual const int * getIndices() const 
47  { return matrix_->getIndices();};
48
49   virtual const CoinBigIndex * getVectorStarts() const 
50  { return matrix_->getVectorStarts();};
51   /** The lengths of the major-dimension vectors. */
52   virtual const int * getVectorLengths() const 
53  { return matrix_->getVectorLengths();} ;
54  /** The length of a single major-dimension vector. */
55  virtual int getVectorLength(int index) const 
56  { return matrix_->getVectorSize(index);};
57
58    /** Delete the columns whose indices are listed in <code>indDel</code>. */
59  virtual void deleteCols(const int numDel, const int * indDel);
60    /** Delete the rows whose indices are listed in <code>indDel</code>. */
61  virtual void deleteRows(const int numDel, const int * indDel);
62#ifndef CLP_NO_VECTOR
63  /// Append Columns
64  virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
65  /// Append Rows
66  virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
67#endif
68  /** Append a set of rows/columns to the end of the matrix. Returns number of errors
69      i.e. if any of the new rows/columns contain an index that's larger than the
70      number of columns-1/rows-1 (if numberOther>0) or duplicates
71      If 0 then rows, 1 if columns */
72  virtual int appendMatrix(int number, int type,
73                           const CoinBigIndex * starts, const int * index,
74                           const double * element, int numberOther=-1);
75  /** Replace the elements of a vector.  The indices remain the same.
76      This is only needed if scaling and a row copy is used.
77      At most the number specified will be replaced.
78      The index is between 0 and major dimension of matrix */
79  virtual void replaceVector(const int index,
80                       const int numReplace, const double * newElements)
81      {matrix_->replaceVector(index,numReplace,newElements);};
82  /** Modify one element of packed matrix.  An element may be added.
83      This works for either ordering If the new element is zero it will be
84      deleted unless keepZero true */
85  virtual void modifyCoefficient(int row, int column, double newElement,
86                           bool keepZero=false)
87       {matrix_->modifyCoefficient(row, column, newElement, keepZero);}
88  /** Returns a new matrix in reverse order without gaps */
89  virtual ClpMatrixBase * reverseOrderedCopy() const;
90  /// Returns number of elements in column part of basis
91  virtual CoinBigIndex countBasis(ClpSimplex * model,
92                                 const int * whichColumn, 
93                                 int numberRowBasic,
94                                  int & numberColumnBasic);
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                                 double * element);
102  /** Creates scales for column copy (rowCopy in model may be modified)
103      returns non-zero if no scaling done */
104  virtual int scale(ClpModel * model) const ;
105  /** Scales rowCopy if column copy scaled
106      Only called if scales already exist */
107  virtual void scaleRowCopy(ClpModel * model) const ;
108  /** Realy really scales column copy
109      Only called if scales already exist.
110      Up to user ro delete */
111  virtual ClpMatrixBase * scaledColumnCopy(ClpModel * model) const ;
112  /** Checks if all elements are in valid range.  Can just
113      return true if you are not paranoid.  For Clp I will
114      probably expect no zeros.  Code can modify matrix to get rid of
115      small elements.
116      check bits (can be turned off to save time) :
117      1 - check if matrix has gaps
118      2 - check if zero elements
119      4 - check and compress duplicates
120      8 - report on large and small
121  */
122  virtual bool allElementsInRange(ClpModel * model,
123                                  double smallest, double largest,
124                                  int check=15);
125  /** Returns largest and smallest elements of both signs.
126      Largest refers to largest absolute value.
127  */
128  virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
129                       double & smallestPositive, double & largestPositive);
130
131  /** Unpacks a column into an CoinIndexedvector
132   */
133  virtual void unpack(const ClpSimplex * model,CoinIndexedVector * rowArray,
134                   int column) const ;
135  /** Unpacks a column into an CoinIndexedvector
136   ** in packed foramt
137      Note that model is NOT const.  Bounds and objective could
138      be modified if doing column generation (just for this variable) */
139  virtual void unpackPacked(ClpSimplex * model,
140                            CoinIndexedVector * rowArray,
141                            int column) const;
142  /** Adds multiple of a column into an CoinIndexedvector
143      You can use quickAdd to add to vector */
144  virtual void add(const ClpSimplex * model,CoinIndexedVector * rowArray,
145                   int column, double multiplier) const ;
146  /** Adds multiple of a column into an array */
147  virtual void add(const ClpSimplex * model,double * array,
148                   int column, double multiplier) const;
149   /// Allow any parts of a created CoinPackedMatrix to be deleted
150   virtual void releasePackedMatrix() const { };
151  /** Given positive integer weights for each row fills in sum of weights
152      for each column (and slack).
153      Returns weights vector
154  */
155  virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model,int * inputWeights) const;
156  /// Says whether it can do partial pricing
157  virtual bool canDoPartialPricing() const;
158  /// Partial pricing
159  virtual void partialPricing(ClpSimplex * model, double start, double end,
160                      int & bestSequence, int & numberWanted);
161  /// makes sure active columns correct
162  virtual int refresh(ClpSimplex * model);
163  // Really scale matrix
164  virtual void reallyScale(const double * rowScale, const double * columnScale);
165  /** Set the dimensions of the matrix. In effect, append new empty
166      columns/rows to the matrix. A negative number for either dimension
167      means that that dimension doesn't change. Otherwise the new dimensions
168      MUST be at least as large as the current ones otherwise an exception
169      is thrown. */
170  virtual void setDimensions(int numrows, int numcols);
171   //@}
172
173  /**@name Matrix times vector methods */
174  //@{
175    /** Return <code>y + A * scalar *x</code> in <code>y</code>.
176        @pre <code>x</code> must be of size <code>numColumns()</code>
177        @pre <code>y</code> must be of size <code>numRows()</code> */
178  virtual void times(double scalar,
179                       const double * x, double * y) const;
180  /// And for scaling
181  virtual void times(double scalar,
182                     const double * x, double * y,
183                     const double * rowScale, 
184                     const double * columnScale) const;
185    /** Return <code>y + x * scalar * A</code> in <code>y</code>.
186        @pre <code>x</code> must be of size <code>numRows()</code>
187        @pre <code>y</code> must be of size <code>numColumns()</code> */
188    virtual void transposeTimes(double scalar,
189                                const double * x, double * y) const;
190  /// And for scaling
191    virtual void transposeTimes(double scalar,
192                                const double * x, double * y,
193                                const double * rowScale, 
194                                const double * columnScale,
195                                double * spare=NULL) const;
196    /** Return <code>x * scalar * A + y</code> in <code>z</code>.
197        Can use y as temporary array (will be empty at end)
198        Note - If x packed mode - then z packed mode
199        Squashes small elements and knows about ClpSimplex */
200  virtual void transposeTimes(const ClpSimplex * model, double scalar,
201                              const CoinIndexedVector * x,
202                              CoinIndexedVector * y,
203                              CoinIndexedVector * z) const;
204    /** Return <code>x * scalar * A + y</code> in <code>z</code>.
205        Note - If x packed mode - then z packed mode
206        This does by column and knows no gaps
207        Squashes small elements and knows about ClpSimplex */
208  void transposeTimesByColumn(const ClpSimplex * model, double scalar,
209                              const CoinIndexedVector * x,
210                              CoinIndexedVector * y,
211                              CoinIndexedVector * z) const;
212    /** Return <code>x * scalar * A + y</code> in <code>z</code>.
213        Can use y as temporary array (will be empty at end)
214        Note - If x packed mode - then z packed mode
215        Squashes small elements and knows about ClpSimplex.
216    This version uses row copy*/
217  virtual void transposeTimesByRow(const ClpSimplex * model, double scalar,
218                              const CoinIndexedVector * x,
219                              CoinIndexedVector * y,
220                              CoinIndexedVector * z) const;
221    /** Return <code>x *A</code> in <code>z</code> but
222        just for indices in y.
223        Note - z always packed mode */
224  virtual void subsetTransposeTimes(const ClpSimplex * model,
225                                    const CoinIndexedVector * x,
226                                    const CoinIndexedVector * y,
227                                    CoinIndexedVector * z) const;
228  /** Returns true if can combine transposeTimes and subsetTransposeTimes
229      and if it would be faster */
230  virtual bool canCombine(const ClpSimplex * model,
231                          const CoinIndexedVector * pi) const;
232  /// Updates two arrays for steepest
233  virtual void transposeTimes2(const ClpSimplex * model,
234                               const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
235                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
236                               CoinIndexedVector * spare,
237                               double referenceIn, double devex,
238                               // Array for exact devex to say what is in reference framework
239                               unsigned int * reference,
240                               double * weights, double scaleFactor);
241  /// Updates second array for steepest and does devex weights
242  virtual void subsetTimes2(const ClpSimplex * model,
243                                CoinIndexedVector * dj1,
244                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
245                               double referenceIn, double devex,
246                               // Array for exact devex to say what is in reference framework
247                               unsigned int * reference,
248                               double * weights, double scaleFactor);
249  /// Sets up an effective RHS
250  void useEffectiveRhs(ClpSimplex * model);
251//@}
252
253  /**@name Other */
254   //@{
255  /// Returns CoinPackedMatrix (non const)
256  inline CoinPackedMatrix * matrix() const { return matrix_;};
257  /** Just sets matrix_ to NULL so it can be used elsewhere.
258      used in GUB
259  */
260  inline void setMatrixNull()
261  { matrix_=NULL;};
262  /// Say we want special column copy
263  inline void makeSpecialColumnCopy()
264  { flags_ |= 8;};
265  /// Say we don't want special column copy
266  void releaseSpecialColumnCopy();
267  /// Are there zeros?
268  inline bool zeros() const
269  { return ((flags_&1)!=0);};
270  /// Do we want special column copy
271  inline bool wantsSpecialColumnCopy() const
272  { return ((flags_&8)!=0);};
273   //@}
274
275
276  /**@name Constructors, destructor */
277   //@{
278   /** Default constructor. */
279   ClpPackedMatrix();
280   /** Destructor */
281   virtual ~ClpPackedMatrix();
282   //@}
283
284   /**@name Copy method */
285   //@{
286   /** The copy constructor. */
287   ClpPackedMatrix(const ClpPackedMatrix&);
288   /** The copy constructor from an CoinPackedMatrix. */
289   ClpPackedMatrix(const CoinPackedMatrix&);
290  /** Subset constructor (without gaps).  Duplicates are allowed
291      and order is as given */
292  ClpPackedMatrix (const ClpPackedMatrix & wholeModel,
293                    int numberRows, const int * whichRows,
294                    int numberColumns, const int * whichColumns);
295  ClpPackedMatrix (const CoinPackedMatrix & wholeModel,
296                    int numberRows, const int * whichRows,
297                    int numberColumns, const int * whichColumns);
298
299  /** This takes over ownership (for space reasons) */
300   ClpPackedMatrix(CoinPackedMatrix * matrix);
301
302   ClpPackedMatrix& operator=(const ClpPackedMatrix&);
303  /// Clone
304  virtual ClpMatrixBase * clone() const ;
305  /** Subset clone (without gaps).  Duplicates are allowed
306      and order is as given */
307  virtual ClpMatrixBase * subsetClone (
308                    int numberRows, const int * whichRows,
309                    int numberColumns, const int * whichColumns) const ;
310  /// make special row copy
311  void specialRowCopy(ClpSimplex * model,const ClpMatrixBase * rowCopy); 
312  /// make special column copy
313  void specialColumnCopy(ClpSimplex * model); 
314  /// Correct sequence in and out to give true value
315  virtual void correctSequence(const ClpSimplex * model,int & sequenceIn, int & sequenceOut) ;
316   //@}
317private:
318  /// Meat of transposeTimes by column when not scaled
319  void gutsOfTransposeTimesUnscaled(const double * pi,CoinIndexedVector * output, const double tolerance) const;
320  /// Meat of transposeTimes by column when scaled
321  void gutsOfTransposeTimesScaled(const double * pi,const double * columnScale, CoinIndexedVector * output, const double tolerance) const;
322  /// Meat of transposeTimes by row n > 2 if packed
323  void gutsOfTransposeTimesByRowGE3(const CoinIndexedVector * piVector, CoinIndexedVector * output,
324                                   CoinIndexedVector * spareVector, const double tolerance, const double scalar) const;
325  /// Meat of transposeTimes by row n == 2 if packed
326  void gutsOfTransposeTimesByRowEQ2(const CoinIndexedVector * piVector, CoinIndexedVector * output,
327                                   CoinIndexedVector * spareVector, const double tolerance, const double scalar) const;
328  /// Meat of transposeTimes by row n == 1 if packed
329  void gutsOfTransposeTimesByRowEQ1(const CoinIndexedVector * piVector, CoinIndexedVector * output,
330                                   const double tolerance, const double scalar) const;
331  /// Gets rid of special copies
332  void clearCopies();
333   
334   
335protected:
336  /// Check validity
337  void checkFlags() const;
338   /**@name Data members
339      The data members are protected to allow access for derived classes. */
340   //@{
341  /// Data
342  CoinPackedMatrix * matrix_;
343  /// number of active columns (normally same as number of columns)
344  int numberActiveColumns_;
345  /** Flags -
346      1 - has zero elements
347      2 - has gaps
348      4 - has special row copy
349      8 - has special column copy
350  */
351  int flags_;
352  /// Special row copy
353  ClpPackedMatrix2 * rowCopy_;
354  /// Special column copy
355  ClpPackedMatrix3 * columnCopy_;
356   //@}
357};
358#ifdef THREAD
359#include <pthread.h>
360typedef struct {
361  double acceptablePivot;
362  const ClpSimplex * model;
363  double * spare;
364  int * spareIndex;
365  double * arrayTemp;
366  int * indexTemp;
367  int * numberInPtr;
368  double * bestPossiblePtr;
369  double * upperThetaPtr;
370  int * posFreePtr;
371  double * freePivotPtr;
372  int * numberOutPtr;
373  const unsigned short * count;
374  const double * pi;
375  const CoinBigIndex * rowStart;
376  const double * element;
377  const unsigned short * column;
378  int offset;
379  int numberInRowArray;
380  int numberLook;
381} dualColumn0Struct;
382#endif
383class ClpPackedMatrix2 {
384 
385public:
386  /**@name Useful methods */
387  //@{
388    /** Return <code>x * -1 * A in <code>z</code>.
389        Note - x packed and z will be packed mode
390        Squashes small elements and knows about ClpSimplex */
391  void transposeTimes(const ClpSimplex * model,
392                      const CoinPackedMatrix * rowCopy,
393                      const CoinIndexedVector * x,
394                      CoinIndexedVector * spareArray,
395                      CoinIndexedVector * z) const;
396  /// Returns true if copy has useful information
397  inline bool usefulInfo() const
398  { return rowStart_!=NULL;};
399  //@}
400
401
402  /**@name Constructors, destructor */
403   //@{
404   /** Default constructor. */
405   ClpPackedMatrix2();
406   /** Constructor from copy. */
407   ClpPackedMatrix2(ClpSimplex * model,const CoinPackedMatrix * rowCopy);
408   /** Destructor */
409   virtual ~ClpPackedMatrix2();
410   //@}
411
412   /**@name Copy method */
413   //@{
414   /** The copy constructor. */
415   ClpPackedMatrix2(const ClpPackedMatrix2&);
416   ClpPackedMatrix2& operator=(const ClpPackedMatrix2&);
417   //@}
418   
419   
420protected:
421   /**@name Data members
422      The data members are protected to allow access for derived classes. */
423   //@{
424  /// Number of blocks
425  int numberBlocks_;
426  /// Number of rows
427  int numberRows_;
428  /// Column offset for each block (plus one at end)
429  int * offset_;
430  /// Counts of elements in each part of row
431  mutable unsigned short * count_;
432  /// Row starts
433  mutable CoinBigIndex * rowStart_;
434  /// columns within block
435  unsigned short * column_;
436  /// work arrays
437  double * work_;
438#ifdef THREAD
439  pthread_t * threadId_;
440  dualColumn0Struct * info_;
441#endif
442   //@}
443};
444typedef struct {
445  CoinBigIndex startElements_; // point to data
446  int startIndices_; // point to column_
447  int numberInBlock_; 
448  int numberPrice_; // at beginning
449  int numberElements_; // number elements per column
450} blockStruct;
451class ClpPackedMatrix3 {
452 
453public:
454  /**@name Useful methods */
455  //@{
456    /** Return <code>x * -1 * A in <code>z</code>.
457        Note - x packed and z will be packed mode
458        Squashes small elements and knows about ClpSimplex */
459  void transposeTimes(const ClpSimplex * model,
460                      const double * pi,
461                      CoinIndexedVector * output) const;
462  /// Updates two arrays for steepest
463  void transposeTimes2(const ClpSimplex * model,
464                       const double * pi, CoinIndexedVector * dj1,
465                       const double * piWeight,
466                       double referenceIn, double devex,
467                       // Array for exact devex to say what is in reference framework
468                       unsigned int * reference,
469                       double * weights, double scaleFactor);
470  //@}
471
472
473  /**@name Constructors, destructor */
474   //@{
475   /** Default constructor. */
476   ClpPackedMatrix3();
477   /** Constructor from copy. */
478   ClpPackedMatrix3(ClpSimplex * model,const CoinPackedMatrix * columnCopy);
479   /** Destructor */
480   virtual ~ClpPackedMatrix3();
481   //@}
482
483   /**@name Copy method */
484   //@{
485   /** The copy constructor. */
486   ClpPackedMatrix3(const ClpPackedMatrix3&);
487   ClpPackedMatrix3& operator=(const ClpPackedMatrix3&);
488   //@}
489   /**@name Sort methods */
490   //@{
491   /** Sort blocks */
492  void sortBlocks(const ClpSimplex * model);
493  /// Swap one variable
494  void swapOne(const ClpSimplex * model,const ClpPackedMatrix * matrix,
495                int iColumn);
496   //@}
497   
498   
499protected:
500   /**@name Data members
501      The data members are protected to allow access for derived classes. */
502   //@{
503  /// Number of blocks
504  int numberBlocks_;
505  /// Number of columns
506  int numberColumns_;
507  /// Column indices and reverse lookup (within block)
508  int * column_;
509  /// Starts for odd/long vectors
510  CoinBigIndex * start_;
511  /// Rows
512  int * row_;
513  /// Elements
514  double * element_;
515  /// Blocks (ordinary start at 0 and go to first block)
516  blockStruct * block_;
517   //@}
518};
519
520#endif
Note: See TracBrowser for help on using the repository browser.