source: trunk/include/ClpMatrixBase.hpp @ 461

Last change on this file since 461 was 461, checked in by forrest, 16 years ago

Trying to make faster

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.9 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  /// Append Columns
62  virtual void appendCols(int number, const CoinPackedVectorBase * const * columns);
63  /// Append Rows
64  virtual void appendRows(int number, const CoinPackedVectorBase * const * rows);
65 
66  /** Returns a new matrix in reverse order without gaps
67      Is allowed to return NULL if doesn't want to have row copy */
68  virtual ClpMatrixBase * reverseOrderedCopy() const {return NULL;};
69 
70  /// Returns number of elements in column part of basis
71  virtual CoinBigIndex countBasis(ClpSimplex * model,
72                                 const int * whichColumn, 
73                                 int numberRowBasic,
74                                  int & numberColumnBasic)=0;
75  /// Fills in column part of basis
76  virtual void fillBasis(ClpSimplex * model,
77                                 const int * whichColumn, 
78                                 int & numberColumnBasic,
79                                 int * row, int * start,
80                                 int * rowCount, int * columnCount,
81                                 double * element)=0;
82  /** Creates scales for column copy (rowCopy in model may be modified)
83      default does not allow scaling
84      returns non-zero if no scaling done */
85  virtual int scale(ClpModel * model) const 
86  { return 1;};
87  /** Scales rowCopy if column copy scaled
88      Only called if scales already exist */
89  virtual void scaleRowCopy(ClpModel * model) const 
90  { };
91  /** Realy really scales column copy
92      Only called if scales already exist.
93      Up to user to delete */
94  inline virtual ClpMatrixBase * scaledColumnCopy(ClpModel * model) const 
95  { return this->clone();};
96 
97  /** Checks if all elements are in valid range.  Can just
98      return true if you are not paranoid.  For Clp I will
99      probably expect no zeros.  Code can modify matrix to get rid of
100      small elements.
101  */
102  virtual bool allElementsInRange(ClpModel * model,
103                                  double smallest, double largest)
104  { return true;};
105  /** Returns largest and smallest elements of both signs.
106      Largest refers to largest absolute value.
107      If returns zeros then can't tell anything */
108  virtual void rangeOfElements(double & smallestNegative, double & largestNegative,
109                               double & smallestPositive, double & largestPositive);
110 
111  /** Unpacks a column into an CoinIndexedvector
112   */
113  virtual void unpack(const ClpSimplex * model,CoinIndexedVector * rowArray,
114                      int column) const =0;
115  /** Unpacks a column into an CoinIndexedvector
116   ** in packed foramt
117   Note that model is NOT const.  Bounds and objective could
118   be modified if doing column generation (just for this variable) */
119  virtual void unpackPacked(ClpSimplex * model,
120                            CoinIndexedVector * rowArray,
121                            int column) const =0;
122  /** Purely for column generation and similar ideas.  Allows
123      matrix and any bounds or costs to be updated (sensibly).
124      Returns non-zero if any changes.
125  */
126  virtual int refresh(ClpSimplex * model)
127  { return 0;};
128  // Really scale matrix
129  virtual void reallyScale(const double * rowScale, const double * columnScale);
130  /** Given positive integer weights for each row fills in sum of weights
131      for each column (and slack).
132      Returns weights vector
133      Default returns vector of ones
134  */
135  virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model,int * inputWeights) const;
136  /** Adds multiple of a column into an CoinIndexedvector
137      You can use quickAdd to add to vector */
138  virtual void add(const ClpSimplex * model,CoinIndexedVector * rowArray,
139                   int column, double multiplier) const =0;
140  /** Adds multiple of a column into an array */
141  virtual void add(const ClpSimplex * model,double * array,
142                   int column, double multiplier) const =0;
143  /// Allow any parts of a created CoinPackedMatrix to be deleted
144  virtual void releasePackedMatrix() const =0;
145  /// Says whether it can do partial pricing
146  virtual bool canDoPartialPricing() const;
147  /// Returns number of hidden rows e.g. gub
148  virtual int hiddenRows() const;
149  /// Partial pricing
150  virtual void partialPricing(ClpSimplex * model, double start, double end,
151                              int & bestSequence, int & numberWanted);
152  /** expands an updated column to allow for extra rows which the main
153      solver does not know about and returns number added.
154     
155      This will normally be a no-op - it is in for GUB but may get extended to
156      general non-overlapping and embedded networks.
157     
158      mode 0 - extend
159      mode 1 - delete etc
160  */
161  virtual int extendUpdated(ClpSimplex * model,CoinIndexedVector * update,int mode);
162  /**
163     utility primal function for dealing with dynamic constraints
164     mode=0  - Set up before "update" and "times" for primal solution using extended rows
165     mode=1  - Cleanup primal solution after "times" using extended rows.
166     mode=2  - Check (or report on) primal infeasibilities
167  */
168  virtual void primalExpanded(ClpSimplex * model,int mode);
169  /**
170      utility dual function for dealing with dynamic constraints
171      mode=0  - Set up before "updateTranspose" and "transposeTimes" for duals using extended
172                updates array (and may use other if dual values pass)
173      mode=1  - Update dual solution after "transposeTimes" using extended rows.
174      mode=2  - Compute all djs and compute key dual infeasibilities
175      mode=3  - Report on key dual infeasibilities
176      mode=4  - Modify before updateTranspose in partial pricing
177  */
178  virtual void dualExpanded(ClpSimplex * model,CoinIndexedVector * array,
179                            double * other,int mode);
180  /**
181      general utility function for dealing with dynamic constraints
182      mode=0  - Create list of non-key basics in pivotVariable_ using
183                number as numberBasic in and out
184      mode=1  - Set all key variables as basic
185      mode=2  - return number extra rows needed, number gives maximum number basic
186      mode=3  - before replaceColumn
187      mode=4  - return 1 if can do primal, 2 if dual, 3 if both
188      mode=5  - save any status stuff (when in good state)
189      mode=6  - restore status stuff
190      mode=7  - flag given variable (normally sequenceIn)
191      mode=8  - unflag all variables
192      mode=9  - synchronize costs and bounds
193      mode=10  - return 1 if there may be changing bounds on variable (column generation)
194      mode=11  - make sure set is clean (used when a variable rejected - but not flagged)
195      mode=12  - after factorize but before permute stuff
196      mode=13  - at end of simplex to delete stuff
197  */
198  virtual int generalExpanded(ClpSimplex * model,int mode,int & number);
199  /**
200     update information for a pivot (and effective rhs)
201  */
202  virtual int updatePivot(ClpSimplex * model,double oldInValue, double oldOutValue);
203  /** Creates a variable.  This is called after partial pricing and may modify matrix.
204      May update bestSequence.
205  */
206  virtual void createVariable(ClpSimplex * model, int & bestSequence);
207  /** Just for debug if odd type matrix.
208      Returns number of primal infeasibilities. */
209  virtual int checkFeasible(ClpSimplex * model) const ;
210  /// Returns reduced cost of a variable
211  double reducedCost(ClpSimplex * model,int sequence) const;
212  /// Correct sequence in and out to give true value
213  virtual void correctSequence(int & sequenceIn, int & sequenceOut) const;
214  //@}
215 
216  //---------------------------------------------------------------------------
217  /**@name Matrix times vector methods
218     They can be faster if scalar is +- 1
219     Also for simplex I am not using basic/non-basic split */
220  //@{
221  /** Return <code>y + A * x * scalar</code> in <code>y</code>.
222      @pre <code>x</code> must be of size <code>numColumns()</code>
223      @pre <code>y</code> must be of size <code>numRows()</code> */
224  virtual void times(double scalar,
225                     const double * x, double * y) const=0;
226  /** And for scaling - default aborts for when scaling not supported
227      (unless pointers NULL when as normal)
228  */
229  virtual void times(double scalar,
230                     const double * x, double * y,
231                     const double * rowScale, 
232                     const double * columnScale) const;
233  /** Return <code>y + x * scalar * A</code> in <code>y</code>.
234      @pre <code>x</code> must be of size <code>numRows()</code>
235      @pre <code>y</code> must be of size <code>numColumns()</code> */
236  virtual void transposeTimes(double scalar,
237                              const double * x, double * y) const = 0;
238  /** And for scaling - default aborts for when scaling not supported
239      (unless pointers NULL when as normal)
240  */
241  virtual void transposeTimes(double scalar,
242                              const double * x, double * y,
243                              const double * rowScale, 
244                              const double * columnScale) const;
245  /** Return <code>x * scalar *A + y</code> in <code>z</code>.
246      Can use y as temporary array (will be empty at end)
247      Note - If x packed mode - then z packed mode
248      Squashes small elements and knows about ClpSimplex */
249  virtual void transposeTimes(const ClpSimplex * model, double scalar,
250                              const CoinIndexedVector * x,
251                              CoinIndexedVector * y,
252                              CoinIndexedVector * z) const = 0;
253  /** Return <code>x *A</code> in <code>z</code> but
254      just for indices in y.
255      This is only needed for primal steepest edge.
256      Note - z always packed mode */
257  virtual void subsetTransposeTimes(const ClpSimplex * model,
258                                    const CoinIndexedVector * x,
259                                    const CoinIndexedVector * y,
260                                    CoinIndexedVector * z) const = 0;
261  /** Return <code>x *A</code> in <code>z</code> but
262      just for number indices in y.
263      Default cheats with fake CoinIndexedVector and
264      then calls subsetTransposeTimes */
265  virtual void listTransposeTimes(const ClpSimplex * model,
266                                  double * x,
267                                  int * y,
268                                  int number,
269                                  double * z) const;
270  //@}
271  //@{
272  ///@name Other
273  /// Clone
274  virtual ClpMatrixBase * clone() const = 0;
275  /** Subset clone (without gaps).  Duplicates are allowed
276      and order is as given.
277      Derived classes need not provide this as it may not always make
278      sense */
279  virtual ClpMatrixBase * subsetClone (
280                                       int numberRows, const int * whichRows,
281                                       int numberColumns, const int * whichColumns) const;
282 
283  /** Returns type.
284      The types which code may need to know about are:
285      1  - ClpPackedMatrix
286      11 - ClpNetworkMatrix
287      12 - ClpPlusMinusOneMatrix
288  */
289  inline int type() const
290  { return type_;};
291  /// Sets type
292  void setType(int type) {type_=type;};
293  /// Sets up an effective RHS
294  void useEffectiveRhs(ClpSimplex * model);
295  /** Returns effective RHS offset if it is being used.  This is used for long problems
296      or big gub or anywhere where going through full columns is
297      expensive.  This may re-compute */
298  virtual double * rhsOffset(ClpSimplex * model,bool forceRefresh=false,
299                                bool check=false);
300  /// If rhsOffset used this is iteration last refreshed
301  inline int lastRefresh() const
302  { return lastRefresh_;};
303  /// If rhsOffset used this is refresh frequency (0==off)
304  inline int refreshFrequency() const
305  { return refreshFrequency_;};
306  inline void setRefreshFrequency(int value)
307  { refreshFrequency_=value;};
308  /// whether to skip dual checks most of time
309  inline bool skipDualCheck() const
310  { return skipDualCheck_;};
311  inline void setSkipDualCheck(bool yes)
312  { skipDualCheck_=yes;};
313  /** Partial pricing tuning parameter - minimum number of "objects" to scan.
314      e.g. number of Gub sets but could be number of variables */
315  inline int minimumObjectsScan() const
316  { return minimumObjectsScan_;};
317  inline void setMinimumObjectsScan(int value)
318  { minimumObjectsScan_=value;};
319  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
320  inline int minimumGoodReducedCosts() const
321  { return minimumGoodReducedCosts_;};
322  inline void setMinimumGoodReducedCosts(int value)
323  { minimumGoodReducedCosts_=value;};
324  /// Current start of search space in matrix (as fraction)
325  inline double startFraction() const
326  { return startFraction_;};
327  inline void setStartFraction(double value) 
328  { startFraction_ = value;};
329  /// Current end of search space in matrix (as fraction)
330  inline double endFraction() const
331  { return endFraction_;};
332  inline void setEndFraction(double value) 
333  { endFraction_ = value;};
334  /// Current best reduced cost
335  inline double savedBestDj() const
336  { return savedBestDj_;};
337  inline void setSavedBestDj(double value) 
338  { savedBestDj_ = value;};
339  /// Initial number of negative reduced costs wanted
340  inline int originalWanted() const
341  { return originalWanted_;};
342  inline void setOriginalWanted(int value) 
343  { originalWanted_ = value;};
344  /// Current number of negative reduced costs which we still need
345  inline int currentWanted() const
346  { return currentWanted_;};
347  inline void setCurrentWanted(int value) 
348  { currentWanted_ = value;};
349  /// Current best sequence
350  inline int savedBestSequence() const
351  { return savedBestSequence_;};
352  inline void setSavedBestSequence(int value) 
353  { savedBestSequence_ = value;};
354  //@}
355 
356 
357protected:
358 
359  /**@name Constructors, destructor<br>
360     <strong>NOTE</strong>: All constructors are protected. There's no need
361     to expose them, after all, this is an abstract class. */
362  //@{
363  /** Default constructor. */
364  ClpMatrixBase();
365  /** Destructor (has to be public) */
366public:
367  virtual ~ClpMatrixBase();
368protected:
369  // Copy
370  ClpMatrixBase(const ClpMatrixBase&);
371  // Assignment
372  ClpMatrixBase& operator=(const ClpMatrixBase&);
373  //@}
374 
375 
376protected:
377  /**@name Data members
378     The data members are protected to allow access for derived classes. */
379  //@{
380  /** Effective RHS offset if it is being used.  This is used for long problems
381      or big gub or anywhere where going through full columns is
382      expensive */
383  double * rhsOffset_;
384  /// Current start of search space in matrix (as fraction)
385  double startFraction_;
386  /// Current end of search space in matrix (as fraction)
387  double endFraction_;
388  /// Best reduced cost so far
389  double savedBestDj_;
390  /// Initial number of negative reduced costs wanted
391  int originalWanted_;
392  /// Current number of negative reduced costs which we still need
393  int currentWanted_;
394  /// Saved best sequence in pricing
395  int savedBestSequence_;
396  /// type (may be useful)
397  int type_;
398  /// If rhsOffset used this is iteration last refreshed
399  int lastRefresh_;
400  /// If rhsOffset used this is refresh frequency (0==off)
401  int refreshFrequency_;
402  /// Partial pricing tuning parameter - minimum number of "objects" to scan
403  int minimumObjectsScan_;
404  /// Partial pricing tuning parameter - minimum number of negative reduced costs to get
405  int minimumGoodReducedCosts_;
406  /// True sequence in (i.e. from larger problem)
407  int trueSequenceIn_;
408  /// True sequence out (i.e. from larger problem)
409  int trueSequenceOut_;
410  /// whether to skip dual checks most of time
411  bool skipDualCheck_;
412  //@}
413};
414// bias for free variables
415#define FREE_BIAS 1.0e1
416// Acceptance criteria for free variables
417#define FREE_ACCEPT 1.0e2
418
419#endif
Note: See TracBrowser for help on using the repository browser.