source: trunk/Clp/src/ClpMatrixBase.hpp @ 799

Last change on this file since 799 was 799, checked in by andreasw, 14 years ago

undid last commit (patches incorrectly applied)

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