source: trunk/include/ClpMatrixBase.hpp @ 468

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

to make sbb faster

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