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

Last change on this file since 1525 was 1525, checked in by mjs, 10 years ago

Formatted .cpp, .hpp, .c, .h files with "astyle -A4 -p". This matches the formatting used in the grand CBC reorganization.

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