source: releases/1.9.0/Clp/src/ClpMatrixBase.hpp

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

adding possibility of long doubles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 20.1 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                                 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 * model, const ClpSimplex * baseModel=NULL) 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  */
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  /** Return <code>x * scalar *A + y</code> in <code>z</code>.
280      Can use y as temporary array (will be empty at end)
281      Note - If x packed mode - then z packed mode
282      Squashes small elements and knows about ClpSimplex */
283  virtual void transposeTimes(const ClpSimplex * model, double scalar,
284                              const CoinIndexedVector * x,
285                              CoinIndexedVector * y,
286                              CoinIndexedVector * z) const = 0;
287  /** Return <code>x *A</code> in <code>z</code> but
288      just for indices in y.
289      This is only needed for primal steepest edge.
290      Note - z always packed mode */
291  virtual void subsetTransposeTimes(const ClpSimplex * model,
292                                    const CoinIndexedVector * x,
293                                    const CoinIndexedVector * y,
294                                    CoinIndexedVector * z) const = 0;
295  /** Returns true if can combine transposeTimes and subsetTransposeTimes
296      and if it would be faster */
297  virtual bool canCombine(const ClpSimplex * model,
298                          const CoinIndexedVector * pi) const {return false;}
299  /// Updates two arrays for steepest and does devex weights (need not be coded)
300  virtual void transposeTimes2(const ClpSimplex * model,
301                               const CoinIndexedVector * pi1, CoinIndexedVector * dj1,
302                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
303                               CoinIndexedVector * spare,
304                               double referenceIn, double devex,
305                               // Array for exact devex to say what is in reference framework
306                               unsigned int * reference,
307                               double * weights, double scaleFactor);
308  /// Updates second array for steepest and does devex weights (need not be coded)
309  virtual void subsetTimes2(const ClpSimplex * model,
310                            CoinIndexedVector * dj1,
311                               const CoinIndexedVector * pi2, CoinIndexedVector * dj2,
312                               double referenceIn, double devex,
313                               // Array for exact devex to say what is in reference framework
314                               unsigned int * reference,
315                               double * weights, double scaleFactor);
316  /** Return <code>x *A</code> in <code>z</code> but
317      just for number indices in y.
318      Default cheats with fake CoinIndexedVector and
319      then calls subsetTransposeTimes */
320  virtual void listTransposeTimes(const ClpSimplex * model,
321                                  double * x,
322                                  int * y,
323                                  int number,
324                                  double * z) const;
325  //@}
326  //@{
327  ///@name Other
328  /// Clone
329  virtual ClpMatrixBase * clone() const = 0;
330  /** Subset clone (without gaps).  Duplicates are allowed
331      and order is as given.
332      Derived classes need not provide this as it may not always make
333      sense */
334  virtual ClpMatrixBase * subsetClone (
335                                       int numberRows, const int * whichRows,
336                                       int numberColumns, const int * whichColumns) const;
337  /// Gets rid of any mutable by products
338  virtual void backToBasics() {}
339  /** Returns type.
340      The types which code may need to know about are:
341      1  - ClpPackedMatrix
342      11 - ClpNetworkMatrix
343      12 - ClpPlusMinusOneMatrix
344  */
345  inline int type() const
346  { return type_;}
347  /// Sets type
348  void setType(int type) {type_=type;}
349  /// Sets up an effective RHS
350  void useEffectiveRhs(ClpSimplex * model);
351  /** Returns effective RHS offset if it is being used.  This is used for long problems
352      or big gub or anywhere where going through full columns is
353      expensive.  This may re-compute */
354  virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,
355                                bool check=false);
356  /// If rhsOffset used this is iteration last refreshed
357  inline int lastRefresh() const
358  { return lastRefresh_;}
359  /// If rhsOffset used this is refresh frequency (0==off)
360  inline int refreshFrequency() const
361  { return refreshFrequency_;}
362  inline void setRefreshFrequency(int value)
363  { refreshFrequency_=value;}
364  /// whether to skip dual checks most of time
365  inline bool skipDualCheck() const
366  { return skipDualCheck_;}
367  inline void setSkipDualCheck(bool yes)
368  { skipDualCheck_=yes;}
369  /** Partial pricing tuning parameter - minimum number of "objects" to scan.
370      e.g. number of Gub sets but could be number of variables */
371  inline int minimumObjectsScan() const
372  { return minimumObjectsScan_;}
373  inline void setMinimumObjectsScan(int value)
374  { minimumObjectsScan_=value;}
375  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
376  inline int minimumGoodReducedCosts() const
377  { return minimumGoodReducedCosts_;}
378  inline void setMinimumGoodReducedCosts(int value)
379  { minimumGoodReducedCosts_=value;}
380  /// Current start of search space in matrix (as fraction)
381  inline double startFraction() const
382  { return startFraction_;}
383  inline void setStartFraction(double value) 
384  { startFraction_ = value;}
385  /// Current end of search space in matrix (as fraction)
386  inline double endFraction() const
387  { return endFraction_;}
388  inline void setEndFraction(double value) 
389  { endFraction_ = value;}
390  /// Current best reduced cost
391  inline double savedBestDj() const
392  { return savedBestDj_;}
393  inline void setSavedBestDj(double value) 
394  { savedBestDj_ = value;}
395  /// Initial number of negative reduced costs wanted
396  inline int originalWanted() const
397  { return originalWanted_;}
398  inline void setOriginalWanted(int value) 
399  { originalWanted_ = value;}
400  /// Current number of negative reduced costs which we still need
401  inline int currentWanted() const
402  { return currentWanted_;}
403  inline void setCurrentWanted(int value) 
404  { currentWanted_ = value;}
405  /// Current best sequence
406  inline int savedBestSequence() const
407  { return savedBestSequence_;}
408  inline void setSavedBestSequence(int value) 
409  { savedBestSequence_ = value;}
410  //@}
411 
412 
413protected:
414 
415  /**@name Constructors, destructor<br>
416     <strong>NOTE</strong>: All constructors are protected. There's no need
417     to expose them, after all, this is an abstract class. */
418  //@{
419  /** Default constructor. */
420  ClpMatrixBase();
421  /** Destructor (has to be public) */
422public:
423  virtual ~ClpMatrixBase();
424protected:
425  // Copy
426  ClpMatrixBase(const ClpMatrixBase&);
427  // Assignment
428  ClpMatrixBase& operator=(const ClpMatrixBase&);
429  //@}
430 
431 
432protected:
433  /**@name Data members
434     The data members are protected to allow access for derived classes. */
435  //@{
436  /** Effective RHS offset if it is being used.  This is used for long problems
437      or big gub or anywhere where going through full columns is
438      expensive */
439  double * rhsOffset_;
440  /// Current start of search space in matrix (as fraction)
441  double startFraction_;
442  /// Current end of search space in matrix (as fraction)
443  double endFraction_;
444  /// Best reduced cost so far
445  double savedBestDj_;
446  /// Initial number of negative reduced costs wanted
447  int originalWanted_;
448  /// Current number of negative reduced costs which we still need
449  int currentWanted_;
450  /// Saved best sequence in pricing
451  int savedBestSequence_;
452  /// type (may be useful)
453  int type_;
454  /// If rhsOffset used this is iteration last refreshed
455  int lastRefresh_;
456  /// If rhsOffset used this is refresh frequency (0==off)
457  int refreshFrequency_;
458  /// Partial pricing tuning parameter - minimum number of "objects" to scan
459  int minimumObjectsScan_;
460  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
461  int minimumGoodReducedCosts_;
462  /// True sequence in (i.e. from larger problem)
463  int trueSequenceIn_;
464  /// True sequence out (i.e. from larger problem)
465  int trueSequenceOut_;
466  /// whether to skip dual checks most of time
467  bool skipDualCheck_;
468  //@}
469};
470// bias for free variables
471#define FREE_BIAS 1.0e1
472// Acceptance criteria for free variables
473#define FREE_ACCEPT 1.0e2
474
475#endif
Note: See TracBrowser for help on using the repository browser.