source: stable/1.11/Clp/src/ClpMatrixBase.hpp @ 1458

Last change on this file since 1458 was 1458, checked in by forrest, 11 years ago

Creating new stable branch 1.11 from trunk (rev 1457)

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