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

Last change on this file since 2030 was 1722, checked in by stefan, 8 years ago

adjust to changes in CoinUtils? header files

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