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

Last change on this file since 800 was 800, checked in by ladanyi, 14 years ago

finishing conversion to svn

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 20.0 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  /** The length of a single major-dimension vector. */
58  virtual int getVectorLength(int index) const ;
59  /** Delete the columns whose indices are listed in <code>indDel</code>. */
60  virtual void deleteCols(const int numDel, const int * indDel) = 0;
61  /** Delete the rows whose indices are listed in <code>indDel</code>. */
62  virtual void deleteRows(const int numDel, const int * indDel) = 0;
63#ifndef CLP_NO_VECTOR
64  /// Append Columns
65  virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
66  /// Append Rows
67  virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
68#endif
69  /** Modify one element of packed matrix.  An element may be added.
70      This works for either ordering If the new element is zero it will be
71      deleted unless keepZero true */
72  virtual void modifyCoefficient(int row, int column, double newElement,
73                                 bool keepZero=false);
74  /** Append a set of rows/columns to the end of the matrix. Returns number of errors
75      i.e. if any of the new rows/columns contain an index that's larger than the
76      number of columns-1/rows-1 (if numberOther>0) or duplicates
77      If 0 then rows, 1 if columns */
78  virtual int appendMatrix(int number, int type,
79                           const CoinBigIndex * starts, const int * index,
80                           const double * element, int numberOther=-1);
81 
82  /** Returns a new matrix in reverse order without gaps
83      Is allowed to return NULL if doesn't want to have row copy */
84  virtual ClpMatrixBase * reverseOrderedCopy() const {return NULL;};
85 
86  /// Returns number of elements in column part of basis
87  virtual CoinBigIndex countBasis(ClpSimplex * model,
88                                 const int * whichColumn, 
89                                 int numberRowBasic,
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                                 double * 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 * model) const 
102  { return 1;};
103  /** Scales rowCopy if column copy scaled
104      Only called if scales already exist */
105  virtual void scaleRowCopy(ClpModel * model) 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 * model) 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 * model,
127                                  double smallest, double largest,
128                                  int check=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 * model)
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  virtual int generalExpanded(ClpSimplex * model,int mode,int & number);
231  /**
232     update information for a pivot (and effective rhs)
233  */
234  virtual int updatePivot(ClpSimplex * model,double oldInValue, double oldOutValue);
235  /** Creates a variable.  This is called after partial pricing and may modify matrix.
236      May update bestSequence.
237  */
238  virtual void createVariable(ClpSimplex * model, int & bestSequence);
239  /** Just for debug if odd type matrix.
240      Returns number of primal infeasibilities. */
241  virtual int checkFeasible(ClpSimplex * model,double & sum) const ;
242  /// Returns reduced cost of a variable
243  double reducedCost(ClpSimplex * model,int sequence) const;
244  /// Correct sequence in and out to give true value
245  virtual void correctSequence(int & sequenceIn, int & sequenceOut) const;
246  //@}
247 
248  //---------------------------------------------------------------------------
249  /**@name Matrix times vector methods
250     They can be faster if scalar is +- 1
251     Also for simplex I am not using basic/non-basic split */
252  //@{
253  /** Return <code>y + A * x * scalar</code> in <code>y</code>.
254      @pre <code>x</code> must be of size <code>numColumns()</code>
255      @pre <code>y</code> must be of size <code>numRows()</code> */
256  virtual void times(double scalar,
257                     const double * x, double * y) const=0;
258  /** And for scaling - default aborts for when scaling not supported
259      (unless pointers NULL when as normal)
260  */
261  virtual void times(double scalar,
262                     const double * x, double * y,
263                     const double * rowScale, 
264                     const double * columnScale) const;
265  /** Return <code>y + x * scalar * A</code> in <code>y</code>.
266      @pre <code>x</code> must be of size <code>numRows()</code>
267      @pre <code>y</code> must be of size <code>numColumns()</code> */
268  virtual void transposeTimes(double scalar,
269                              const double * x, double * y) const = 0;
270  /** And for scaling - default aborts for when scaling not supported
271      (unless pointers NULL when as normal)
272  */
273  virtual void transposeTimes(double scalar,
274                              const double * x, double * y,
275                              const double * rowScale, 
276                              const double * columnScale,
277                              double * spare=NULL) const;
278  /** Return <code>x * scalar *A + y</code> in <code>z</code>.
279      Can use y as temporary array (will be empty at end)
280      Note - If x packed mode - then z packed mode
281      Squashes small elements and knows about ClpSimplex */
282  virtual void transposeTimes(const ClpSimplex * model, double scalar,
283                              const CoinIndexedVector * x,
284                              CoinIndexedVector * y,
285                              CoinIndexedVector * z) const = 0;
286  /** Return <code>x *A</code> in <code>z</code> but
287      just for indices in y.
288      This is only needed for primal steepest edge.
289      Note - z always packed mode */
290  virtual void subsetTransposeTimes(const ClpSimplex * model,
291                                    const CoinIndexedVector * x,
292                                    const CoinIndexedVector * y,
293                                    CoinIndexedVector * z) const = 0;
294  /** Returns true if can combine transposeTimes and subsetTransposeTimes
295      and if it would be faster */
296  virtual bool canCombine(const ClpSimplex * model,
297                          const CoinIndexedVector * pi) const {return false;};
298  /// Updates two arrays for steepest and does devex weights (need not be coded)
299  virtual void transposeTimes2(const ClpSimplex * model,
300                               const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
301                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
302                               CoinIndexedVector * spare,
303                               double referenceIn, double devex,
304                               // Array for exact devex to say what is in reference framework
305                               unsigned int * reference,
306                               double * weights, double scaleFactor);
307  /// Updates second array for steepest and does devex weights (need not be coded)
308  virtual void subsetTimes2(const ClpSimplex * model,
309                            CoinIndexedVector * dj1,
310                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
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  /** Return <code>x *A</code> in <code>z</code> but
316      just for number indices in y.
317      Default cheats with fake CoinIndexedVector and
318      then calls subsetTransposeTimes */
319  virtual void listTransposeTimes(const ClpSimplex * model,
320                                  double * x,
321                                  int * y,
322                                  int number,
323                                  double * z) const;
324  //@}
325  //@{
326  ///@name Other
327  /// Clone
328  virtual ClpMatrixBase * clone() const = 0;
329  /** Subset clone (without gaps).  Duplicates are allowed
330      and order is as given.
331      Derived classes need not provide this as it may not always make
332      sense */
333  virtual ClpMatrixBase * subsetClone (
334                                       int numberRows, const int * whichRows,
335                                       int numberColumns, const int * whichColumns) const;
336 
337  /** Returns type.
338      The types which code may need to know about are:
339      1  - ClpPackedMatrix
340      11 - ClpNetworkMatrix
341      12 - ClpPlusMinusOneMatrix
342  */
343  inline int type() const
344  { return type_;};
345  /// Sets type
346  void setType(int type) {type_=type;};
347  /// Sets up an effective RHS
348  void useEffectiveRhs(ClpSimplex * model);
349  /** Returns effective RHS offset if it is being used.  This is used for long problems
350      or big gub or anywhere where going through full columns is
351      expensive.  This may re-compute */
352  virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,
353                                bool check=false);
354  /// If rhsOffset used this is iteration last refreshed
355  inline int lastRefresh() const
356  { return lastRefresh_;};
357  /// If rhsOffset used this is refresh frequency (0==off)
358  inline int refreshFrequency() const
359  { return refreshFrequency_;};
360  inline void setRefreshFrequency(int value)
361  { refreshFrequency_=value;};
362  /// whether to skip dual checks most of time
363  inline bool skipDualCheck() const
364  { return skipDualCheck_;};
365  inline void setSkipDualCheck(bool yes)
366  { skipDualCheck_=yes;};
367  /** Partial pricing tuning parameter - minimum number of "objects" to scan.
368      e.g. number of Gub sets but could be number of variables */
369  inline int minimumObjectsScan() const
370  { return minimumObjectsScan_;};
371  inline void setMinimumObjectsScan(int value)
372  { minimumObjectsScan_=value;};
373  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
374  inline int minimumGoodReducedCosts() const
375  { return minimumGoodReducedCosts_;};
376  inline void setMinimumGoodReducedCosts(int value)
377  { minimumGoodReducedCosts_=value;};
378  /// Current start of search space in matrix (as fraction)
379  inline double startFraction() const
380  { return startFraction_;};
381  inline void setStartFraction(double value) 
382  { startFraction_ = value;};
383  /// Current end of search space in matrix (as fraction)
384  inline double endFraction() const
385  { return endFraction_;};
386  inline void setEndFraction(double value) 
387  { endFraction_ = value;};
388  /// Current best reduced cost
389  inline double savedBestDj() const
390  { return savedBestDj_;};
391  inline void setSavedBestDj(double value) 
392  { savedBestDj_ = value;};
393  /// Initial number of negative reduced costs wanted
394  inline int originalWanted() const
395  { return originalWanted_;};
396  inline void setOriginalWanted(int value) 
397  { originalWanted_ = value;};
398  /// Current number of negative reduced costs which we still need
399  inline int currentWanted() const
400  { return currentWanted_;};
401  inline void setCurrentWanted(int value) 
402  { currentWanted_ = value;};
403  /// Current best sequence
404  inline int savedBestSequence() const
405  { return savedBestSequence_;};
406  inline void setSavedBestSequence(int value) 
407  { savedBestSequence_ = value;};
408  //@}
409 
410 
411protected:
412 
413  /**@name Constructors, destructor<br>
414     <strong>NOTE</strong>: All constructors are protected. There's no need
415     to expose them, after all, this is an abstract class. */
416  //@{
417  /** Default constructor. */
418  ClpMatrixBase();
419  /** Destructor (has to be public) */
420public:
421  virtual ~ClpMatrixBase();
422protected:
423  // Copy
424  ClpMatrixBase(const ClpMatrixBase&);
425  // Assignment
426  ClpMatrixBase& operator=(const ClpMatrixBase&);
427  //@}
428 
429 
430protected:
431  /**@name Data members
432     The data members are protected to allow access for derived classes. */
433  //@{
434  /** Effective RHS offset if it is being used.  This is used for long problems
435      or big gub or anywhere where going through full columns is
436      expensive */
437  double * rhsOffset_;
438  /// Current start of search space in matrix (as fraction)
439  double startFraction_;
440  /// Current end of search space in matrix (as fraction)
441  double endFraction_;
442  /// Best reduced cost so far
443  double savedBestDj_;
444  /// Initial number of negative reduced costs wanted
445  int originalWanted_;
446  /// Current number of negative reduced costs which we still need
447  int currentWanted_;
448  /// Saved best sequence in pricing
449  int savedBestSequence_;
450  /// type (may be useful)
451  int type_;
452  /// If rhsOffset used this is iteration last refreshed
453  int lastRefresh_;
454  /// If rhsOffset used this is refresh frequency (0==off)
455  int refreshFrequency_;
456  /// Partial pricing tuning parameter - minimum number of "objects" to scan
457  int minimumObjectsScan_;
458  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
459  int minimumGoodReducedCosts_;
460  /// True sequence in (i.e. from larger problem)
461  int trueSequenceIn_;
462  /// True sequence out (i.e. from larger problem)
463  int trueSequenceOut_;
464  /// whether to skip dual checks most of time
465  bool skipDualCheck_;
466  //@}
467};
468// bias for free variables
469#define FREE_BIAS 1.0e1
470// Acceptance criteria for free variables
471#define FREE_ACCEPT 1.0e2
472
473#endif
Note: See TracBrowser for help on using the repository browser.